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になる。