yukicoder : No.76 回数の期待値で練習

問題文はしっかり読みましょう。
http://yukicoder.me/problems/154

問題

1～6の目がでるサイコロがある。
サイコロを振る度その目を足して行って、和がNを超えたら終了する。

終了までにサイコロを振る回数の期待値を求めよ。

解法

この問題、今でこそ括弧で注意書きがあるが本番はこの記載がなかった。
つまり、各目の出る数は一定ではないということがわかる。

i番の目が出る確率をP(i)とし、和が初めてx以上になるようにサイコロを振る回数の期待値をF(x)とすると：

• 
• 

である。F(x)がxがマイナスな時にも成立するというのが重要で、これによりF(x)はxちょうどではなくx以上になる確率を求めることができる。

あとはP(i)を求めればよい。
サンプルケースにF(1)～F(6)の値があるので、これらを用いて順にP(1)～P(6)を求めていく。
ちなみにこのサイコロの各目が出る確率の比は1:2:3:1:3:2である。

int T;
double DP[1000057];
double S[7];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	S[1]=1.0/12;
	S[2]=2.0/12;
	S[3]=3.0/12;
	S[4]=1.0/12;
	S[5]=3.0/12;
	S[6]=2.0/12;
	
	for(i=1;i<=1000006;i++) {
		DP[i+10]=1+(DP[i+10-1]*S[1]+DP[i+10-2]*S[2]+DP[i+10-3]*S[3]+DP[i+10-4]*S[4]+DP[i+10-5]*S[5]+DP[i+10-6]*S[6]);
	}
	
	cin>>T;
	FOR(i,T) {
		cin>>x;
		_P("%.12lf\n",DP[x+10]);
	}
}

まとめ

これこそ「悪の」シリーズにふさわしい問題かも。