yukicoder : No.75 回数の期待値の問題

先に「☆２個だ！」と076に取り掛かってしまいタイムロス。
http://yukicoder.me/problems/129

問題

初期状態では、残り数値がKである。
６面サイコロを１回振ると、残り数値が目の数の分減る。

残り数値が0になったら終了である。
残り数値が0を通り過ぎてマイナスになった場合、Kにリセットされる。

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

解法

残り数値xから終了までのサイコロを振る回数の期待値をP(x)とする。
P(x)には以下の関係が成り立つ。

• P(0)=0
• xが負のとき、P(x)=P(K)
• xが正のとき、P(x)=1 + (P(x-1)+P(x-2)+P(x-3)+P(x-4)+P(x-5)+P(x-6))/6

答えとなるP(K)を求める方法はいくつかある。

• P(0)～P(K)の式から(K+1)変数の連立方程式を立てて解く。
• P(K)=mと仮決めしてDPを行い、DPの結果で求まるP(K)≧mかどうか判定する。条件を満たすmの最小値が解なので、二分探索でよい。自分はこちら。
• 誤差の条件が緩いので、モンテカルロ法。

int N;
double dp[10000];

double test(double d) {
	int i,j;
	
	for(i=1;i<=N;i++) {
		for(j=1;j<=6;j++) {
			if(j>i) if(j>i) dp[i] += d;
			if(i>j) dp[i] += dp[i-j];
		}
		dp[i]=dp[i]/6.0+1;
	}
	return dp[N];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	double L=0,R=1e10;
	FOR(i,100) {
		double M=(L+R)/2.0;
		if(test(M)>=M) L=M;
		else R=M;
	}
	_P("%.12lf\n",(L+R)/2.0);
	
}

まとめ

076にやられた。