PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 215 / 亀裂のない壁

2x1 と 3x1 のレンガを使って壁を作る。 ただし,水平方向に隣接したレンガ間の隙間が上下の層にまたがってはならない。つまり,伝播亀裂(running crack)がないようにする。

たとえば下図の 9x3 の壁は条件をみたしていない。赤線が伝播亀裂だからである。

f:id:variee:20180610143040g:plain

9x3 の亀裂のない壁は8通りある。これを W(9, 3)=8 と表す。
W(32, 10) を計算せよ。

本家:Problem 215 - Project Euler
日本語訳:Problem 215 - PukiWiki


第164問と同じような方法で解きました。

variee.hatenadiary.com

レンガの数の組わせは 2x+3y=32 の非負整数解として求められます。6組ありました。

 (x, y) = (1, 10),\, (4, 8),\, (7, 6),\, (10, 4),\, (13, 2),\, (16, 0)


この後の手順は次のとおりです。第164問を解いたときとくらべるとだいぶ楽でした。

  1. Permutations で2を x 個,3を y 個並べた順列を作る
  2. Accumulate で累積和を計算。レンガの区切り位置を並べた順列を作る。計算量を減らすため,末尾の32を削除
  3. 「a の上に b をおける」を「a->b」で表してグラフにする
  4. 隣接行列を計算。その9乗の成分の総和が答え