結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    P_A = float(input[ptr])
    ptr += 1
    P_B = 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

    # Precompute a_probs and b_probs
    a_probs = {}
    for mask in range(1 << N):
        cnt = bin(mask).count('1')
        if cnt == 0:
            continue
        indices = []
        for i in range(N):
            if mask & (1 << i):
                indices.append(i)
        # Sort indices based on A's values
        sorted_indices = sorted(indices, key=lambda x: A[x])
        size = len(sorted_indices)
        if size == 1:
            a_probs[mask] = [(sorted_indices[0], 1.0)]
        else:
            prob_smallest = P_A
            prob_others = (1.0 - P_A) / (size - 1)
            probs = []
            for idx in sorted_indices:
                if idx == sorted_indices[0]:
                    probs.append((idx, prob_smallest))
                else:
                    probs.append((idx, prob_others))
            a_probs[mask] = probs

    b_probs = {}
    for mask in range(1 << N):
        cnt = bin(mask).count('1')
        if cnt == 0:
            continue
        indices = []
        for i in range(N):
            if mask & (1 << i):
                indices.append(i)
        # Sort indices based on B's values
        sorted_indices = sorted(indices, key=lambda x: B[x])
        size = len(sorted_indices)
        if size == 1:
            b_probs[mask] = [(sorted_indices[0], 1.0)]
        else:
            prob_smallest = P_B
            prob_others = (1.0 - P_B) / (size - 1)
            probs = []
            for idx in sorted_indices:
                if idx == sorted_indices[0]:
                    probs.append((idx, prob_smallest))
                else:
                    probs.append((idx, prob_others))
            b_probs[mask] = probs

    # Initialize DP
    dp = defaultdict(lambda: defaultdict(float))
    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1
    dp[(initial_a_mask, initial_b_mask)][0] = 1.0

    for step in range(N):
        new_dp = defaultdict(lambda: defaultdict(float))
        for (a_mask, b_mask), scores in dp.items():
            a_choices = a_probs.get(a_mask, [])
            b_choices = b_probs.get(b_mask, [])
            for a_idx, a_p in a_choices:
                a_val = A[a_idx]
                new_a_mask = a_mask & ~ (1 << a_idx)
                for b_idx, b_p in b_choices:
                    b_val = B[b_idx]
                    new_b_mask = b_mask & ~ (1 << b_idx)
                    if a_val > b_val:
                        delta = a_val + b_val
                    else:
                        delta = - (a_val + b_val)
                    for score, p in scores.items():
                        new_score = score + delta
                        new_p = p * a_p * b_p
                        new_dp[(new_a_mask, new_b_mask)][new_score] += new_p
        dp = new_dp

    total = 0.0
    for scores in dp.values():
        for score, p in scores.items():
            if score > 0:
                total += p

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

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