プロジェクトオイラー 問１１５

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１５「ブロックの組み合わせ方の数え上げ その2」
注意: これは Problem 114 をより難しくした問題である.

長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする.
例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である.
m = 3 の時, n = 30 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
同様に, m = 10 では F(10, 56) = 880711, F(10, 57) = 1148904 であることがわかり, つまり n = 57 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
m = 50 のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の n の値を求めよ.






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def endb(m, n, bd, rd):
	if n not in bd:
		bd[n] = endb(m, n-1, bd, rd) + endr(m, n-1, bd, rd)
	return bd[n]

def endr(m, n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(m, i,bd,rd) for i in xrange(n-m+1)])
	return rd[n]

def f(m, k):
	bd = {0:0, 1:1}
	rd = {m:1}
	for i in xrange(m): rd[i] = 0

	n = 0
	while endb(m, n, bd, rd)+endr(m, n, bd, rd)<=k: n += 1
	return n


m=50
k = 1000000
n = f(m, k)
print n

問１１４との違いは、以下の２点です。
a.赤ブロックの最小個数が3個固定だったのがm個になったこと。
b.全体の長さを固定にしてパターン数を求めていたことに対して
　パターン数の下限値から全体の長さの最小値を求めること。

そこで、問１１４で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()、
同赤ブロックの関数endr()を上記aに対応できるように改良し、
求める値を返すf()も上記bに合わせて改良します。

１．関数endb(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が黒ブロックのパターン数を返します。
・問１１４の関数endb()に引数mを追加し、呼び出す関数endr()も問１１４のものに引数mを追加するので、それに合わせました。
・bdは終端が黒で全体がn個の場合のパターン数の辞書（連想配列）です。
　rdは終端が赤で全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
　全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

２．関数endr(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が赤ブロックのパターン数を返します。
・問１１４の関数endb()に引数mを追加し、固定値2の部分をm-1に改良しました。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の２つの場合があります。
　a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
　b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
　　この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

　aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
　bの場合はループ変数iを0からnのm個手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

３．関数f(m, k)
・赤ブロックの最小個数mで問題の条件に合うパターン数が下限値k個を超える、全体の長さの最小値を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さが、黒は1個で、赤はm個なので、黒赤それぞれでその値未満のパターン数は0で、その値で1パターンが初期値になります。
　なお、辞書rdには、キーmのとき1を固定で設定し、m未満のキーのときはfor文で回して0を設定します。
・黒赤それぞれのが終端となるパターン数の和が全パターン数です。
　全体の長さnは0から始めて1ずつ増加させながら全パターン数を計算していき、
　この全パターン数が下限値kを超えたら、そのときのnを返します。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
168