※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー解説問161」の編集履歴(バックアップ)一覧に戻る
プロジェクトオイラー解説問161」を以下のとおり復元します。
*Problem 161 「トリオミノ」 †
----
*問題

トリオミノとは3つの正方形を辺で繋げたものである. 以下は2つの基本形.
#ref(p_161_1.gif)

すべての方向を可能性に入れると, 以下の6つがある.
#ref(p_161_3.gif)

n x m が3で割り切れるならば, どのn x m の格子もトリオミノによって埋めることができる. 
反転, 回転によって得られる埋めかたを別の埋め方とすると, 2 x 9 の格子では41通りの埋め方がある.
9*12の格子では何通りの埋め方があるか。
----
解法
只今解説準備中。
左下から右上へ図のような順番で隙間なくみっちり敷き詰めていき動的計画法で解きます。




あるマスにピースを置くとき重要となるのは、今までどんなピースをどんな風に置いたかは意味を持たず、おかれたピースの全体の形だけです。

よってピースのおかれた左下から右上へ1マスに1ビット割り当てると9*12=108ビットでおかれたおかれてないを管理できます。
おかれたおかれてないを128ビット整数型で管理しこれを主キーとしこの主キーに対応する組み合わせ数を計算していきます。

ここでよく見てみると、今検証中の行より下はどの組み合わせでも隙間なくすべて埋まっています。
とすると、検証中の行より下を消去しても組み合わせの計算に影響を与えないことがわかります。
これを行うには行の右端に到達するたびに主キーの値を9ビット右シフトすることで簡単に消去が行えます。

左下から埋めたとき、今作業中の行より下は考慮する意味がなく、1*3の縦棒より大きなものはありません。
よってある行rを計算するとき3行*9列だけを主キーの値とすればよいと判明します。

復元してよろしいですか?