CEOI 2021 Day1 - L-triominoes
概要
Author : Cyanmond
解法
小課題 1
$ W \leq 13, H \leq 1000という制約から、状態数$ \Theta(H2^W)の bitDP が想像つく。
$ \mathrm{dp}(i, s)を "$ i行目まで考えて、$ i-1行目までは全て埋まっていて$ i行目の状態が$ sである状態が可能かどうかの真偽値" などと定義できる。ここでタイルをおけないマスは既に埋まっていると考える。
各キーからの遷移先は dfs 的に求められるが、遷移先の数の抑えは難しい。
簡単な抑えで$ O(2^{\frac{W}{2}})などとなる。
$ sの立っている bit 数に指数の肩が依存するので、多分全ての$ sを考えたときの総和は別で抑えられる... が、立っている bit の位置などによっても変わりそうなので難しそう。
実際の速度は十分である。ただ毎回遷移先を計算するのは速度が心もとないので、$ 2^W通りの状態それぞれに大して遷移先を初めに列挙しておくのがよい。
$ i+1行目に既に埋まっているマスがあるとき、$ \mathrm{dp}(i, s)から$ \mathrm{dp}(i + 1, t)の遷移は ($ tを整数として見た場合) 既に埋まっているマスの bit が立っていなければならない。この処理は、もともと列挙された遷移先それぞれについて定数回の bit 演算だけで行うことができるので問題ない。
小課題 2
$ H, W \geq 2より、$ H \times Wが$ 6の倍数の時は明らかに可能である。また、$ H \times Wが$ 3の倍数でない場合は明らかに不可能なこともわかる。
実は$ H \times Wが$ 6の倍数であることはは必要条件ではない。
実際に小課題 1 のコードを用いて実験してみると、$ \min(H, W) \geq 5 かつ$ H \times Wが奇数の$ 3の倍数である場合、実は可能であることがわかる。
美しい証明ではないように思えるが、とりあえず小さいケースについて解ければ後は帰納法が回るので証明できる。
よって答えは、以下のいずれかを満たすかどうかで決まる。
$ H \times Wが$ 6の倍数
$ H \times Wが$ 3の倍数かつ$ \min(H, W) \geq 5
小課題 6
きれいな (一般の W に適用可能な) 証明があるとうれしいです
小課題 1 の方針をそのまま適用しようとすると$ \Omega(2^WH)かかって明らかに間に合わない。
$ K \leq 250なので、実際にはもともと埋まっているマスを全く含まない行が大半を占めることがわかる。実はこれを用いて高速化できる。
$ i行目以降にマスが存在しない時、$ \mathrm{dp}(i), \mathrm{dp}(i + 1), \cdotsには規則性がある。例えば$ W=13のとき、これは最悪でも$ 8個目から周期$ 3のループに入る。
これの証明もきれいなものではないが、各$ sについて$ \mathrm{dp}(i, s)のみを true にした状態から遷移を始めると必ず周期$ 3のループに入ることが観察できる。それぞれの$ sについて同じ周期でループしていれば任意の状態から始めてループに入ることがいえる。
この実験も小課題 1 のコードを大体流用できる。
$ W < 13のときもそれぞれ同様に実験してみると、$ W \leq 13のとき常に$ 8個以下で周期$ 3以下のループに入ることを実験によって観察できる。
実験結果からは、$ W \bmod 3に周期や周期に入るまでの個数が依存しているように見える。ここはちゃんと検証できていない。
そのため$ H回 DP の遷移をする必要はなく、周期に入ったらサボってしまえばよい。