EDPC I - Coins

問題のリンク

I - Coins

思考過程

・N枚全てのコインを振って、表がx 枚となる確率P(x) を0 <= x <= N について求めたらよい。
・独立な試行とDPは非常に相性が良い。

DP table

というわけでDP。
・dp[i][j] := i枚目までのコインを振って、表がj 枚出るという確率。

初期値

・dp[0][0] = 1 （0枚振って表が0枚の確率は1である。本当にそうかな）
・dp[i][j] = 0 （他はまだ0）

遷移

配る方が書きやすい。
・dp[i+1][j+1] += dp[i][j] * p[i] （表が出るパターン、j + 1 <= n でなくてはならない）
・dp[i+1][j] += dp[i][j] * ( 1 - p[i] ) （裏が出るパターン）

解答

・sum{ P(x) | n/2 < x <= n} が答えです。

以下実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
double dp[3010][3010];
int main()
{
  int n;cin >> n;
  vector<double> p(n);
  rep(i,n) cin >> p[i];


  rep(i,n+1) rep(j,n+1) dp[i][j] = 0;
  dp[0][0] = 1;

  rep(i,n) {
    rep(j,n+1) {
      dp[i+1][j] += dp[i][j]*(1 - p[i]);
      if(j != n) dp[i+1][j+1] += dp[i][j]*p[i];
    }
  }
  
  double res = 0;
  for (int i = (n+1)/2; i <= n; ++i) {
    res += dp[n][i];
  }

  printf("%.9f\n", res);
  
  return 0;
}