C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題I (I – Coins) を解いてみた.
■感想.
1. 解答に時間かかったものの本問も正答出来たので, アップロードしてみた.
■C++版プログラム(問題I／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <bits/stdc++.h> using namespace std; int main() { // 1. 入力情報取得. int N; cin >> N; double P[N + 1] = {}; for(int i = 1; i <= N; i++) cin >> P[i]; // 2. 表の個数が裏の個数を上回る確率を計算. // dp[i][j]: i枚目のコインまで確認して, 表の個数(j)となる確率を保存. double dp[N + 1][N + 1] = {}; // 2-1. 1回目は, P[1], 1.0 - P[1] を設定. dp[1][1] = P[1]; dp[1][0] = 1.0 - P[1]; // 2-2. 2回目以降は, 前回の状態をもとに設定. // ex. // 2枚目まで確認して, 表が2枚 … 1枚目まで確認して, 表が1枚. // dp[2][2] = P[2] * dp[1][1]; // 2枚目まで確認して, 表が1枚 … 1枚目まで確認して, 表が1枚 or 表が0枚. // dp[2][1] = (1 - P[2]) * dp[1][1] + P[2] * dp[1][0]; // 2枚目まで確認して, 表が0枚 … 1枚目まで確認して, 表が0枚. // dp[2][0] = (1 - P[2]) * dp[1][0]; // for(int i = 2; i <= N; i++){ for(int j = 0; j <= i; j++){ if(j == 0) dp[i][0] = (1 - P[i]) * dp[i - 1][0]; if(i == j) dp[i][i] = P[i] * dp[i - 1][i - 1]; if(j > 0 && j < i) dp[i][j] = P[i] * dp[i - 1][j - 1] + (1 - P[i]) * dp[i - 1][j]; } } // for(int i = 0; i <= N; i++){ // for(int j = 0; j <= i; j++){ // cout << dp[i][j] << " "; // } // cout << endl; // } // 3. 後処理. double ans = 0.0; for(int j = (N + 1) / 2; j <= N; j++) ans += dp[N][j]; cout << fixed; cout << setprecision(10) << ans << endl; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
[入力例] 3 0.30 0.60 0.80 [出力例(debug版)] 0 0.7 0.3 0.28 0.54 0.18 0.056 0.332 0.468 0.144 0.6120000000 ※AtCoderのテストケースより [入力例] 1 0.50 [出力例(debug版)] 0 0.5 0.5 0.5000000000 ※AtCoderのテストケースより [入力例] 5 0.42 0.01 0.42 0.99 0.42 [出力例(debug版)] 0 0.58 0.42 0.5742 0.4216 0.0042 0.333036 0.485692 0.179508 0.001764 0.00333036 0.334563 0.48263 0.177731 0.00174636 0.00193161 0.195445 0.420442 0.305788 0.0756597 0.000733471 0.3821815872 ※AtCoderのテストケースより [入力例] 11 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 [出力例] 0.5000000000 |