へやわけDP
探索方法
今までは、「角のマスから1マスずつ黒白を決め、分断したら別のパターン」という再帰でプログラムを書いて、特定のサイズのへやに、へやわけのルールを満たしたまま黒マスを詰める方法を探索していました。
「ある行をどのように塗れるか」は「その直前の行がどのように塗られているか」のみに依存します。なので、(何列目まで見たか,累計何マス塗ったか,直前の行の塗られ方はどうなっているか)の3状態を持ったDPで求めることが出来ます。
（詳細は次ツイート）
5×nならある行の塗り方は(φ,1,2,3,4,5,13,14,15,24,25,35,135)の13通りですが、2マス以上塗る場合は、それらが同じ連結成分に属しているかで場合分けしておく必要があり(分断禁)、2マスで各2通り、3マスは5通りの計23通りになります。
角のへやの探索をします。上と左に壁があるものとして考えます。
A.一行ごとの塗り方（以下「状態」と呼びます）のリストアップ
まず、一行ごとに、横nマスに入る黒マスと白マスのパターンをリストアップします。黒マスは隣接しません。黒を1,白を0とし、1,0,1,0,0,0,1などと付けます。 そして、黒マスどうしの斜めの連なりに注目し、どの黒マスがどの連なりに属するかの番号も付けます。
番号は左から振ることにします。横7マスなら、登場する最大の数字は4です。
さらに場合分けをします。連なりのうち、壁にアースされているもの（連なりの中に、壁に接している黒マスがあるもの）を全て1とします。アースされていない連なりには改めて2以上の番号を振っていきます。
1,0,2,0,0,0,2,2,0,1,0,0,0,1,2,0,3,0,0,0,3は全て別々の状態です。 今回は左端に壁があるので、左端に黒マスがあるとき、その黒マスの番号は確実に1です。それ以外は状態リストから削除します。
B.遷移行列
状態ごとに、その下の行に入りうる状態は限られます。どの状態の下にどの状態が入るか、その一覧表が遷移行列です。
状態ごとに、その下の行に黒マスを並べ、下の行がどの状態になるかを調べます。
下の行の黒マスの、左上や右上にどの連なりの黒マスがあるのかを見つつ、番号を振っていきます。
番号を最後まで振ってから、小さい順に並べ替えています。
黒マスの左上か右上が1なら、その黒マスもやはり1です。
左上と右上の番号が同じなら(その時に限り)分断禁に違反します。
C.状態の整理
状態ごとの、黒マスの個数と、最上列に入るかどうかのリストを作ります。
D.DP
(現在の行、今まで詰めた黒マスの個数、現在の最下列の状態の番号)の3状態でDPします。
先ほどの遷移行列を用いて、状態ごとに、最下列のさらに下に付け足せるか判定します。
全状態が終了したら、次の行に進み、最後の行で目的の黒マスの個数に達しているものを足し、解の総数を求めます。
また、解の具体的な構成も出来ます。最下列から黒マスの数を引いて行って上の列へと戻っていき、「現在の最下列の状態の番号」を拾っていき、すべてつなげれば完成です。
角の1x5から100x5までの解の総数を数え上げるのに数分かかります。