「プロジェクトオイラー解説問161」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー解説問161 - (2013/12/15 (日) 17:54:18) のソース

*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の格子では何通りの埋め方があるか。
----
解法
只今解説準備中。
左下から右上へ図のような順番で隙間なくみっちり敷き詰めていき動的計画法で解きます。


詰めていくときピースのおかれた状態を管理するための記法が必要となります。
マス目に１～108まで図のように番号を割り振ります。
#ref(e161_2.gif)
これを１２８ビット整数型で管理しこれを主キーとしこの主キーに対応する組み合わせ数を計算していきます。
128ビットの右１ビット目が1番のマス目に対応し。
右２ビット目が２番のマス目に対応し１０８番目のマスが１０８ビット目に対応します。
あるマスにピースのブロックが占めていれば1で占めていなければ0と対応させます。






具体的な番号からビットへの変換は下記の通りです。
#ref(e161_3.gif)
この図を現す状態は 
 マス目　 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
 ビット列  1  1  1  0  0  0  1  0  1  1  1  1  1  1  1  1  1  1  1 1 1 1 1 1 1 1 1 1
 できちんと書いて図と対応するビット列は
 1110001011111111111111111111 
 となります。







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

よってピースのおかれた左下から右上へ１マスに１ビット割り当てると9*12＝108ビットでおかれたおかれてないで状態を管理できます。









次にピースは数字で表現でき、ピースを置くことはビット演算で変化を計算できます。
ピースを数字で表したもの。
#ref(e161_6.gif)








ピースのおき方
６種類の回転も反転も不可能な別種のピースが６種類あると考えます。
ピースを置くとき、ピースの一番下の一番左の部分を置けないか検討します。
#ref(e161_7.gif)










ピースを置くこととビット演算の対応
#ref(e161_8.gif)






ピースを置けない場合。
#ref(e161_9.gif)
こういう場合はピースを置こうとしているマス目の行と列から判断して計算から排除します。








ピースを置けない場合その２
#ref(e161_9.gif)
この場合も計算から排除します。






ピースを置けない場合その３










***具体的な計算手順
あるマス目まで隙間なく埋めていった場合のビット列の集合を
[(B1,組み合わせ数1),(B2,組み合わせ数２),,,,(Bn,組み合わせ数ｎ)]
とします。
今ｍ個目のマス目にピースを置こうとした結果、ｍマス目にピースを置いたことを表すためにＢ1にビット演算を施して
B1→[B11,B12,B13,,,B16]などのように新しい番号の集合が出てきます。
B2→[B21,B22,,,,,,,B26]
,,,
Bn→[Bn1,Bn2,,,,,,,Bn6]
同じビット列になったものを統合して組み合わせ数を統合していきます。


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

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