結果

問題 No.174 カードゲーム（Hard）
コンテスト
ユーザー Kyutatsu
提出日時 2024-12-31 23:46:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 322 ms / 2,000 ms
コード長 2,092 bytes
コンパイル時間 5,779 ms
コンパイル使用メモリ 288,632 KB
実行使用メモリ 20,004 KB
最終ジャッジ日時 2024-12-31 23:46:36
合計ジャッジ時間 7,955 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iomanip>
#include <functional>
#include <sstream>
#include <bit>

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);

    // DP[ 状態S ] := カードを使っていった結果、Sとなる "確率"
    vector<double> DP_A(1 << N), DP_B(1 << N);
    DP_A[(1 << N) - 1] = 1.0;
    DP_B[(1 << N) - 1] = 1.0;

    // prob[n試合目][カード] := を出す確率
    vector prob_a(N, vector<double>(N));
    vector prob_b(N, vector<double>(N));

    auto calc_dp = [&](
        double P, 
        vector<double>& dp,
        vector<vector<double>>& prob
    ) {
        for (int i=(1 << N) - 1;1<=i;i--) {
            bool is_first = true;
            for (int j=0;j<N;j++) {
                if ((1 << j) & i) {
                    int next_s = (1 << j) ^ i;
                    int count = popcount((unsigned int)i);
                    double p;
                    if (count == 1) p = dp[i];
                    else if (is_first) {
                        p = P * dp[i];
                        is_first = false;
                    }
                    else p = (1.0 - P) * (1.0 / (count - 1.0)) * dp[i];
                    
                    dp[next_s] += p;
                    
                    int n = N - count; // n試合目(0〜N-1)
                    prob[n][j] += p;
                }
            }
        }
        // CHECK 1.0となるはず.
        cerr << "dp[0] = " << dp[0] << endl;
    };
    calc_dp(PA, DP_A, prob_a);
    calc_dp(PB, DP_B, prob_b);

    double res = 0;
    for (int n=0;n<N;n++)
        for (int a_card=0;a_card<N;a_card++)
            for (int b_card=0;b_card<N;b_card++) {
                double p = prob_a[n][a_card] * prob_b[n][b_card];
                double s = A[a_card] + B[b_card];
                if (A[a_card] > B[b_card]) res += p * s;
            }
    cout << fixed << setprecision(10) << res << endl;
}
0