ある集合の部分集合それぞれの中央値を直接求めるのはなかなか難しいが、 ある数 $m$ を固定して「$m$ 以上になる/以下になるものがあるかないか」という判定はある程度高速にできるので、 二分探索が有効な解法の1つとなる。
中央値を言い換えると、 今回の定義では「自身を超える値が $\frac{K^2}{2}$ 以下となる数の中で、最小の数」といえる。
1次元での例 2: o x o x o o x 4/7 半数を超えるのでNG 3 1 4 1 5 9 2 → 3: x x o x o o x 3/7 OK 4: x x x x o o x 2/7 OK → 中央値は3
これで求まる。
中央値を調べるには、$N \times N$ 配列を{$m$ 以下=0, $m$ 超過=1} で変換した後、二次元累積和を使うと高速。
Pythonでは、scipy.signal.convolve2d という
二次元たたみ込みのできる関数があったのだが、普通に遅かった。
重みを変えたりできるので、中身は普通に毎回 $K \times K$ を計算してるのかな。
$N$ が馬鹿デカいが、黒ポーンが無い行は 白ポーンは下に移動するしかないので到達可能な列は変わらない。
調べるのは黒ポーンのある行だけでよい。
また、その行でどの列に注目すればよいかに関しても、
i-1行 ... × ○ ○ ○ × ○ × ... ○:到達可能な列 ×:不可能 ▲ ▲ ▲ ▲ ▲:i行目の黒ポーン i 行 ... × ○ ○ ○ ○ × × 理由 (1)(2)(2)(1)(2)(3)(1)
直前の行と変化があるのは黒ポーンがある列のみで、他はそのまま引き継がれる。
「到達可能な列の集合」をsetなどで管理して、変化のある箇所のみ追加削除すればよい。
setに対する操作は全体で黒ポーンの個数 $O(M)$ になるので、十分間に合う。
実装の注意点として、
としないと、1列ごとに追加削除をすると 中身が $i-1$ 行目と $i$ 行目の情報が混在した状態になり、正確に求まらない。
まず、雑草は高さ順に整列してindexも振りなおす。
小さい方または大きい方から抜いていけばいいのかな、とも思うが、以下のような場合は中途半端な1本を抜くのが最適となる。
K=2 v A 2 3 6 13 14 先頭や末尾の2本を抜くとBさんの操作回数は2回だが、 "6"の1本を抜いても2回で済み、これがAさんの抜く本数としては最小
そのため貪欲は難しそうで、DPを組んでみたくなる。
しかし、以下のようなDPでは、$O(NK)$ になりダメ。
ここで、雑草の高さは半分ずつになっていくので、Bさんの操作回数は多くても $\log_2{A_{max}}=30$ 回程度しかいかないことがポイントとなる。
$j$ の持つ意味とそこに入る値を逆にすればよい。
こうすれば、$O(N\log{A_{max}})$ で間に合う。
初期値は、全てを $0$ で埋めておく。
$DP[i][j]$ の更新は、以下のようになる。
s i A ... 11 10 9 7 6 5 DP : j-1 ☆ ☆: AiをBさんが抜く場合に参照する箇所 j ★ ★: AiをAさんが抜く場合に参照する箇所 :
$A_1~A_s$ の草を(Aさんの抜く本数を最小化しつつ)抜ききった際、高さが $A_s$ 以下のどこかを境として、それより上の草は全て抜かれ、下の草は全て残っているはず。
境が $A_s$ ぴったりにならないのは、Bさんが草 $s$ を抜くための操作の余波でそれより小さい何本か(上図で $9,7,6$ など)が抜かれる可能性があるためだが、 逆に言うと余波が届くのは $\frac{A_s}{2}$ の手前までなので、高さが $\frac{A_s}{2}$ 以下の草は草 $i$ を含め絶対に残っている。
(Aさんが手を加えないまま)次のBさんの操作で最大 $H$ になる草の高さは、$2A_i$ 未満 $A_i$ 以上となる。
この操作では、高さ $A_i$ の草は必ず抜かれる。
$DP[s][j-1]$ の状態からAさんは1本も草を抜かなくても、必ずちょうどあと1回のBさんの操作で、$A_1~A_i$ までを抜かれた状態にできる。