1056 - Ben Toh
問題概要
初日、弁当を確率1で手に入れる。また、その次の日から弁当を買い続ける。弁当を手に入れた次の日の、弁当を入手できる確率は半分になる。しかし、弁当を入手できなかった次の日は確率1で弁当を入手できる。一日一回n日間弁当を買いに行くとき、入手できる弁当の期待値を求めよ。
コード
#include<iostream> #include<vector> #include<cmath> #define N 100001 #define ALPHA_N 10 using namespace std; void solve(double *expect){ double possible[ALPHA_N]; double npossible[ALPHA_N]; expect[0] = 0; expect[1] = 1; expect[2] = 1.5; possible[0]=1; for(int i = 1; i < ALPHA_N; ++i){ double pos = 1.0/((double)(1<<i)); possible[i] = pos * possible[i-1]; npossible[i] = (1-pos)*possible[i-1]; } for(int n = 3; n < N; ++n){ expect[n] = 0; for(int j = 1; j < ALPHA_N && n-j-1 >= 0; ++j){ expect[n] += npossible[j] * ( j + expect[n-j-1] ); } if( n-1 < ALPHA_N ) expect[n] += n * possible[n-1]; } } int main(){ double ans[N]; solve( ans ); while(true){ int n; scanf("%d", &n); if(n==0)break; printf("%.3lf\n", ans[n]); } return 0; }
解法
m(m<=n)日目で弁当を入手できなかった場合について、[その確率]×[それまでに手に入れた弁当の数+(n-m-1)日間で入手できる弁当の数の期待値] を考える。
厳密にやると大変なことになるので、連続何個か以上の場合はすべて考慮しないようにする。
ちなみに、9個連続を確率0とみなすとWAになる。