結果

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

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    P_A = float(input[idx]); idx +=1
    P_B = float(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    B = list(map(int, input[idx:idx+N]))
    
    A_sorted = sorted(A)
    B_sorted = sorted(B)
    
    # Precompute the indices for quick lookup
    a_index_map = {a: i for i, a in enumerate(A_sorted)}
    b_index_map = {b: i for i, b in enumerate(B_sorted)}
    
    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1
    
    @lru_cache(maxsize=None)
    def dp(a_mask, b_mask, current_diff):
        if a_mask == 0 and b_mask == 0:
            return 1.0 if current_diff > 0 else 0.0
        
        # Get A's remaining cards
        a_remaining = []
        for i in range(N):
            if (a_mask & (1 << i)):
                a_remaining.append(A_sorted[i])
        k_A = len(a_remaining)
        
        # Get B's remaining cards
        b_remaining = []
        for i in range(N):
            if (b_mask & (1 << i)):
                b_remaining.append(B_sorted[i])
        k_B = len(b_remaining)
        
        # Compute probabilities for A's choices
        a_probs = {}
        if k_A == 1:
            a = a_remaining[0]
            a_probs[a] = 1.0
        elif k_A > 1:
            min_a = a_remaining[0]
            a_probs[min_a] = P_A
            other_prob = (1.0 - P_A) / (k_A - 1)
            for a in a_remaining[1:]:
                a_probs[a] = other_prob
        
        # Compute probabilities for B's choices
        b_probs = {}
        if k_B == 1:
            b = b_remaining[0]
            b_probs[b] = 1.0
        elif k_B > 1:
            min_b = b_remaining[0]
            b_probs[min_b] = P_B
            other_prob = (1.0 - P_B) / (k_B - 1)
            for b in b_remaining[1:]:
                b_probs[b] = other_prob
        
        total = 0.0
        for a, prob_a in a_probs.items():
            for b, prob_b in b_probs.items():
                delta = (a + b) if a > b else -(a + b)
                a_idx = a_index_map[a]
                next_a_mask = a_mask & ~(1 << a_idx)
                b_idx = b_index_map[b]
                next_b_mask = b_mask & ~(1 << b_idx)
                total += prob_a * prob_b * dp(next_a_mask, next_b_mask, current_diff + delta)
        return total
    
    result = dp(initial_a_mask, initial_b_mask, 0)
    print("{0:.15f}".format(result))

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