ABC 401-500/ABC460D - Repeatedly Repainting - 競技プログラミング用 知識集積所【6/6更新】

---

問題

ABC460D

必要知識

B以下レベルの内容は省略

• 考察問題
• 幅優先探索※

考え方

10^100ターンのシミュレーションなどできるわけがないので、考察問題として考える。
隣接2マスの関係が重要なので、白白、白黒、黒黒の3つの隣接パターンを考える。

白黒の場合。
白だったマスは次ターン黒になり、黒だったマスは白になる。
従って、次ターンも同様に繰り返され、2ターン後に元に戻る。

白白の場合。
どちらかのとなりに黒が来るまでは、何も起こらない。
少なくとも一方が黒になった時点で、白黒または黒黒に合流する。

黒黒の場合。
最初に両方白になり、後は白白に合流する。
特に、両方のマスが白に隣接していた場合は、そちらとの白黒パターンにより2ターン後に元に戻る。

以上を考えると、「自身も黒で周囲8近傍にも黒しかない」というマスがなければ、

• 各マス初めて黒になるのが何ターン目かを幅優先探索※で求める
• 初めて黒になるのが偶数ターン目なら、それ以降の偶数ターンで黒、奇数ターンで白
• 初めて黒になるのが奇数ターン目なら、それ以降の奇数ターンで黒、偶数ターンで白

として、任意の大きなターン数について答えを出せることになる。

あとは「自身も黒で周囲8近傍にも黒しかない」というパターンがあるケースが問題だが、この形はターン数経過で生成されることがない。
なぜなら、そこが黒く塗られたということは隣に前ターン黒があったということであり、そのマスは今は白に変化していなければおかしいから。

ということは、

• 1ターンはシミュレーションする
• そこから10^100-1ターン後の様子を先ほどの方法で求める

とすればよい。

解答例

解答例

注意点

別解