※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ1051~1060」の編集履歴(バックアップ)一覧に戻る
AOJ1051~1060」を以下のとおり復元します。
*1056 Ben Toh
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056&lang=jp
最大10万日にわたる弁当争奪戦でどれだけ弁当をゲットできるか期待値を求める問題。

この問題、馬鹿正直に賢い漸化式を建てようとすると計算量との戦いで中々漸化式が立ちません。
漸化式が立っても計算量が膨れ上がったりします。
なのですがこの問題不思議なことに、日数がたつごとに前日からの弁当取得数期待値の増加が定数に収束します。
そこを利用して適当な日までは厳密に計算し後は単純な線形予測で解けます。




 #include<stdio.h>
 long double memo[32];
 double saiki(int deep,long double r1,long double r2,long double sum,int last){
	if(deep==last){
		return sum*r2;
	}
	double re=0;
	if(deep>0)re=(1.0-r1)*(memo[last-deep-1]+sum)*r2;
	re+=saiki(deep+1,r1*0.5,r2*r1,sum+1,last);//弁当をゲットできた
	return re;
 }
 int main(){
	for(int i=1;i<31;i++){
		memo[i]=saiki(0,1.0,1.0,0,i);
		//printf("%.13Lf\n",memo[i]);
	}
	long double add=0.621446216664598;
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		if(30<n) printf("%Lf\n",memo[30]+(n-30)*add);
		else printf("%Lf\n",memo[n]);
	}
 }

復元してよろしいですか?