F - Hanjo 2 Editorial by kyopro_friends
左から \(i\) 番目、上から \(j\) 番目のマスをマス \((i,j)\) と呼ぶことにします。
\(HW\) が十分小さい場合は ABC196D『Hanjo』と同様に全探索することで答えを求めることができます。どうすればより効率に求めることができるでしょうか?
\(O(2^H HW) 解法\)
全探索を行う際、「未確定のうち最も左、最も上のマス」から順に決めることを考えます。
(探索途中の図の例)
このとき、いま決めようとしているマスより上および左にあるマスは全てタイルに被われておりしており、1列以上右にあるマスは被われていません。
(黄色:必ず被われている、赤:被われていたりいなかったりする、白:絶対に被われていない)
上図の赤色の部分のみが今後の敷き詰め方に影響する本質的な部分なので
\(dp[i][j][S]\) = マス \((i,j)\) 以前のマスは全て被われており、\(H\) 個のマス \((i,j+1), \ldots,(i,H),(i+1,1),\ldots,(i+1,j)\) のうちすでに被われているマスの集合が \(S\)
というDPを考えることができます。これで \(O(HW2^H)\) で解くことができます。
\(O(4^H W)\) 解法
上では \(1\) マスずつ決めましたが、1列ずつ決めることを考えてみましょう。
この場合、次のようなDPを考えることができます。
\(dp[i][S]\) = \(i\) 列目より前のマスは全て被われており、\(H\) 個のマス \((i,1),\ldots,(i,H)\) のうちすでに被われているマスの集合が \(S\)
詳細は省略しますが、このDPでは \(dp[i][S]\) から\(dp[i+1][T]\) への遷移を全ての \((S,T)\) の組に対して行う必要があるため、計算量は \(O(4^H W)\) となります。
(少し工夫をすると \(O(3^H W)\) にもなります)
\(O(8^H \log W)\) 解法
先程述べたDPでは計算量が悪化してしまいましたが、実はこのDPを高速化することで \(O(8^H \log W)\) となり、元の問題を解くことができます。
\(dp[i][*]\) から \(dp[i+1][*]\) への遷移が \(i\) に依存しておらず、かつ、線形な式になっています。より正確には、\((S,T)\) のみに依存するある定数 \(c(S,T)\) が存在して
\(dp[i+1][T]=\sum_S c(T,S) dp[i][S]\)
と表せます。
このようなDPは一般に行列累乗により高速化することができます。
具体的には \(c(T,S)\)を \((T,S)\) 成分とした行列を \(W\) 乗したものに、縦ベクトル \(dp[0][*]\)を右から掛けて得られる縦ベクトルが \(dp[W][*]\) になります。
行列サイズは \(2^H \times 2^H\) であるので、これの \(W\) 乗は、繰り返し二乗法により \(O(8^H \log W)\) で求めることができます。
\(c(T,S)\) は \(O(4^H H)\) で容易に構築することができるため、以上により問題が解けました。
なお、行列累乗でDPを高速化する問題の例としては EDPC R 『Walk』 などがあります。
posted:
last update: