yukicoder : No.301 サイコロで確率問題 (1)

300問達成おめでとうございます。
http://yukicoder.me/problems/189

問題

yukicoder No.75と同じ。
yukicoder : No.75 回数の期待値の問題 - kmjp's blog

ただし出目の和の上限は10^18と大きい。
また、1つのテストは最大1万個のケースで構成される。

解法

Nが小さいときは過去問の解法をそのまま利用すればよい。

上記プログラムをN＝1～200で回してみると、解が(N+5/3)に収束していくのがわかる。
よってNが大きいときあそれを答えればよい。

double dp[10000];

double test(double d,ll a) {
	int i,j;
	
	ZERO(dp);
	for(i=1;i<=a;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[a];
}

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

int T;
ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		if(N<=200) solve2(N);
		else {
			_P("%.12lf\n",N+1+2.0/3);
		}
		
	}
	
}

まとめ

yukicoder勢にサイコロ苦手意識が…。