競技プログラミング用 知識集積所
ABC424D - 2x2 Erasing 2
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 貪欲法（アルゴリズム系）※ （不完全なもの）
- 深さ優先探索※
考え方
サイズが最大7x7と小さいが、最大100問出されるので、1問あたり2x10^6回くらいの計算で処理する必要がある。
単純なbit全探索とかでやると、端のマスを候補から除外するとしても間に合わない。
単純なbit全探索とかでやると、端のマスを候補から除外するとしても間に合わない。
そこで、貪欲法※でうまくいかないか考えてみる。
左上から右方向にチェックしていくとして、黒い2x2を見つけたら、そのうちどれかを白くする。
このとき、左上を塗るのは左下の下位互換、右上を塗るのは右下の下位互換である。
しかし、左下が右下の下位互換かと言えばそうでもない。
左上から右方向にチェックしていくとして、黒い2x2を見つけたら、そのうちどれかを白くする。
このとき、左上を塗るのは左下の下位互換、右上を塗るのは右下の下位互換である。
しかし、左下が右下の下位互換かと言えばそうでもない。
反例 □■■ ■■■ ■■□
そこで、2択だけ消すことにして、残る2択は深さ優先探索※で処理しながら最小値を探す。
この際、「左下を白にする→木を彫り進める→戻ってきたら左下を黒に戻す→右下を白にする→木を彫り進める→戻ってきたら右下を黒に戻す」という形にすると、計算を毎回1からやらなくて済むので高速化できる。
この際、「左下を白にする→木を彫り進める→戻ってきたら左下を黒に戻す→右下を白にする→木を彫り進める→戻ってきたら右下を黒に戻す」という形にすると、計算を毎回1からやらなくて済むので高速化できる。
問題は計算量の見積もり。
特に7x7の場合に2x10^6回で収まるかの判断が重要。
特に7x7の場合に2x10^6回で収まるかの判断が重要。
まず、この方針では1段目を自分で塗ることは絶対にない。
「2段目と3段目」「4段目と5段目」「6段目と7段目」をそれぞれペアにして考える。
同じ縦列のマスをペアにして考えると、上下両方を自分で塗ることは絶対にない。
さらに、7列全て上下どちらかを塗るということにも絶対にならない。
ということは、各2x7の長方形内で、自分で塗るのは最大で6マスである。
つまり全体で最大18マスまでしか自分で塗らない。
木の高さが最大18で、各所で2択にしかならないのだから、探索は2^18=262144通り以下で済む。
定数倍次第で少し怖いが、実際は18マスも自分で塗るパターンはほぼ起こらないので、よほど下手な実装をしなければ十分間に合う。
「2段目と3段目」「4段目と5段目」「6段目と7段目」をそれぞれペアにして考える。
同じ縦列のマスをペアにして考えると、上下両方を自分で塗ることは絶対にない。
さらに、7列全て上下どちらかを塗るということにも絶対にならない。
ということは、各2x7の長方形内で、自分で塗るのは最大で6マスである。
つまり全体で最大18マスまでしか自分で塗らない。
木の高さが最大18で、各所で2択にしかならないのだから、探索は2^18=262144通り以下で済む。
定数倍次第で少し怖いが、実際は18マスも自分で塗るパターンはほぼ起こらないので、よほど下手な実装をしなければ十分間に合う。
解答例
注意点
解法によっては幅や高さが2の場合がコーナーケースになるので注意。
端の部分を白く塗る候補から外す解法だと、幅2の場合や高さ2の場合に黒マス2x2がどうやっても消せなくなる。
3マス以上ない場合はどちらかの列を候補に残しておくこと。
（そういう解法で間に合うかものがあるかどうかは不明）
3マス以上ない場合はどちらかの列を候補に残しておくこと。
（そういう解法で間に合うかものがあるかどうかは不明）
