「AOJ1051～1060」の編集履歴（バックアップ）一覧に戻る

AOJ1051～1060 - (2012/07/24 (火) 12:29:01) の編集履歴(バックアップ)

---

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;//30日目以降はこの値で取得数が増えていくと考えても誤差累積は小さく何の問題もない
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]);
}
}