結果
問題 | No.66 輝け☆全国たこやき杯 |
ユーザー | なお |
提出日時 | 2014-11-08 17:33:50 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,030 bytes |
コンパイル時間 | 3,198 ms |
コンパイル使用メモリ | 145,500 KB |
実行使用メモリ | 5,736 KB |
最終ジャッジ日時 | 2023-08-30 02:43:30 |
合計ジャッジ時間 | 2,068 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
5,736 KB |
testcase_08 | AC | 2 ms
5,672 KB |
testcase_09 | AC | 4 ms
5,640 KB |
ソースコード
// 想定解法: DP #include <bits/stdc++.h> using namespace std; void rc(int v,int mn,int mx){if(v<mn||mx<v){cerr<<"error"<<endl;}} #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) #define FOR(i, f, t) for(int(i)=(f);(i)<(t);(++i)) const int MAX = 15; double dp[MAX+1][(1<<MAX)+1]; int M, S[(1<<MAX)+1]; // m回戦に選手iが勝つ確率を返す double dfs(int m, int i){ if(dp[m][i] >= 0) return dp[m][i]; int p = 1<<(m-1), p2 = p*2; int j = i/p2*p2, k = i/p*p; if(j == k) j += p; double t = 0; for(int l = j; l < j+p; l++){ t += dfs(m-1,l) * S[i] / (S[i]+S[l]); } return dp[m][i] = t * dfs(m-1, i); } int main(){ cin >> M; rc(M, 1, MAX); int n = 1 << M; REP(i, n){ cin >> S[i]; rc(S[i], 1, 30000); S[i] *= S[i]; dp[0][i] = 1.0; } REP(i,M) REP(j,n) dp[i+1][j] = -1; REP(j,n) dp[0][j] = 1.0; cout << fixed << setprecision(16) << dfs(M,0) << endl; return 0; }