競技プログラミング用 知識集積所
ABC425D - Ulam-Warburton Automaton
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
ただし、01最良優先探索※に近いことをするので、その知識があると楽かも。
考え方
問題に書いてある通りにやる愚直解に1つの工夫を混ぜるだけでいける。
完全に問題通りにできない理由は、最大30万マスを10^100回ずつ調べるのは明らかに間に合わないから、というだけである。
しかし、今回新たに塗る可能性があるのは、前回（1回目なら初期状態）に黒く塗った隣のマスだけである。
したがって、塗るべきマスを調査しながら同時に今回黒く塗ったマスの隣のマス一覧を用意し、次の調査はそのリストにあるマスだけ調べればよい。
しかし、今回新たに塗る可能性があるのは、前回（1回目なら初期状態）に黒く塗った隣のマスだけである。
したがって、塗るべきマスを調査しながら同時に今回黒く塗ったマスの隣のマス一覧を用意し、次の調査はそのリストにあるマスだけ調べればよい。
すると、あるマスが黒く塗られるのは多くとも1回だけ、つまりどう転んでもマス数の数倍くらいの調査回数で終わる。
調査回数のループ回数を10^100に設定すると中身がなくてもそれだけでTLEするので、「次の調査対象がない」となった時点で調査を打ち切ってよい。
調査回数のループ回数を10^100に設定すると中身がなくてもそれだけでTLEするので、「次の調査対象がない」となった時点で調査を打ち切ってよい。
解答例
注意点
調査しながら黒マスで塗らないようにする
周囲の黒マスの数を数えて1つだった場合に、即塗ってはいけない。
今それを塗ったせいで、次のマスのチェックに影響してしまうからである。
必ず、1つであったマスの位置を記録するだけにとどめ、全ての調査が終わった後でまとめて塗ること。
今それを塗ったせいで、次のマスのチェックに影響してしまうからである。
必ず、1つであったマスの位置を記録するだけにとどめ、全ての調査が終わった後でまとめて塗ること。
