nkmrtty’s blog

https://nkmrtty.com/

Lights Out

ライツアウト自体はどういうものか知ってはいたんだけど、アルゴリズムがさっぱりで悔しかったので勉強した。

問題設定としては以下の通り。

N行M列に並べられたN×M個のライトがあり、それぞれのライトはONとOFFの2つの状態を持つ。 ライトをタップすることでONとOFFを切り替えられるが、その時、そのライトの上下左右のライトのONとOFFも同時に切り替わる。 与えられた初期状態から何回かライトをタップしてすべてのライトを消すための手順を求めよ。  
[入力形式]
N M
(ライトの初期状態:0がON/.がOFF)  
[入力例]
5 5
.....
.....
..0..
.....
.....

求められる答えとしては最小のタップ数であったり、すべての手順数であったり。

まず、以下のことが直感的にわかる。

  • 同じライトを偶数回タップしても結果は同じ(各ライトはタップするかしないかの2択)
  • ライトを押す順番が変わっても結果は同じ

つまり、単純な総当りだと {O(2^{N\times M})} の時間計算量になる。

総当りのときのPythonコードはこちら。盤のサイズでON/OFF用のマスクビット列が決まるので、ON/OFFの処理を高速化できる余地はあるけどタダのテクニックなので割愛。

Lights Out

これをどうにか高速化できないかという話なんだけど、そんなん自分の頭じゃわかんないですってやり方だった。
具体的な内容については参考サイトを見てほしいんですが、1行目のどのライトをタップするかが決まればすべてのライトを消せるかどうかがわかると言うもの(わからん)。
直感的には1行目のライトをOFFにするには、1行目のONのライトの下にある2行目のライトをタップしないといけない、2行目のライトをOFFにするには.....、という操作をしないといけないのでという感じ。
これで時間計算量は1行目のライトの組み合わせと2行目以降で上段がONのライトの探索なので {O(MN2^{M})}になるのかな。

コードはこちら。めっちゃ早い。

Fast Lights Out

おわり。

参考サイト