TopCoder SRM 381 Div1 Easy TheDiceGame
問題
1〜6の数字をもつダイスがある。
これを振ると、出た目の数だけキャンディが貰える。
n個のキャンディを貰えるまでダイスを振り続けるとき、ダイスを振る回数の期待値を求めよ。
制約条件
n≦1000000
方針
DP.
dp[i]をi個のキャンディを貰えるまでに振るダイスの期待値とすると、
線形性から、
dp[i]=Σ[j=1,6](dp[i-j]+1)/6が成り立つ。
ソースコード
double dp[1000001]; class TheDiceGame { public: double expectedThrows(int n) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ rep(j,6)dp[i]+=(dp[max(0,i-j-1)]+1)/6; } return dp[n]; } };