結果

問題 No.174 カードゲーム（Hard）
ユーザー h_nosonh_noson
提出日時 2016-05-06 17:42:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 278 ms / 2,000 ms
コード長 2,263 bytes
コンパイル時間 597 ms
コンパイル使用メモリ 71,248 KB
実行使用メモリ 20,172 KB
最終ジャッジ日時 2024-07-06 21:39:26
合計ジャッジ時間 3,244 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 277 ms
20,172 KB
testcase_03 AC 272 ms
20,044 KB
testcase_04 AC 266 ms
19,920 KB
testcase_05 AC 267 ms
19,916 KB
testcase_06 AC 278 ms
19,916 KB
testcase_07 AC 268 ms
20,052 KB
testcase_08 AC 268 ms
20,048 KB
testcase_09 AC 269 ms
20,048 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

int n;
double pb;
double dp[1<<20], dp2[1<<20], p[20][20], e[20][20];
int a[20], b[20];

int main() {
    int i, j;
    double pa;
    cin >> n >> pa >> pb;
    rep (i,n) cin >> a[i];
    rep (i,n) cin >> b[i];
    dp[0] = dp2[0] = 1;
    rep (i,1<<n) {
        bool first = true;
        int cnt = __builtin_popcount(i);
        rep (j,n) {
            if (!(1<<j&i)) {
                if (cnt == n-1) {
                    dp[i|1<<j] += dp[i];
                    dp2[i|1<<j] += dp2[i];
                    p[cnt][j] += dp[i];
                }
                else if (first) {
                    dp[i|1<<j] += dp[i] * pa;
                    dp2[i|1<<j] += dp2[i] * pb;
                    first = false;
                    p[cnt][j] += dp[i] * pa;
                }
                else {
                    dp[i|1<<j] += dp[i] * (1-pa) / (n-cnt-1);
                    dp2[i|1<<j] += dp2[i] * (1-pb) / (n-cnt-1);
                    p[cnt][j] += dp[i] * (1-pa) / (n-cnt-1);
                }
            }
        }
    }
    sort(a,a+n);
    sort(b,b+n);
    rep (i,n) rep (j,n) e[i][j] = p[i][j] * a[j];
    rep (i,n) rrep (j,n-1) {
        p[i][j] += p[i][j+1];
        e[i][j] += e[i][j+1];
    }
    double ans = 0;
    rep (i,1<<n) {
        int cnt = __builtin_popcount(i);
        bool first = true;
        rep (j,n) {
            if (!(i&1<<j)) {
                int index = lower_bound(a,a+n,b[j]) - a;
                if (cnt == n-1)
                    ans += index < n ? dp2[i]*(e[cnt][index]+p[cnt][index]*b[j]) : 0;
                else if (first) {
                    ans += index < n ? dp2[i]*(pb*e[cnt][index]+p[cnt][index]*pb*b[j]) : 0;
                    first = false;
                }
                else
                    ans += index < n ? dp2[i]*((1-pb)/(n-cnt-1)*e[cnt][index]+p[cnt][index]*(1-pb)/(n-cnt-1)*b[j]) : 0;
            }
        }
    }
    cout << setprecision(10) << ans << endl;
    return 0;
}
0