「プロジェクトオイラー解説問161」の編集履歴（バックアップ）一覧に戻る
プロジェクトオイラー解説問161 - (2013/12/15 (日) 17:38:55) の編集履歴(バックアップ)
Problem 161 「トリオミノ」 †
問題
トリオミノとは3つの正方形を辺で繋げたものである. 以下は2つの基本形.
すべての方向を可能性に入れると, 以下の6つがある.
n x m が3で割り切れるならば, どのn x m の格子もトリオミノによって埋めることができる.
反転, 回転によって得られる埋めかたを別の埋め方とすると, 2 x 9 の格子では41通りの埋め方がある.
9*12の格子では何通りの埋め方があるか。
解法
只今解説準備中。
左下から右上へ図のような順番で隙間なくみっちり敷き詰めていき動的計画法で解きます。
まずピースのおかれた状態を管理するための記法が必要となります。
マス目に１～108まで図のように番号を割り振ります。
これを１２８ビット整数型で管理しこれを主キーとしこの主キーに対応する組み合わせ数を計算していきます。
128ビットの右１ビット目が1番のマス目に対応し。
右２ビット目が２番のマス目に対応し１０８番目のマスが１０８ビット目に対応します。
あるマスにピースのブロックが占めていれば1で占めていなければ0と対応させます。
具体的な番号からビットへの変換は下記の通りです。
この図を現す状態は
マス目 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
となります。
あるマスにピースを置くとき重要となるのは、今までどんなピースをどんな風に置いたかは意味を持たず、おかれたピースの全体の形だけが重要です。
よってピースのおかれた左下から右上へ１マスに１ビット割り当てると9*12＝108ビットでおかれたおかれてないで状態を管理できます。
ここでよく見てみると、今検証中の行より下はどの組み合わせでも隙間なくすべて埋まっています。
とすると、検証中の行より下を消去しても組み合わせの計算に影響を与えないことがわかります。
これを行うには行の右端に到達するたびに主キーの値を９ビット右シフトすることで簡単に消去が行えます。
左下から埋めたとき、今作業中の行より下は考慮する意味がなく、1*3の縦棒より行を横断するものはありません。
よってある行ｒを計算するとき３行*9列だけを主キーの値とすればよいと判明します。
ピースは数字で表現でき、ピースを置くことはビット演算で表示できます。
