Problem 1056 : Ben Toh

Problem 1056 : Ben Toh
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1056&lang=jp

• 問題概要

今年のUAPCの問題です。
コンテスト中に解くことができてすごくうれしかったです。
最初の日はかならず弁当をゲットできる。
その日弁当をゲットすると、次の日はその半分の確率でゲットできる。
失敗すると、もとの確率にリセットされる。

n日目の期待値を求めよ。

• 解法

DP
dp[i]について、ゲットできず、リセットされたとこから、誤差の許されるところまで減っていく確率を足していく。リセットされる確率 * どんどん減っていく確率をして足していく。つまり、前の取れる確率×0.5^日数*リセットされる確率。iのゲットできない確率からi+1からの、iの日にゲットできなかった場合のものを算出する。
うー、せつめいするのがむずかしい。図でもないととても説明できそうにない。
ソースを見せるのが一番わかり易い。
base リセットされる確率。
rate １、０．５、０，２５と減っていく、問題で定義された確率
prate 前の弁当とれる確率。
nrate　j-i日たったときの確率。

つまり、確率　＝ （前日が１としたときのこの日取れる確率)*(前日の確率)*（リセットして計算し始めたときの確率)
これでdpします。

• ソース

#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdio>

using namespace std;
double dp[100000+1];
main(){

  int n;
  while( cin >> n ) {
    if(n == 0)break;
    double ans = 0;
    fill(dp, dp +n+1, 0);
    for(int i=0; i<=n; i++){
      double rate = 1, prate=1, base=1 - dp[i];
      for(int j=i+1; j<=n; j++){
	double nrate = rate * prate;
	if(nrate < 0.0000000001)break;
	dp[j] += (nrate * base);
	prate = nrate;
	rate *= 0.5;
      }
      ans += dp[i];
    }
    printf("%0.8lf\n",ans);
  }
}

こういう問題大好き。