結果
問題 |
No.66 輝け☆全国たこやき杯
|
ユーザー |
![]() |
提出日時 | 2015-07-29 12:08:01 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 2,009 bytes |
コンパイル時間 | 1,304 ms |
コンパイル使用メモリ | 163,372 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-17 21:56:23 |
合計ジャッジ時間 | 2,124 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class TakoyakiCup { public: void solve(void) { int M,N; cin>>M; N = (1<<M); vector<double> S(N, 0.0); REP(i,N) cin>>S[i]; // x が y に勝つ確率 auto win = [&](int x, int y) { return S[x]*S[x]/(S[x]*S[x]+S[y]*S[y]); }; // 各 round を逐次勝ち上がる確率を計算していく // dp[i][j] := i が j round 目を勝ち上がる確率 vector<vector<double>> dp(N, vector<double>(M+1,0)); // 戦う前なので 1.0 初期化 REP(i, N) dp[i][0] = 1.0; // 各 round ごとに DP // O(M^2*2^M) FOR(i, 1, M+1) { int len = (1<<i); // i round のサブトーナメントの参加人数 REP(x, N) { // x が所属するサブトーナメントの範囲 [l,r) を求める int l = x/len*len; int r = l+len; int mid = l+len/2; // トーナメント区間の中心 if (x < mid) FOR(y, mid, r) // 対戦相手は自分の所属していなサブトーナメントに所属している dp[x][i] += dp[x][i-1]*dp[y][i-1]*win(x,y); else FOR(y, l, mid) dp[x][i] += dp[x][i-1]*dp[y][i-1]*win(x,y); } } cout<<dp[0][M]<<endl; } }; #if 1 int main(int argc, char *argv[]) { ios::sync_with_stdio(false); auto obj = new TakoyakiCup(); obj->solve(); delete obj; return 0; } #endif