結果

問題 No.173 カードゲーム（Medium）
ユーザー gew1fw
提出日時 2025-06-12 13:00:12
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,497 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 849,504 KB
最終ジャッジ日時 2025-06-12 13:06:29
合計ジャッジ時間 4,762 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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

    A_sorted = sorted(A)
    B_sorted = sorted(B)

    def get_first_set_bit(mask):
        if mask == 0:
            return -1
        return (mask & -mask).bit_length() -1

    # Precompute probabilities for A's masks
    a_probs = {}
    n = N
    for mask in range(1 << n):
        bits = []
        for i in range(n):
            if (mask >> i) & 1:
                bits.append(i)
        k = len(bits)
        if k == 0:
            continue
        if k == 1:
            a_probs[mask] = [(bits[0], 1.0)]
        else:
            first = get_first_set_bit(mask)
            prob_list = []
            for i in bits:
                if i == first:
                    prob = PA
                else:
                    prob = (1.0 - PA) / (k -1)
                prob_list.append( (i, prob) )
            a_probs[mask] = prob_list

    # Precompute probabilities for B's masks
    b_probs = {}
    for mask in range(1 << n):
        bits = []
        for i in range(n):
            if (mask >> i) & 1:
                bits.append(i)
        k = len(bits)
        if k == 0:
            continue
        if k == 1:
            b_probs[mask] = [(bits[0], 1.0)]
        else:
            first = get_first_set_bit(mask)
            prob_list = []
            for i in bits:
                if i == first:
                    prob = PB
                else:
                    prob = (1.0 - PB) / (k -1)
                prob_list.append( (i, prob) )
            b_probs[mask] = prob_list

    # Initialize DP
    dp = defaultdict( lambda: defaultdict(float) )
    full_mask_a = (1 << n) -1
    full_mask_b = (1 << n) -1
    dp[(full_mask_a, full_mask_b)][0] = 1.0

    for step in range(N):
        new_dp = defaultdict( lambda: defaultdict(float) )
        for (a_mask, b_mask), score_dict in dp.items():
            for score_diff, prob in score_dict.items():
                # Iterate over all possible a and b choices
                a_choices = a_probs.get(a_mask, [])
                b_choices = b_probs.get(b_mask, [])
                for a_idx, a_p in a_choices:
                    a_card = A_sorted[a_idx]
                    new_a_mask = a_mask ^ (1 << a_idx)
                    for b_idx, b_p in b_choices:
                        b_card = B_sorted[b_idx]
                        new_b_mask = b_mask ^ (1 << b_idx)
                        if a_card > b_card:
                            contribution = a_card + b_card
                        else:
                            contribution = - (a_card + b_card)
                        new_score = score_diff + contribution
                        key = (new_a_mask, new_b_mask)
                        new_dp[key][new_score] += prob * a_p * b_p
        # Prune states with very low probability to save memory
        dp = defaultdict( lambda: defaultdict(float) )
        for key, scores in new_dp.items():
            for s, p in scores.items():
                if p >= 1e-9:
                    dp[key][s] += p

    total = 0.0
    for key in dp:
        for s, p in dp[key].items():
            if s > 0:
                total += p
    print("{0:.15f}".format(total))

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