結果
問題 |
No.66 輝け☆全国たこやき杯
|
ユーザー |
|
提出日時 | 2015-10-09 17:47:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 1,097 bytes |
コンパイル時間 | 760 ms |
コンパイル使用メモリ | 71,768 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-07-20 02:23:36 |
合計ジャッジ時間 | 1,352 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <utility> #include <cmath> using namespace std; int main() { int m, n; cin >> m; n = pow(2, m); vector<int> s(n), s2(n); for (int i = 0; i < n; i++) { cin >> s[i]; s2[i] = s[i] * s[i]; } // dp[i][j] = i回戦をjが突破する確率 vector< vector<double> > prob(m + 1, vector<double>(n, 0)); prob[0] = vector<double>(n, 1); vector< vector <double> > win(n, vector<double>(n, 0.0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { continue; } win[i][j] = (1.0 * s2[i]) / (s2[i] + s2[j]); } } for (int i = 1; i <= m; i++) { int n_person = pow(2, i); for (int j = 0; j < n; j += n_person) { int y_begin = j + n_person / 2; int y_end = j + n_person - 1; for (int x = j; x < y_begin; x++) { for (int y = y_begin; y <= y_end; y++) { prob[i][x] += win[x][y] * prob[i - 1][x] * prob[i - 1][y]; prob[i][y] += win[y][x] * prob[i - 1][x] * prob[i - 1][y]; } } } } printf("%.9f\n", prob[m][0]); return 0; }