問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$H$ 行 $W$ 列からなるグリッドがある. この中から $K$ 個のマスをランダムに選び, その $K$ 個のを含む最小の長方形に含まれるマスの数をスコアとする.

スコアの期待値を求めよ.

制約

$1 \leq H,W \leq 1000$
$1 \leq K \leq 1000$

解法

上から $i$ 行目, 左から $j$ 列目のマス目を $(i,j)$ と書き, マスの部分集合 $A$ を含む最小の長方形に含まれるマスの集合を $B(A)$ と書くことにする.

スコアを取る確率変数を $X$ とすると,

$\displaystyle X=\sum_{\substack{1 \leq i \leq H \\ 1 \leq j \leq W}} [(i,j) \in B(A)]$

である.

ここで, $A$ の選び方はランダムであり, 可能性は $\dbinom{HW}{K}$ 通りあるので,

$\displaystyle \begin{align*} E[X] &=\sum_A \left(\sum_{\substack{1 \leq i \leq H \\ 1 \leq j \leq W}} [(i,j) \in B(A)] \right) \dbinom{HW}{K}^{-1} \\ &=\dbinom{HW}{K}^{-1} \sum_{\substack{1 \leq i \leq H \\ 1 \leq j \leq W}} \left(\sum_A [(i,j) \in B(A)] \right) \end{align*}\$

である.

よって, 各マスについて, $(i,j) \in B(A)$ となる $A$ の個数を求めることにする.

このとき, $A:=\{(a_1, b_1), \dots, (a_K, b_K)\}$ としたとき, 以下は同値である.

$(i,j) \in B(A)$
$\min (a_1, \dots, a_K) \leq i \leq \max (a_1, \dots, a_K)$ かつ $\min (b_1, \dots, b_K) \leq j \leq \max (b_1, \dots, b_K)$

ここで, $\min (a_1, \dots, a_K) \leq i$ という条件は $i$ 以下の $a_k$ が存在するという条件になり, やや扱いにくい. そこで, 否定を取り, $\min (a_1, \dots, a_K) \gt i$ とすると, 全ての $a_k$ が $i$ より大きいということになり扱いやすくなる.

よって, 以下のようにする.

$(i,j) \not \in B(A)$
( $\min (a_1, \dots, a_K) \gt i$ または $\max (a_1, \dots, a_K) \lt i$ ) または ( $\min (b_1, \dots, b_K) \gt j$ または $\max (b_1, \dots, b_K) \lt j$ ).

$\min (a_1, \dots, a_K) \gt i$ または $\max (a_1, \dots, a_K) \lt i$ を $P$ , $\min (b_1, \dots, b_K) \gt j$ または $\max (b_1, \dots, b_K) \lt j$ を $Q$ ということにする.

$P$ または $Q$ を満たす $A$ の数を求める. ここで, 包除原理により, $P,Q, P$ かつ $Q$ を満たす $A$ の数を求められれば良い.

$P$ となるような $A$ の数を考える. このとき, $\min (a_1, \dots, a_K) \gt i$ と $\max (a_1, \dots, a_K) \lt i$ は同時には達成不可能であるから, それぞれの場合についての場合の数を足し合わせれば良い.

$\min (a_1, \dots, a_K) \gt i$ ということは $(i+1)$ 行目以降から $K$ 個のマスを選ぶことになるので, $\dbinom{(H-i)W}{K}$ 個である. $\max (a_1, \dots, a_K) \lt i$ についても同様にして $\dbinom{(i-1)W}{K}$ 個である.

よって, $P$ となる $A$ の数は

$\dbinom{(H-i)W}{K}+\dbinom{(i-1)W}{K}$

である.

$Q$ についても同様にして, $Q$ となる $A$ の数は

$\dbinom{H(W-j)}{K}+\dbinom{H(j-1)}{K}$

である.

最後に, $P,Q$ が同時に達成される場合を考える. このとき, 分配法則により, $P,Q$ が同時に達成されることと, 以下のうちのどれかが成り立つことは同値になる.

$\min (a_1, \dots, a_K) \gt i$ かつ $\min (b_1, \dots, b_K) \gt j$ .
$\min (a_1, \dots, a_K) \gt i$ かつ $\max (b_1, \dots, b_K) \lt j$ .
$\max (a_1, \dots, a_K) \lt i$ かつ $\min (b_1, \dots, b_K) \gt j$ .
$\max (a_1, \dots, a_K) \lt i$ かつ $\max (b_1, \dots, b_K) \lt j$ .

また, この $4$ について, どの $2$ つを選んでも同時に達成することはない. よって, 各場合についての結果を足し合わせればよい.

例えば, 一番上の場合については $\dbinom{(H-i)(W-j)}{K}$ 通りとなる. 他の場合も同様にして求めることにより, $P,Q$ が同時に達成する $A$ の数は

$\dbinom{(H-i)(W-j)}{K}+\dbinom{(H-i)(j-1)}{K}+\dbinom{(i-1)(W-j)}{K}+\dbinom{(i-1)(j-1)}{K}$

である.

よって, 求めるべき期待値 $E[X ]$ は $(i,j)$ に対して,

$S_{i,j}:=\dbinom{(H-i)W}{K}+\dbinom{(i-1)W}{K}+\dbinom{H(W-j)}{K}+\dbinom{H(j-1)}{K},$

$T_{i,j}:=\dbinom{(H-i)(W-j)}{K}+\dbinom{(H-i)(j-1)}{K}+\dbinom{(i-1)(W-j)}{K}+\dbinom{(i-1)(j-1)}{K}$

とおくと,

$\begin{align*} E[X] &=\dbinom{HW}{K}^{-1} \sum_{\substack{1 \leq i \leq H \\ 1 \leq j \leq W}} \left(\dbinom{HW}{K}-\left(S_{i,j}-T_{i,j} \right) \right) \\ &=HW-\dbinom{HW}{K}^{-1} \sum_{\substack{1 \leq i \leq H \\ 1 \leq j \leq W}} \left(S_{i,j}-T_{i,j} \right) \\ \end{align*}$

であり, $S_{i,j}, T_{i,j}$ は $4$ 個の二項係数の和であるから, 適切な $O(HW)$ 時間の前計算により, 期待値を $O(HW)$ 時間で求められる.

Kazun の競プロ記録

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

AtCoder Beginner Contest 297 F問題 Minimum Bounding Box 2

問題

提出解答

問題の概要

制約

解法

である.