結果

問題 No.174 カードゲーム（Hard）
ユーザー gew1fw
提出日時 2025-06-12 16:22:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,825 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 138,752 KB
最終ジャッジ日時 2025-06-12 16:22:50
合計ジャッジ時間 3,748 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, P_A, P_B = map(float, sys.stdin.readline().split())
    N = int(N)
    P_A = float(P_A)
    P_B = float(P_B)
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    A.sort()
    B.sort()

    @lru_cache(maxsize=None)
    def dp(a_tuple, b_tuple):
        a_list = list(a_tuple)
        b_list = list(b_tuple)
        if not a_list or not b_list:
            return 0.0
        a_len = len(a_list)
        b_len = len(b_list)
        
        a_smallest = a_list[0]
        a_prob = {}
        if a_len == 1:
            a_prob[a_smallest] = 1.0
        else:
            a_prob[a_smallest] = P_A
            other_prob = (1.0 - P_A) / (a_len - 1)
            for a in a_list[1:]:
                a_prob[a] = other_prob
        
        b_smallest = b_list[0]
        b_prob = {}
        if b_len == 1:
            b_prob[b_smallest] = 1.0
        else:
            b_prob[b_smallest] = P_B
            other_prob = (1.0 - P_B) / (b_len - 1)
            for b in b_list[1:]:
                b_prob[b] = other_prob
        
        total = 0.0
        for a in a_list:
            pa = a_prob[a]
            for b in b_list:
                pb = b_prob[b]
                prob = pa * pb
                contrib = (a + b) * (a > b) * prob
                total += contrib
                new_a = tuple(x for x in a_list if x != a)
                new_b = tuple(x for x in b_list if x != b)
                next_val = dp(new_a, new_b)
                total += prob * next_val
        return total

    a_initial = tuple(sorted(A))
    b_initial = tuple(sorted(B))
    result = dp(a_initial, b_initial)
    print("{0:.15f}".format(result))

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