日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問１１６「赤タイル, 緑タイル, あるいは青タイル」
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える.
もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.
もし緑のタイルを選んだ場合は, 3 通りである.
もし青のタイルを選んだ場合は, 2 通りである.
複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.
50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか.
ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.
注: この問題は Problem 117 に関連する
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def e(m, n, d):
if n not in d:
d[n] = e(m, n-1, d)+e(m, n-m, d)
return d[n]
def dd(n):
d = {0:0, n:2}
for i in xrange(1, n): d[i] = 1
return d
def f(n, t):
s = 0
for m in t:
d = dd(m)
s += e(m, n, d) -1
return s
n = 50
t = 2,3,4
s = f(n, t)
print s
前回の解法は、問１１４、１１５を参考に続けて考えたため、終端のブロックが1個かm個かによって関数end1()とendm()として関数を分けていましたが、1個ブロックもm個ブロックもその後にどちらを置いてもいいので本質的に違いはありません。
そこで、
関数end1()とendm()を統合して、終端のブロック数に関係しない関数e()として別解を作成しました。
１．関数e(m, n, d)
・全体がn個で、1個とm個のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書（連想配列）です。
1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
全体がn-1個の後に1個ブロックを1つ置く場合と
全体がn-m個の後にm個ブロックを1つ置く場合の２系統あるので、この和になります。
２．関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
1個ブロックとn個ブロックの両方があることを考慮します。
・具体的には以下のとおりです。
キー=nの場合、1個ブロックn個連続またはm個ブロック1個の場合なのでパターン数は2、
0<キー<nの場合、1ブロックが連続しているパターンだけなのでパターン数は1、
キー=0の場合、パターン数は0となります。
３．関数f(n, t)
・全体のブロック数nのときの求めるパターン数を返します。
ただし、引数tは1個ブロックとともに使用するm個ブロックのmに相当する数のタプルです。
本問では赤(長さ 2), 緑(長さ 3), 青(長さ 4)を使用するので、t=2,3,4となります。
・ループ変数mとして引数tから値を１つずつ取り出します。
・パターン数辞書をdとして、関数dd()で初期化した状態で準備します。
・mの値ごとに関数e()でパターン数を求め、
全部1個ブロックの場合は数えないのでそのパターン数1を引きます。
・上記を使用するm個ブロックの分だけ累積します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
20492570929
