競技プログラミング用 知識集積所
ABC407D - Domino Covering XOR
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
制限を見るとHW<=20で、全探索（未作成）でなんとかなりそうな気がするので、ひとまず妥当性を考えてみる。
まず、各マスについて、「新たには置かない」「右のマスにまたがるように置く」「下のマスにまたがるように置く」の三択。
で、右端や下端は選択肢が減ると考えると、最も正方形に近い最大盤面である4*5の場合で、3^12*2^7=68024448通り。
これに、毎回「ドミノを全部配置できるか確認して、実際に配置してxor取って……」をやると間に合わない。
まず、各マスについて、「新たには置かない」「右のマスにまたがるように置く」「下のマスにまたがるように置く」の三択。
で、右端や下端は選択肢が減ると考えると、最も正方形に近い最大盤面である4*5の場合で、3^12*2^7=68024448通り。
これに、毎回「ドミノを全部配置できるか確認して、実際に配置してxor取って……」をやると間に合わない。
そこで、「右のマスにまたがるように置く」をした場合には右のマス、「下のマスにまたがるように置く」をした場合には下のマスで選択肢を考えないようにして高速化したい。
また、xorを計算するのも毎回新たに計算し直したくない。
そうすると、深さ優先探索（未作成）の出番となる。
この2つの工夫により、68024448よりそこそこ少ない計算量で済みそうなので、間に合うことが期待される。
また、xorを計算するのも毎回新たに計算し直したくない。
そうすると、深さ優先探索（未作成）の出番となる。
この2つの工夫により、68024448よりそこそこ少ない計算量で済みそうなので、間に合うことが期待される。
そこまでわかれば、あとは実装が重いだけ。
