結果

問題 No.174 カードゲーム（Hard）
ユーザー gew1fw
提出日時 2025-06-12 21:30:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,684 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 172,900 KB
最終ジャッジ日時 2025-06-12 21:30:45
合計ジャッジ時間 3,997 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    N, PA, PB = map(float, sys.stdin.readline().split())
    N = int(N)
    PA = PA
    PB = PB
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    
    A_sorted = sorted(A)
    B_sorted = sorted(B)
    
    A_indices = {a: i for i, a in enumerate(A_sorted)}
    B_indices = {b: i for i, b in enumerate(B_sorted)}
    
    A_mask = 0
    for a in A:
        A_mask |= 1 << A_indices[a]
    
    B_mask = 0
    for b in B:
        B_mask |= 1 << B_indices[b]
    
    @lru_cache(maxsize=None)
    def dp(a_mask, b_mask):
        if a_mask == 0 and b_mask == 0:
            return 0.0
        a_remaining = [A_sorted[i] for i in range(N) if (a_mask & (1 << i))]
        b_remaining = [B_sorted[i] for i in range(N) if (b_mask & (1 << i))]
        if not a_remaining or not b_remaining:
            return 0.0
        
        a_min = min(a_remaining)
        b_min = min(b_remaining)
        len_a = len(a_remaining)
        len_b = len(b_remaining)
        
        a_choice = []
        a_prob = []
        if len_a == 1:
            a_choice.append(a_min)
            a_prob.append(1.0)
        else:
            a_choice.append(a_min)
            a_prob.append(PA)
            other_cards = [a for a in a_remaining if a != a_min]
            prob_other = (1.0 - PA) / (len_a - 1)
            for a in other_cards:
                a_choice.append(a)
                a_prob.append(prob_other)
        
        b_choice = []
        b_prob = []
        if len_b == 1:
            b_choice.append(b_min)
            b_prob.append(1.0)
        else:
            b_choice.append(b_min)
            b_prob.append(PB)
            other_cards = [b for b in b_remaining if b != b_min]
            prob_other = (1.0 - PB) / (len_b - 1)
            for b in other_cards:
                b_choice.append(b)
                b_prob.append(prob_other)
        
        total = 0.0
        for i in range(len(a_choice)):
            a = a_choice[i]
            pa = a_prob[i]
            for j in range(len(b_choice)):
                b = b_choice[j]
                pb = b_prob[j]
                prob = pa * pb
                a_new_mask = a_mask & ~(1 << A_indices[a])
                b_new_mask = b_mask & ~(1 << B_indices[b])
                if a > b:
                    total += prob * (a + b)
                elif a < b:
                    pass
                total += prob * dp(a_new_mask, b_new_mask)
        return total
    
    expected = dp(A_mask, B_mask)
    print("{0:.15f}".format(expected))

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