問題概要 #
$H \times W$のフィールドの各マスに、色a-zである石を置いている。次の動きを繰り返せるだけ繰り返した時、石は何個残る？
- 各行について、全てが同じ色ならば、その石全てに印をつける。
- 各列について、全てが同じ色ならば、その石全てに印をつける。
- 印がついた石をすべて取り除く。
制約: $H, W \in [1, 2000]$
考え方 #
愚直にシミュレーションしかなさそう。各行を見るたびに$O(x)$かかるなら、全体で$I((H + W)^2 x)$かかる。$o(x)$は可能ならば定数レベルに抑えたい。(毎回の操作では最悪$O(H + W)$の行と列についての操作。全体ではたかだか$H + W$回までしか使われない。同時に達成されることはないが、かなり大きい上限値。実際はずっと小さい。)
ここで、色がたかだか26色しかないことを見る。各行と列ごとにcolor[i] := 色iの石の個数とすれば、各行や列を取り除くときは1減らす、各行や列が同じ色かどうかの判定も26回走査すればよいので、$o(x)$は26という定数と考えていい。
後は実装すればいい。
実装上のやり方 #
ステップ1とステップ2は実質同時である(取り除くことは同時)ので、実装するときも指示通り、
- ステップ1で印をつける(印をつける代わりに行iをマークする)
- ステップ2でも印をつける(印をつける代わりに行jをマークする)
- 印がついてるところを取り除く
- 何色を取り除くのかに関しても、ステップ1,2の時点でメモしておく。この行or列はどうせ同じだからあとで見ればいい、はミスのもと！(今回の場合実際に取り除かれた石は以後の判定に影響しないので実際にWAを産む。愚直に実装してくれ)
- 終了条件判定(行と列の残存がいずれかが1になる、取り除けなかったなど)
で行うべき。
追記 #
毎回26色を見なくても済むやり方はある。('a', 4), ('b', 2), ('f', 1)みたいに保持すること。
そして例えばここからfを取り除くと0になるので、('a', 4), ('b', 2)に簡約すればよい。
これも後で実装する。