結果

問題 No.174 カードゲーム（Hard）
ユーザー lam6er
提出日時 2025-03-20 20:29:29
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,653 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,832 KB
実行使用メモリ 274,064 KB
最終ジャッジ日時 2025-03-20 20:30:23
合計ジャッジ時間 3,799 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    PA = float(input[ptr])
    ptr += 1
    PB = float(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+N]))
    ptr += N

    sorted_A = sorted(A)
    sorted_B = sorted(B)

    def compute_probs(sorted_cards, P):
        N_cards = len(sorted_cards)
        card_probs = [[0.0] * (N_cards + 2) for _ in range(N_cards)]

        full_mask = (1 << N_cards) - 1
        dp = [defaultdict(float) for _ in range(N_cards + 2)]
        dp[1][full_mask] = 1.0

        for t in range(1, N_cards + 1):
            current_dp = dp[t]
            for mask, prob in current_dp.items():
                if prob <= 0.0:
                    continue
                m = bin(mask).count('1')
                if m == 0:
                    continue

                if m == 1:
                    idx = (mask).bit_length() - 1
                    card_probs[idx][t] += prob
                    next_mask = mask ^ (1 << idx)
                    dp[t + 1][next_mask] += prob
                else:
                    lsb = mask & -mask
                    min_idx = (lsb).bit_length() - 1
                    count_other = m - 1
                    prob_other = (1.0 - P) / count_other if count_other != 0 else 0.0

                    temp_mask = mask
                    while temp_mask:
                        lsb_current = temp_mask & -temp_mask
                        idx = (lsb_current).bit_length() - 1
                        temp_mask ^= lsb_current

                        if idx == min_idx:
                            current_prob = P
                        else:
                            current_prob = prob_other

                        card_probs[idx][t] += prob * current_prob
                        next_mask = mask ^ (1 << idx)
                        dp[t + 1][next_mask] += prob * current_prob
        return card_probs

    prob_A = compute_probs(sorted_A, PA)
    prob_B = compute_probs(sorted_B, PB)

    index_map_A = {card: i for i, card in enumerate(sorted_A)}
    index_map_B = {card: i for i, card in enumerate(sorted_B)}

    expected = 0.0
    for a in A:
        idx_a = index_map_A[a]
        for b in B:
            idx_b = index_map_B[b]
            if a > b:
                total = 0.0
                for t in range(1, N + 1):
                    total += prob_A[idx_a][t] * prob_B[idx_b][t]
                expected += (a + b) * total

    print("{0:.15f}".format(expected))

if __name__ == '__main__':
    main()
0