*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]); } }