結果

問題 No.173 カードゲーム（Medium）
ユーザー lam6er
提出日時 2025-03-31 17:54:10
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,141 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 274,288 KB
最終ジャッジ日時 2025-03-31 17:55:58
合計ジャッジ時間 4,847 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    N, PA, PB = 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()))
    
    sorted_a = tuple(sorted(A))
    sorted_b = tuple(sorted(B))
    
    @lru_cache(maxsize=None)
    def dfs(a_remaining, b_remaining, diff):
        if len(a_remaining) == 0 and len(b_remaining) == 0:
            return 1.0 if diff > 0 else 0.0
        
        total_prob = 0.0
        
        a_list = list(a_remaining)
        b_list = list(b_remaining)
        
        # Compute probabilities for A's choices
        a_probs = {}
        a_size = len(a_list)
        if a_size >= 1:
            if a_size == 1:
                a_probs[a_list[0]] = 1.0
            else:
                a_probs[a_list[0]] = PA
                other_prob = (1 - PA) / (a_size - 1)
                for a in a_list[1:]:
                    a_probs[a] = other_prob
        
        # Compute probabilities for B's choices
        b_probs = {}
        b_size = len(b_list)
        if b_size >= 1:
            if b_size == 1:
                b_probs[b_list[0]] = 1.0
            else:
                b_probs[b_list[0]] = PB
                other_prob_b = (1 - PB) / (b_size - 1)
                for b in b_list[1:]:
                    b_probs[b] = other_prob_b
        
        # Generate all possible pairs (a, b)
        for a in a_list:
            pa = a_probs.get(a, 0.0)
            if pa <= 0:
                continue
            new_a = tuple(x for x in a_list if x != a)
            for b in b_list:
                pb = b_probs.get(b, 0.0)
                if pb <= 0:
                    continue
                new_diff = diff + (a + b) if a > b else diff - (a + b)
                new_b = tuple(y for y in b_list if y != b)
                prob = dfs(new_a, new_b, new_diff)
                total_prob += pa * pb * prob
        
        return total_prob
    
    result = dfs(sorted_a, sorted_b, 0)
    print("{0:.12f}".format(result))

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