結果
問題 |
No.174 カードゲーム(Hard)
|
ユーザー |
![]() |
提出日時 | 2025-01-01 19:28:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 216 ms / 2,000 ms |
コード長 | 1,843 bytes |
コンパイル時間 | 3,133 ms |
コンパイル使用メモリ | 286,924 KB |
実行使用メモリ | 11,968 KB |
最終ジャッジ日時 | 2025-01-01 19:28:42 |
合計ジャッジ時間 | 5,410 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> #include <iomanip> #include <functional> #include <sstream> #include <bit> #include <numeric> using namespace std; int main() { int N; cin >> N; double PA, PB; cin >> PA >> PB; vector<int> A(N), B(N); for (int i=0;i<N;i++) cin >> A[i]; for (int i=0;i<N;i++) cin >> B[i]; ranges::sort(A); ranges::sort(B); auto calc = [&](double P, vector<vector<double>>& cards) { // DP[ 状態S ] := 状態Sとなる確率 // cards[n][c] := n試合目でカードcを出す確率 vector<double> DP(1 << N); DP[(1 << N) -1] = 1.0; for (int s=(1<<N)-1;0<s;s--) { bool is_first = true; int rem = popcount((unsigned int)s); for (int c=0;c<N;c++) { if ((1 << c) & s) { if (rem==1) { double p = 1.0; double px = DP[s] * p; cards[N-rem][c] += px; DP[s ^ (1 << c)] += px; break; } double p = is_first ? P : ((double)1.0 - P) / (rem-1.0); is_first = false; double px = DP[s] * p; cards[N-rem][c] += px; DP[s ^ (1 << c)] += px; } } } cerr << "DP[0] := " << DP[0] << endl; }; vector cards_a(N, vector<double>(N)); vector cards_b(N, vector<double>(N)); calc(PA, cards_a); calc(PB, cards_b); double res = 0; for (int n=0;n<N;n++) for (int a=0;a<N;a++) for (int b=0;b<N;b++) { if (A[a] > B[b]) res += (A[a] + B[b]) * (cards_a[n][a] * cards_b[n][b]); } cout << fixed << setprecision(12) << res << endl; }