DPまとめコンテスト I - Coins

概要

枚のコインがあり、コインの表が出る確率はである。
枚のコインをすべて投げるとき、表の枚数が裏の枚数を超える確率を求めよ。

制約

は奇数

方針

dp[i][j] : コインをi枚使い、表がj枚である確率 としてDPする。

解答

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	double p[n];
	rep(i, n) cin >> p[i];
 
	double dp[n+1][n+1];
	rep(i, n+1) rep(j, n+1) dp[i][j] = 0.0;
	// dp[i][j] : コインをi枚使い、表がj枚である確率
 
	dp[0][0] = 1.0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= i; j++){
			if(j-1 >= 0) dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1.0 - p[i-1]);
			else dp[i][j] = dp[i-1][j] * (1.0 - p[i-1]);
		}
	}
 
	double ans = 0.0;
	for(int i = n / 2 + 1; i <= n; i++) ans += dp[n][i];
	cout << fixed << setprecision(11) << ans << endl;
}