結果
問題 |
No.66 輝け☆全国たこやき杯
|
ユーザー |
![]() |
提出日時 | 2016-07-05 14:03:11 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 50 ms / 5,000 ms |
コード長 | 1,887 bytes |
コンパイル時間 | 525 ms |
コンパイル使用メモリ | 62,044 KB |
実行使用メモリ | 69,248 KB |
最終ジャッジ日時 | 2024-10-12 20:15:51 |
合計ジャッジ時間 | 1,771 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <iostream> #include <iomanip> using namespace std; const int kMAX_M = 11; int M; int S[1 << kMAX_M]; double dp[(1 << kMAX_M) * 2][1 << kMAX_M]; // dp[node][player] int Pow2(int n) { return n * n; } double WinningProbability(int node_id, int player, int depth) { if (dp[node_id][player] >= 0.0) return dp[node_id][player]; if (depth == M) { return dp[node_id][player] = 1.0; } int player_num = 1 << (M - depth), my_lb, my_ub; // (1 << depth) - 1 => 一番左のいとこのid my_lb = (node_id - ((1 << depth) - 1)) * player_num; my_ub = my_lb + player_num; int l_id = 2 * node_id + 1, r_id = 2 * node_id + 2; double res = 0.0; if (player < (my_lb + my_ub) / 2) { // プレイヤーが左の子に存在する場合 for (int enemy = (my_lb + my_ub) / 2; enemy < my_ub; enemy++) { res += (double)Pow2(S[player]) / (double)(Pow2(S[player]) + Pow2(S[enemy])) * WinningProbability(l_id, player, depth + 1) * WinningProbability(r_id, enemy, depth + 1); } } else { // プレイヤーが右の子に存在する場合 for (int enemy = my_lb; enemy < (my_lb + my_ub) / 2; enemy++) { res += (double)Pow2(S[player]) / (double)(Pow2(S[player]) + Pow2(S[enemy])) * WinningProbability(l_id, enemy, depth + 1) * WinningProbability(r_id, player, depth + 1); } } return dp[node_id][player] = res; } void Solve() { for (int i = 0; i < (1 << kMAX_M) * 2; i++) { for (int j = 0; j < (1 << kMAX_M); j++) { dp[i][j] = -1.0; } } cout << fixed << setprecision(10) << WinningProbability(0, 0, 0) << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> M; for (int i = 0; i < (1 << M); i++) { cin >> S[i]; } Solve(); return 0; }