結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:20:48
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,114 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 82,204 KB
実行使用メモリ 316,968 KB
最終ジャッジ日時 2025-03-20 21:22:18
合計ジャッジ時間 4,863 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 2 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    PA = float(input[idx]); idx +=1
    PB = float(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    B = list(map(int, input[idx:idx+N]))
    
    card_to_index_A = {a: i for i, a in enumerate(A)}
    card_to_index_B = {b: i for i, b in enumerate(B)}
    
    initial_mask = (1 << N) - 1
    
    @lru_cache(maxsize=None)
    def get_remaining_a(mask_a):
        return [a for i in range(N) if (mask_a >> i) & 1 for a in [A[i]]]
    
    @lru_cache(maxsize=None)
    def get_remaining_b(mask_b):
        return [b for i in range(N) if (mask_b >> i) & 1 for b in [B[i]]]
    
    memo = {}
    
    def dfs(mask_a, mask_b, score_diff):
        if mask_a == 0 and mask_b == 0:
            return 1.0 if score_diff > 0 else 0.0
        key = (mask_a, mask_b, score_diff)
        if key in memo:
            return memo[key]
        a_remaining = get_remaining_a(mask_a)
        b_remaining = get_remaining_b(mask_b)
        
        k_a = len(a_remaining)
        a_probs = {}
        if k_a >= 1:
            if k_a ==1:
                a_card = a_remaining[0]
                a_probs[a_card] = 1.0
            else:
                a_min = min(a_remaining)
                a_probs[a_min] = PA
                remaining_non_min = [c for c in a_remaining if c != a_min]
                prob = (1.0 - PA) / (k_a -1)
                for c in remaining_non_min:
                    a_probs[c] = prob
        else:
            a_probs = {}
        
        k_b = len(b_remaining)
        b_probs = {}
        if k_b >=1:
            if k_b ==1:
                b_card = b_remaining[0]
                b_probs[b_card] = 1.0
            else:
                b_min = min(b_remaining)
                b_probs[b_min] = PB
                remaining_non_min = [c for c in b_remaining if c != b_min]
                prob = (1.0 - PB) / (k_b -1)
                for c in remaining_non_min:
                    b_probs[c] = prob
        else:
            b_probs = {}
        
        total_p = 0.0
        if not a_probs or not b_probs:
            pass
        else:
            for a_card, p_a in a_probs.items():
                for b_card, p_b in b_probs.items():
                    a_idx = card_to_index_A[a_card]
                    new_mask_a = mask_a ^ (1 << a_idx)
                    b_idx = card_to_index_B[b_card]
                    new_mask_b = mask_b ^ (1 << b_idx)
                    a_val = a_card
                    b_val = b_card
                    if a_val > b_val:
                        new_score = score_diff + (a_val + b_val)
                    else:
                        new_score = score_diff - (a_val + b_val)
                    p = p_a * p_b
                    res = dfs(new_mask_a, new_mask_b, new_score)
                    total_p += p * res
        memo[key] = total_p
        return total_p
    
    result = dfs(initial_mask, initial_mask, 0)
    print("{0:.15f}".format(result))

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