AtCoder Beginner Contest 203（Sponsored by Panasonic）D,E,F問題メモ

AtCoder Beginner Contest 203（Sponsored by Panasonic）

D - Pond

• $N \times N$ のグリッド区画の各マスに、高さ $A_{i,j}$ が設定されている
• この中ではみ出さずにとれる $K \times K$ の区画のうち、その中央値が最小のものの値を求めよ
  • 偶数個の場合は、真ん中2個のうち小さい方を中央値とする
• $1 \le K \le N \le 800$
• $0 \le A_{i,j} \le 10^9$

ある集合の部分集合それぞれの中央値を直接求めるのはなかなか難しいが、 ある数 $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

• 二分探索で中央値 $m$ を仮定する
• $K \times K$ 区画を1つずつずらしながら「中央値は $m$ 以下か？」を調べる
  • 1個でも当てはまる区画があれば、答えは $m$ 以下
  • 1個も当てはまる区画が無ければ、答えは $m+1$ 以上

これで求まる。

中央値を調べるには、$N \times N$ 配列を{$m$ 以下=0, $m$ 超過=1} で変換した後、二次元累積和を使うと高速。

Pythonでは、scipy.signal.convolve2d という 二次元たたみ込みのできる関数があったのだが、普通に遅かった。
重みを変えたりできるので、中身は普通に毎回 $K \times K$ を計算してるのかな。

Python3

E - White Pawn

• $(0,0)～(2N,2N)$ の $(2N+1) \times (2N+1)$ のグリッド
• 白のポーンが最上段中央 $(0,N)$ に置かれている
• 黒のポーンが $M$ 個、それぞれ $(X_i,Y_i)$ に置かれている
• 白のポーンを以下のルールで1段ずつ下へ動かしていく
  • 自身の1つ下のマスに黒のポーンが無ければ、そこへ動かせる
  • 自身の左斜め下、または右斜め下のマスに黒のポーンがあれば、そこへ動かせる
  • それ以外へは動かせない
• この操作を最下段まで繰り返したとき、到達可能な列の個数を求めよ
• $1 \le N \le 10^9$
• $0 \le M \le 2 \times 10^5$

$N$ が馬鹿デカいが、黒ポーンが無い行は 白ポーンは下に移動するしかないので到達可能な列は変わらない。

調べるのは黒ポーンのある行だけでよい。

また、その行でどの列に注目すればよいかに関しても、

• (1) 黒ポーンの無い列は、そこに到達可能かどうかは直前の行と一致
• 黒ポーンのある列は、直前の行で
  • (2) 右斜め上か左斜め上に到達可能なら、到達可能
  • (3) そうでないなら、到達不可能

i-1行  ... × ○ ○ ○ × ○ × ...  ○:到達可能な列  ×:不可能
              ▲ ▲    ▲ ▲         ▲:i行目の黒ポーン
 i 行  ... × ○ ○ ○ ○ × ×
 理由     (1)(2)(2)(1)(2)(3)(1)

直前の行と変化があるのは黒ポーンがある列のみで、他はそのまま引き継がれる。

「到達可能な列の集合」をsetなどで管理して、変化のある箇所のみ追加削除すればよい。
setに対する操作は全体で黒ポーンの個数 $O(M)$ になるので、十分間に合う。

実装の注意点として、

• 毎回setをコピーしてたら、終盤に到達可能な行がどんどん増えた場合、1回のコピーに時間がかかりすぎる
• そのため、1つのsetに破壊的に追加削除していくことになるが、その際、
  • ある行に存在する全ての黒ポーン列について追加削除を決定（実際の追加削除はしない）
  • 最後に一斉に追加削除を反映

としないと、1列ごとに追加削除をすると 中身が $i-1$ 行目と $i$ 行目の情報が混在した状態になり、正確に求まらない。

Python3

F - Weed

• 雑草が $N$ 本、各高さは $A_i$
• 以下の方法で全ての草を抜く
  • まずAさんが、好きな雑草を最大 $K$ 本まで選んで抜く
  • 次にBさんが、以下の操作を草が無くなるまで繰り返す
    • 残っている草の高さの最大値を $H$ とし、$\dfrac{H}{2}$ より大きい草を一斉に全て抜く
• Bさんの操作回数を最小化し、その中でAさんの草を抜く本数を最小化した時の、それぞれの値を求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$

まず、雑草は高さ順に整列してindexも振りなおす。

小さい方または大きい方から抜いていけばいいのかな、とも思うが、以下のような場合は中途半端な1本を抜くのが最適となる。

K=2       v
A   2  3  6  13  14

先頭や末尾の2本を抜くとBさんの操作回数は2回だが、
"6"の1本を抜いても2回で済み、これがAさんの抜く本数としては最小

そのため貪欲は難しそうで、DPを組んでみたくなる。

しかし、以下のようなDPでは、$O(NK)$ になりダメ。

• ダメな $DP[i][j]=$ 大きい方から $i$ 本目までの草を考え、Aさんが抜く本数が $j$ 本の時のBさんの操作回数の最小値

ここで、雑草の高さは半分ずつになっていくので、Bさんの操作回数は多くても $\log_2{A_{max}}=30$ 回程度しかいかないことがポイントとなる。
$j$ の持つ意味とそこに入る値を逆にすればよい。

• $DP[i][j]=$ 大きい方から $i$ 本目までの草を考え、Bさんの操作回数が $j$ 回の時の、Aさんの抜く本数の最小値

こうすれば、$O(N\log{A_{max}})$ で間に合う。

初期値は、全てを $0$ で埋めておく。

$DP[i][j]$ の更新は、以下のようになる。

• $j=0$ の時
  • 全て抜くしかないので、$DP[i][0]=i$

• $j \gt 0$ の時、以下の2つの小さい方となる
  • Aさんが抜く
    • $DP[i][j]=DP[i-1][j]+1$
  • Bさんが抜く
    • 高さが $2A_i$ 以上の草の中で一番小さいものを $A_s$ とする
      • 無ければ $s=0$ とする
    • $DP[i][j]=DP[s][j-1]$

            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$ までを抜かれた状態にできる。

Python3