プロジェクトオイラー
http://projecteuler.net/
Q232.
プレーヤーが2人いる。まず、プレーヤー1がコインを投げる。そのコインが表だったら、プレーヤー1には1ポイント与えられる。裏なら0ポイントである。次に、プレーヤー2がある正の整数Tを選んで、コインをT回投げる。そのコインがすべて表ならプレーヤー2には2T-1が与えられる。裏なら0ポイントである。プレーヤー1が先行で、100ポイント以上先に得たほうが勝ちである。
プレーヤー2は常に勝つ確率が最大になるようなTの選択をする。
プレーヤー2が確率を、小数点以下8桁で示せ。
苦労した。最初はなんでもない問題かと思った。Tは7→6→3でぴったり100になるからそうすればいいだけだろうと。しかし、試してみるとそうではなかった。意外と細かくするほうが確率が高くなった。そのうち、相手のポイント獲得に応じてTを変えなければいけないことに気がついた。しかし、よくよく考えると、簡単に漸化式が書けることが分かった。そうすると、2T-1が残りのポイント数を超えるようなTを選ばなければならないことに気がついた。例えば相手があと1ポイントで自分が7ポイントなら、博打で8ポイントを狙っていかなければならない。最後に、相手と自分は同時にコイントスして、同時に100ポイント以上に達すれば自分の勝ちではない、と今までしていたが、相手がコイントスしたのを見てTを選べるので、それよりは高い確率で勝つことに気がついた。その修正は簡単だった。
def calc_P(m, n):
if n == 0:
Popt[m][n] = 1.0
elif m == 0:
Popt[0][n] = 0
else:
T = 1
while 2 ** (T - 1) < n * 2:
n_next = max(0, n - 2 ** (T - 1))
p = (Popt[m][n_next] + Popt[m-1][n_next]
+ (2 ** T - 1) * Popt[m-1][n]) / (2 ** T + 1)
if p > Popt[m][n]:
Popt[m][n] = p
T += 1N = 100
Popt = [ [ 0 ] * (N + 1) for n in range(N + 1) ]
for n in range(N + 1):
for m in range(N + 1):
calc_P(m, n)
print (Popt[N][N] + Popt[N-1][N]) / 2
