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

プロジェクトオイラー(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

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

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

問１１４「ブロックの組み合わせ方の数え上げ その1」
長さ 7 ユニットからなる 1 列上に, 最低 3 ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). 
これを敷き詰める方法は, ちょうど 17 通りある.

50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか.

注意: 上の例では起こりえないが, 通常はブロックの大きさが複数混ざっていてもよい. 
例えば, 8 ユニットの長さの 1 列では, 赤(3), 黒(1), 赤(4) を使うことができる.







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






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

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

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

def f(n):
	bd, rd = {0:0, 1:1}, {0:0, 1:0, 2:0, 3:1}
	return endb(n, bd, rd) + endr(n, bd, rd)

n=50
s = f(n)
print s

黒ブロック（長さ１個）または赤ブロック（長さ３個以上）を１つずつ置いていって個数を数えます。
ただし、赤ブロックは連続では置けないので、
順番に並べていく中で終端が赤か黒かで別々の関数にします。

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

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

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

３．関数f(n)
・問題の条件で長さnで1列を敷き詰めるパターン数を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さは黒が1個で赤が3個なので、黒赤それぞれでこの値未満のパターン数は0で、その値で1パターンというのが初期値になります。
・黒赤それぞれのが終端となるパターン数の和が、求めるパターン数です。

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

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

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

問１１３「非はずみ数」
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 10¹⁰未満では277032個しかない.
googol数 (10¹⁰⁰) 未満ではずみ数でないものの数を答えよ.






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






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

def g(n):
	if n<2: return 1
	else: return n*g(n-1)

def C(n, m): return g(n)//g(m)//g(n-m)

def H(n, m): return C(n+m-1, m)

def f(n):
	c = H(10, n)-H(10, 0)
	for i in xrange(1, n+1): c += H(10,i)
	c -= 10*n
	return c

n=100
s = f(n)
print s

与えられた数が大きすぎるので桁数ごとに個数を計算して合計することにします。

まず増加数です。
これは0から9までの数字10種類からi個を選ぶ重複組合せです。
重複組合せの個数は公式から以下の通りです。
　₁₀H_i  ...(A)

図にすると、i桁の数字が以下のように表せます。「｜」は仕切り棒です。
連続する0｜連続する1|・・・｜連続する9
つまり、i個の要素を連続する0から連続する9までの10個の部分に分けることと同じです。
重複組合せでは、仕切り棒の本数も含めた格納場所に仕切り棒を入れることを考えます
10個の部分に分けるので必要な仕切り棒は10-1で9本必要です。
つまり、i+9個の格納場所に9本の仕切り棒を格納し、仕切り棒の間には連続する数字を格納することと同じです。
なお仕切り棒が隣合う場合、その間の連続する数字は１つも無いことになります。
重複組合せの個数の式と、重複を許さない組合せの個数の式との関係は以下の通りです。
　_nH_m = _n+m-1C_m  ...(B)
m-1は、仕切り棒の本数です。

それから、最上位が0の場合、桁数がiではなくなってしまいますが、
その個数は最上位1桁だけ0固定で他のi-1桁分は重複組合せなので、
　₁₀H_i-1
この分を差し引くと
　₁₀H_i - ₁₀H_i-1
これを全桁分、つまり桁数iを1からnまで動かして和をとると、
ほとんどの項が打ち消しあって以下だけが残ります。
　₁₀H_n - ₁₀H₀  ...(C)

次に減少数です。
減少数と同じように図にすると、i桁の数字が以下のように表せます。
連続する9｜連続する8|・・・｜連続する0
この重複組合せの個数は上記(A)と同じです。

さらに、増加数と減少数で重複して数えている分を差し引きます。
増加数でも減少数でもカウントしている値は、全桁同じ数字の場合なので、
各桁数ごとに10個あり、n桁以下の範囲では、
10*n  ...(D)
です。

１．g(n)
・階乗n!を返します。
・問２０のものを流用しました。


２．関数C(n, m)
・n個の中からm個を選ぶ組合せの個数を返します。
・公式から、n!/（m!・(n-m)!）　です。

３．関数H(n, m)
・n個の中からm個を選ぶ重複組合せの個数を返します。
・上記(B)をそのまま実装しました。

４．関数f(n)
・10ⁿ未満、つまりn桁以下で、はずみ数以外の数の個数を返します。

・c = H(10, n)-H(10, 0)
　増加数の個数です。上記(C)をそのまま実装しました。

・for i in xrange(1, n+1): c += H(10,i)
　減少数の個数です。
　n桁の減少数である上記(A)をそのまま実装し、1桁からn桁の分の和を計算しました。

・c -= 10*n
　増加数と減少数の重複分を差し引きます。
　上記(D)をそのまま実装しました。




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