結果

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

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    P_A = float(input[ptr])
    ptr += 1
    P_B = float(input[ptr])
    ptr += 1
    
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+N]))
    ptr += N

    # Precompute the index for each card for A and B
    a_index = {card: idx for idx, card in enumerate(A)}
    b_index = {card: idx for idx, card in enumerate(B)}

    # Precompute the probability for each subset for A and B
    a_subsets = {}
    for mask in range(1 << N):
        cards = [A[i] for i in range(N) if (mask & (1 << i))]
        if not cards:
            continue
        a_subsets[mask] = compute_probabilities(cards, P_A, a_index)
    
    b_subsets = {}
    for mask in range(1 << N):
        cards = [B[i] for i in range(N) if (mask & (1 << i))]
        if not cards:
            continue
        b_subsets[mask] = compute_probabilities(cards, P_B, b_index)
    
    @lru_cache(maxsize=None)
    def dfs(a_mask, b_mask, d):
        if a_mask == 0 and b_mask == 0:
            return 1.0 if d > 0 else 0.0
        
        total = 0.0
        
        a_cards = [A[i] for i in range(N) if (a_mask & (1 << i))]
        a_probs = a_subsets.get(a_mask, {})
        
        b_cards = [B[i] for i in range(N) if (b_mask & (1 << i))]
        b_probs = b_subsets.get(b_mask, {})
        
        for a_card, p_a in a_probs.items():
            a_idx = a_index[a_card]
            new_a_mask = a_mask ^ (1 << a_idx)
            
            for b_card, p_b in b_probs.items():
                b_idx = b_index[b_card]
                new_b_mask = b_mask ^ (1 << b_idx)
                
                if a_card > b_card:
                    new_d = d + (a_card + b_card)
                elif b_card > a_card:
                    new_d = d - (a_card + b_card)
                else:
                    new_d = d
                
                prob = p_a * p_b * dfs(new_a_mask, new_b_mask, new_d)
                total += prob
        
        return total

    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1
    result = dfs(initial_a_mask, initial_b_mask, 0)
    print("{0:.15f}".format(result).rstrip('0').rstrip('.') if '.' in "{0:.15f}".format(result) else "{0:.15f}".format(result))

def compute_probabilities(cards, P, index):
    if len(cards) == 1:
        return {cards[0]: 1.0}
    else:
        min_card = min(cards)
        prob_min = P
        others = [c for c in cards if c != min_card]
        other_prob = (1 - P) / len(others) if others else 0.0
        prob = {}
        prob[min_card] = prob_min
        for c in others:
            prob[c] = other_prob
        return prob

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