Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contetst 242 F問題 Black and White Rooks

AtCoder ABC ABC242 F問題 500 pts

問題

提出解答

問題の概要

縦 $N$ 行, 横 $M$ 列のマスからなる将棋盤と, 黒の飛車 $B$ 個, 白の飛車 $W$ 個がある.

この将棋盤に $(B+W)$ 個の飛車を置く. 以下を満たすような置き方は何通りか?

$(B+W)$ 個の飛車全てが置かれている.
各マスに置かている飛車は高々1個である.
ある黒の飛車と白の飛車の組み合わせで互いに攻撃し合うものが存在しない.

制約

$1 \leq N,M \leq 50$
$1 \leq B,W \leq 2500$
$B+W \leq NM$

解法

「ある黒の飛車と白の飛車の組み合わせで互いに攻撃し合うものが存在しない」ことと, 「黒の飛車と白の飛車の両方が存在する行や列が存在しない」ことは同値である.

従って, 条件を満たすような飛車の配置を次のようにして漏れなく, 重複なく分類することができる.

黒の飛車が存在する列が $r_b$ 列, 白の飛車が存在する列が $r_w$ 列, 黒の飛車が存在する行が $c_b$ 行, 白の飛車が存在する行が $c_w$ 行となるような配置の方法.

また, 各色の飛車が存在する行と列をたちまち決定させると, 黒, 白の飛車の置き方は独立である.

よって, 次の問題を解ければよいことになる.

縦 $X$ 行, 横 $Y$ 列からなる将棋盤に $K$ 個の飛車を置く方法のうち, 全ての行と列に $1$ 個以上の飛車が存在するような配置の方法

この問題の答えを $T(X,Y;K)$ と書くことにする.

縦 $X$ 行, 横 $Y$ 列からなる将棋盤に $K$ 個の飛車を置く方法の数は $\dbinom{XY}{K}$ である. これから条件を満たさない配置を引くことにする.

条件を見たない配置の方法について, 次のように $a,b$ を定める.

飛車が存在する列の数は $a$ , 存在する列の数は $b$ である.

このとき, $0 \leq a \leq X, 0 \leq b \leq Y, (a,b) \neq (X,Y)$ である. これと, どの $a$ 行, $b$ 列に飛車を存在させるかも考慮することにより,

$\displaystyle T(X,Y;K)=\dbinom{XY}{K}-\sum_{\substack{0 \leq a \leq X \\ 0 \leq b \leq Y \\ (a,b) \neq (X,Y)}} \dbinom{X}{a} \dbinom{Y}{b} T(a,b;K)$

である.

最後に, あり得る $r_b, r_w, c_b, c_r$ に対して全て計算する. ただし, この場合もどの行と列にどの色の飛車を存在させるかということを考慮すると, 求めるべき答えは

$\displaystyle \sum_{0 \leq r_b, r_w \leq N \\ 0 \leq c_b, c_w \leq M \\ r_b+r_w \leq N \\ c_b+c_r \leq M} \dbinom{N}{r_b} \dbinom{N-r_b}{r_w} \dbinom{M}{c_b} \dbinom{M-c_b}{c_w} T(r_b,c_b; B) T(r_w,c_w;W)$

である.

計算量は前計算で $T(a,b;K)$ を求めるパート, 最終解答を求めるパート共に $O(N^2 M^2)$ であるから, 全体でも $O(N^2 M^2)$ である.