ABC003-D:AtCoder社の冬

問題

https://beta.atcoder.jp/contests/abc003/tasks/abc003_4

制約

  • 1 <= R, C <= 30
  • 1 <= X <= R, 1 <= Y <= C
  • 0 <= D, L, 1 <= D, L <= X * Y

考え方

包除原理である。まず、R * C から X * Y の長方形のとり方を求める。次に X * Y の長方形に D + L 個の置き方について考える。部分点解法である X * Y = D + L の場合は X * Y の長方形に D + L 個の置き方は 1 通りに定まる。そうでない場合は以下のように考える。

X * Y の長方形に D + L 個のすべての置き方 - ( NG となる置き方)

X * Y の長方形に D + L 個の置き方が NG となる場合について考える。以下のような場合は条件を満たさない置き方になる。

f:id:d_tutuz:20180823081722p:plain

NG になるパターンをそれぞれ P, Q, R, S と呼び、その時の場合の数を | P |, | Q |, | R |, | S | とし、すべての置き方を | N | とする。
求めたい数は N - ( | P ∨ Q ∨ R ∨ S | ) である。
これは包除原理より

N - ( | P | + | Q | + | R | + | S | - | P ∧ Q | - | P ∧ R | - | P ∧ S | - | Q ∧ R | - | Q ∧ S | - | R ∧ S | + | P ∧ Q ∧ R | + | P ∧ Q ∧ S | + | P ∧ R ∧ S | + | Q ∧ R ∧ S | - | P ∧ Q ∧ R ∧ S | )

で求めることができる。

さて、ここで包除原理の実装について考える。これはO(2N)で求めることができる。つまり各 P, Q, R, S の集合をビットと見立てて、ビットが 1 のときにその集合が含まれると解釈することで網羅することができる。対応するイメージ図は以下である。

f:id:d_tutuz:20180823230613p:plain

上記の対応関係を考えることで今回の 4 つの集合を持つ場合の包除原理が 1 << 4 = 16 回ループすることで網羅できる。P, Q の場合は上下の x 方向の大きさが -1 になり、R, S の場合は 左右の y 方向の大きさが -1 になる。またビットの偶奇によってその要素の正負がわかる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int r = in.nextInt(), c = in.nextInt(), x = in.nextInt(), y = in.nextInt();
            int d = in.nextInt(), l = in.nextInt();

            long sum = 0;
            for (int i = 0; i < 1 << 4; i++) {
                int tx = x;
                int ty = y;

                if ((i >> 0 & 1) == 1) ty--;
                if ((i >> 1 & 1) == 1) ty--;
                if ((i >> 2 & 1) == 1) tx--;
                if ((i >> 3 & 1) == 1) tx--;

                if (tx < 0 || ty < 0) continue;

                if (Integer.bitCount(i) % 2 == 0) {
                    sum += comb(tx * ty, d + l) * comb(d + l, d);
                } else {
                    sum -= comb(tx * ty, d + l) * comb(d + l, d) % MOD;
                }
                sum = (sum + MOD) % MOD;
            }

            sum *= (r - x + 1) * (c - y + 1);

            out.println(sum % MOD);

        }

ポイント

  • 包除原理

類題

雑記

包除原理の実装(状態をビットと見立てて場合分け+ビットの偶奇で正負を判断する)方法はきれいですね。