AOJ 1056 - Ben Toh

問題 : Ben Toh

解法 :

弁当を得れるかの最初の4 日の遷移図を書くと次のようになる.

すると, この遷移図は0 を境に2 日前の遷移と同じ遷移をしている事が分かる. ここで$n$ 日目に弁当を得る個数の期待値を$E_n$ とすると, これは$E_{n-2}$ から$E_0$ までの和と定数を使って表すことができることが分かる. (コード参照.)

また, $E_i$ にかける係数が小さくなったときに計算を打ち切ることで, $O(n \log n)$ 時間程度でこの問題を解けることが分かる.

ずっと前から考えていて, この方針で解こうとしていたら誤差死とかで苦労してしまった... 期待値むずいですネ.

コード　:

#include <cstdio>
#include <algorithm>

using namespace std;

double dp[100001];

int main()
{
	int n;
	
	dp[1] = 1.0; dp[2] = 1.5; dp[3] = 2.125;
	
	for (int i = 4; i <= 100000; i++){
		double mul = 1, p = 1, r = 0.5;
		for (int j = i - 2; j >= 0 && mul > 1e-15; j--){
			dp[i] += (dp[j] + i - 1 - j) * (1 - r) * mul;
			p *= 0.5;
			r *= 0.5;
			mul *= p;
		}
		dp[i] += mul * i;
	}
	
	while (scanf("%d", &n) && n){
		printf("%lf\n", dp[n]);
	}
	
	return (0);
}