結果

問題 No.174 カードゲーム（Hard）
ユーザー lam6er
提出日時 2025-04-16 00:00:25
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,777 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 81,684 KB
実行使用メモリ 684,124 KB
最終ジャッジ日時 2025-04-16 00:02:38
合計ジャッジ時間 3,818 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    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]))
    idx +=N
    
    A_sorted = sorted(A)
    B_sorted = sorted(B)
    
    # Precompute for each mask, the sorted available cards and count
    a_masks = {}
    for mask in range(1 << N):
        available = []
        for i in range(N):
            if mask & (1 << i):
                available.append(A_sorted[i])
        a_masks[mask] = (available, len(available))
    
    b_masks = {}
    for mask in range(1 << N):
        available = []
        for i in range(N):
            if mask & (1 << i):
                available.append(B_sorted[i])
        b_masks[mask] = (available, len(available))
    
    A_index = {card: i for i, card in enumerate(A_sorted)}
    B_index = {card: i for i, card in enumerate(B_sorted)}
    
    memo = {}
    
    def dp(a_mask, b_mask):
        if (a_mask, b_mask) in memo:
            return memo[(a_mask, b_mask)]
        
        a_available, a_count = a_masks[a_mask]
        b_available, b_count = b_masks[b_mask]
        
        if a_count == 0 or b_count == 0:
            memo[(a_mask, b_mask)] = 0.0
            return 0.0
        
        a_probs = {}
        if a_count == 1:
            a_probs[a_available[0]] = 1.0
        else:
            a_min = a_available[0]
            a_probs[a_min] = P_A
            other_prob = (1.0 - P_A) / (a_count - 1)
            for card in a_available[1:]:
                a_probs[card] = other_prob
        
        b_probs = {}
        if b_count == 1:
            b_probs[b_available[0]] = 1.0
        else:
            b_min = b_available[0]
            b_probs[b_min] = P_B
            other_prob = (1.0 - P_B) / (b_count - 1)
            for card in b_available[1:]:
                b_probs[card] = other_prob
        
        total = 0.0
        
        for a in a_available:
            pa = a_probs[a]
            for b in b_available:
                pb = b_probs[b]
                prob = pa * pb
                contribution = (a + b) if (a > b) else 0.0
                new_a_mask = a_mask ^ (1 << A_index[a])
                new_b_mask = b_mask ^ (1 << B_index[b])
                res = dp(new_a_mask, new_b_mask)
                total += prob * (contribution + res)
        
        memo[(a_mask, b_mask)] = total
        return total
    
    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1
    result = dp(initial_a_mask, initial_b_mask)
    print("{0:.15f}".format(result))

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