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

プロジェクトオイラー解説問161 - (2013/12/15 (日) 16:59:10) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

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




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

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

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

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

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




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

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

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

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