結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:41:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,554 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 858,888 KB
最終ジャッジ日時 2025-06-12 14:41:46
合計ジャッジ時間 4,994 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache
import itertools

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 = sorted(A)
    B = sorted(B)
    
    # Precompute for each subset of A's cards, the probability distribution
    # Similarly for B's subsets
    
    # For A:
    a_size = len(A)
    a_subsets = []
    for mask in range(1 << a_size):
        subset = []
        for i in range(a_size):
            if (mask >> i) & 1:
                subset.append(A[i])
        a_subsets.append(subset)
    
    a_probs = [{} for _ in range(1 << a_size)]
    for mask in range(1 << a_size):
        subset = a_subsets[mask]
        if not subset:
            continue
        k = len(subset)
        if k == 1:
            a_probs[mask][subset[0]] = 1.0
        else:
            min_a = min(subset)
            prob_min = P_A
            others = [x for x in subset if x != min_a]
            other_prob = (1 - P_A) / (k - 1) if (k - 1) != 0 else 0.0
            a_probs[mask][min_a] = prob_min
            for x in others:
                a_probs[mask][x] = other_prob
    
    # For B:
    b_size = len(B)
    b_subsets = []
    for mask in range(1 << b_size):
        subset = []
        for i in range(b_size):
            if (mask >> i) & 1:
                subset.append(B[i])
        b_subsets.append(subset)
    
    b_probs = [{} for _ in range(1 << b_size)]
    for mask in range(1 << b_size):
        subset = b_subsets[mask]
        if not subset:
            continue
        k = len(subset)
        if k == 1:
            b_probs[mask][subset[0]] = 1.0
        else:
            min_b = min(subset)
            prob_min = P_B
            others = [x for x in subset if x != min_b]
            other_prob = (1 - P_B) / (k - 1) if (k - 1) != 0 else 0.0
            b_probs[mask][min_b] = prob_min
            for x in others:
                b_probs[mask][x] = other_prob
    
    # Precompute card values for A and B, and their indices for masks
    A_indices = {card: i for i, card in enumerate(A)}
    B_indices = {card: i for i, card in enumerate(B)}
    
    @lru_cache(maxsize=None)
    def dp(A_mask, B_mask, diff):
        if A_mask == 0 and B_mask == 0:
            return 1.0 if diff > 0 else 0.0
        
        total = 0.0
        a_sub = a_subsets[A_mask]
        b_sub = b_subsets[B_mask]
        if not a_sub or not b_sub:
            return 0.0  # invalid state
        
        a_p = a_probs[A_mask]
        b_p = b_probs[B_mask]
        
        for a_val, a_prob in a_p.items():
            a_idx = A_indices[a_val]
            new_A_mask = A_mask & ~(1 << a_idx)
            for b_val, b_prob in b_p.items():
                b_idx = B_indices[b_val]
                new_B_mask = B_mask & ~(1 << b_idx)
                
                if a_val > b_val:
                    new_diff = diff + (a_val + b_val)
                elif a_val < b_val:
                    new_diff = diff - (a_val + b_val)
                else:
                    new_diff = diff
                
                total += a_prob * b_prob * dp(new_A_mask, new_B_mask, new_diff)
        
        return total
    
    initial_A_mask = (1 << a_size) - 1
    initial_B_mask = (1 << b_size) - 1
    result = dp(initial_A_mask, initial_B_mask, 0.0)
    print("{0:.15f}".format(result))

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