SRM408 Div2 1000

問題

友達のシドと赤玉redCount個と青玉blueCount個が入ったバッグから取り出すゲームをする。玉の個数の合計は奇数。
自分のターンではランダムに玉を1つ取り出す。シドのターンでは必ず青玉を取り出す。自分が勝つためにはバックに入っている最後の玉を取り出し、なおかつそれが青色の時でなければならない。それ以外はシドが勝利する。
自分が勝つ確率を返す。

考え方

dp。
まず、青玉より赤玉の方が多い場合は必ず負け、青玉-赤玉が偶数の時も必ず負ける。
dp[r][b]=(r/(r+b))*dp[r-1][b-1] + (b/(r+b))*dp[r][b-2]と書ける。(dp[0][3]=1.0,dp[1][2]=1/3)。
しかし、double dp[4000][4000]は無理なので、うまく配列を使ってメモリを減らす。
よく見ると、rが偶数の時はbが奇数のところ、rが奇数の時はbが偶数のところしか使わない。なので、dp[4000][2000]で偶数か奇数かで計算を変えればよい。