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

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

問１２１「円盤ゲームの賞金額」
袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている.
ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する.
各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.
プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.
ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど11/120 となる.
したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう.
支払いはすべてポンドの整数倍であり,
またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため,
与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.
15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.


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



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

def mul(L): return reduce(lambda x,y: x*y, L)

def f(n):
	import itertools
	m = n//2 + 1
	c = 0
	L = [i+2 for i in xrange(n)]
	Ls = set(L)
	
	for i in xrange(m, n+1):
		for t in itertools.combinations(L, i):
			u = Ls - set(t)
			if u: c += mul([s-1 for s in u])
			else: c += 1
			
	s = mul(L)//c
	return s
	
if __name__=="__main__":
	print f(15)

１．関数f(n)
・n回のターンで得られる賞金の最大値を求めます。

・m = n//2 + 1
　mは勝利に必要な勝ち数です。n回のターンのうち半分以上で勝ちです。

・L = [i+2 for i in xrange(n)]
　Lは各ターンごとの全円盤数のリストです。
　リストLのi番目の要素は、iターン目に円盤を取り出す確率の分母でもあります。

・Ls = set(L)
　Lsは全円盤数リストLを集合型にしたものです。後で集合演算で使います。

・for i in xrange(m, n+1):
　ループ変数iは勝ち数です。
　必要な最低勝ち数mから全勝の場合のnまでの値を取ります。

・for t in itertools.combinations(L, i):
　ループ変数tは勝ち数iの場合に青円盤を取り出すターンでの全円盤数、の組み合わせです。
　つまり、青円盤を取り出すターンごとのそれぞれの確率の分母の組み合わせでもあり、
　各ターンごとの全円盤数リストLから、勝ち数i個の要素を取り出した組み合わせです。

・u = Ls - set(t)
　uは全円盤数リストLsからループ変数tの要素を集合演算で差し引いたリストです。
　つまり、赤円盤を取り出すターンでの全円盤数、の組み合わせです。
　これは、青円盤を取り出す１つのパターンの中で、異なる赤円盤を取り出す。場合の数です。
　なので、uの要素を全部掛け合わせると、青円盤を取り出す１つのパターンの。場合の数になります。

・if u: c += mul([s-1 for s in u])
　else: c += 1
　cは青円盤を取り出す１つのパターンの、場合の数の累積値です。
　青円盤を取り出す1つのパターンの場合の数は、uの要素を全部掛け合わせた値なので
　これを累積します。
　ただし、全部青円盤、つまり全ターンで勝つ場合、赤円盤が出ないためリストuが空で
積として計算できないので固定で１パターン分を累積します。

・s = mul(L)//c
　return s
　求める値sは１ゲーム当たりの最大賞金で、勝率の逆数です。
　全部のパターン数を、勝ちパターン数で割った値の小数点以下切り捨て値です。
　問題中の例の４ターンの場合、勝率11/120なので、最大賞金は120/11 = 10.9 ...で10です。
　全部の場合の数は、各ターンごとの全円盤数の積です。
　これを勝つパターン数cで割った値の整数値が、求める最大賞金です。

２．関数mul(L)
・リストLの全要素の積です。問１１０で作成した関数を流用しました。



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