SRM 339 div1 level2

最初に数学をやっておけば簡単だった。

この賭け、結局勝って次の賭けからもう一度勝つ時に儲かるチップは必ず１。

Ｓ= 1+2+4+...+2^n
2S = 2+4+8+...+2^(n+1)
S=2S-S = 2^(n+1)-1

n-1回負けてn回目に勝つと負け分は2^n-1、勝ち分は2^n、だから儲けは１。

すると、連続k回負けて次に勝つというセットがどのように組めるか数えればよいだけ。ゴールが1000だから、現在の持ち金と残りラウンド数の2次元配列でも[1000][50]だからＤＰで余裕。残りラウンドがrなら、0からr-1回連続で負けて次に勝つというセットが取れる。確率は求められるし、k回負けて次にかつなら、残りラウンドはr-k-1にして次の再起呼び出しをすればよい。

• 等差数列は解いておけ
• ＤＰはmemすること前提に。memのサイズでループ回数を概算。
• この場合は、途中で掛け金がなくなることを終了条件に含めなければならない。