結果
問題 | No.66 輝け☆全国たこやき杯 |
ユーザー | codershifth |
提出日時 | 2015-07-29 12:08:01 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 2,009 bytes |
コンパイル時間 | 1,235 ms |
コンパイル使用メモリ | 150,012 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-24 21:31:17 |
合計ジャッジ時間 | 2,362 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 5 ms
4,380 KB |
ソースコード
#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