AOJ1056 Ben Toh

問題リンク Ben Toh

• 解法

DPです。
dp[ n ]: n日間に得られる弁当の個数の期待値
の表を埋めて解きます。
n日間の期間があり、初日から連続してk日間弁当を獲得できている場合を考えます、またこの状態になる確率をp、次の弁当獲得確率をwinとします。ここで、p*(1-win)の確率で弁当獲得に失敗します。そしてk+2日目からは残り日数n-k-1の場合と全く同じ状態遷移図となるのでdp[n-k-1]の結果が使えます。つまり
dp[ n ] += p*(1-win) * (k + dp[max{0, n-k-1}])
となります。このkを1〜nまで続け、最後に、連続n日間弁当を獲得し続けた場合の
dp[ n ] += n*p
を加算します。
ですが、これだと、dp[ n ]を求めるのにO(n)かかってTLEとなります。問題の答えの精度に注目すると10^-2までとかなり粗い精度でいいので少し計算をさぼることができます。
連続して弁当を獲得し続けられる確率 p は急激に小さくなっていくので少し経つだけでほぼ0となります。よって、pがほとんど0になったらそこでdp[ n ]を求めるためのループを止めてしまっても解に影響ありません。

• ソース

import java.util.Scanner;

//Ben Toh
public class AOJ1056 {
	
	void run(){
		double EPS = 1e-13;
		double[] res = new double[100001];
		res[1] = 1;
		for(int n=2;n<=100000;n++){
			double p = 1, win = 0.5;
			int k = 1;
			while(EPS<p && k<n){
				double not = p*(1-win);
				res[n] += not*(k+res[Math.max(0, n-k-1)]);
				p*=win; win/=2; k++;
			}
			res[n]+=n*p;
		}
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			System.out.printf("%.8f\n", res[n]);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1056().run();
	}
}