結果

問題 No.174 カードゲーム（Hard）
ユーザー gew1fw
提出日時 2025-06-12 21:31:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,201 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 162,688 KB
最終ジャッジ日時 2025-06-12 21:32:47
合計ジャッジ時間 3,713 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = float(PA)
    PB = float(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)
    
    @lru_cache(maxsize=None)
    def dp(mask_a, mask_b):
        if mask_a == 0 and mask_b == 0:
            return 0.0
        a_cards = []
        for i in range(N):
            if (mask_a >> i) & 1:
                a_cards.append(A[i])
        b_cards = []
        for i in range(N):
            if (mask_b >> i) & 1:
                b_cards.append(B[i])
        
        if not a_cards or not b_cards:
            return 0.0
        
        a_size = len(a_cards)
        b_size = len(b_cards)
        
        a_min = min(a_cards)
        a_other = [x for x in a_cards if x != a_min]
        a_prob = {}
        if a_size == 1:
            a_prob[a_min] = 1.0
        else:
            a_prob[a_min] = PA
            for x in a_other:
                a_prob[x] = (1.0 - PA) / (a_size - 1)
        
        b_min = min(b_cards)
        b_other = [x for x in b_cards if x != b_min]
        b_prob = {}
        if b_size == 1:
            b_prob[b_min] = 1.0
        else:
            b_prob[b_min] = PB
            for x in b_other:
                b_prob[x] = (1.0 - PB) / (b_size - 1)
        
        total = 0.0
        
        for a_card, a_p in a_prob.items():
            for b_card, b_p in b_prob.items():
                prob = a_p * b_p
                new_mask_a = mask_a ^ (1 << A.index(a_card))
                new_mask_b = mask_b ^ (1 << B.index(b_card))
                if a_card > b_card:
                    current = a_card + b_card
                else:
                    current = 0.0
                sub = dp(new_mask_a, new_mask_b)
                total += prob * (current + sub)
        
        return total
    
    initial_mask_a = (1 << N) - 1
    initial_mask_b = (1 << N) - 1
    result = dp(initial_mask_a, initial_mask_b)
    print("{0:.15f}".format(result))

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