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

「AOJ1051~1060」の編集履歴(バックアップ)一覧に戻る

AOJ1051~1060 - (2012/07/24 (火) 12:39:40) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

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