結果

問題 No.174 カードゲーム（Hard）
ユーザー lam6er
提出日時 2025-03-31 17:52:13
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,927 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 280,964 KB
最終ジャッジ日時 2025-03-31 17:52:52
合計ジャッジ時間 3,774 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    # Read input
    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]))
    
    sorted_A = sorted(A)
    sorted_B = sorted(B)
    
    # Process player A's P_A probabilities
    P_A = defaultdict(lambda: defaultdict(float))
    dp_a = [defaultdict(float) for _ in range(N+2)]
    initial_mask = (1 << N) - 1
    dp_a[1][initial_mask] = 1.0
    
    for step in range(1, N+1):
        current_dp = dp_a[step]
        next_dp = defaultdict(float)
        for mask, prob in current_dp.items():
            if prob == 0.0:
                continue
            # Find minimal card in the mask
            if mask == 0:
                continue
            lsb = mask & -mask
            min_idx = (lsb).bit_length() -1
            min_card = sorted_A[min_idx]
            
            # Collect all indices present in the mask
            present_indices = []
            temp_mask = mask
            while temp_mask:
                lsb_i = temp_mask & -temp_mask
                idx_i = (lsb_i).bit_length() -1
                present_indices.append(idx_i)
                temp_mask ^= lsb_i
            
            size_mask = len(present_indices)
            for card_idx in present_indices:
                c = sorted_A[card_idx]
                if size_mask ==1:
                    prob_choose = 1.0
                else:
                    if c == min_card:
                        prob_choose = PA
                    else:
                        prob_choose = (1.0 - PA) / (size_mask -1)
                
                new_mask = mask ^ (1 << card_idx)
                next_dp[new_mask] += prob * prob_choose
                P_A[c][step] += prob * prob_choose
        
        dp_a[step +1] = next_dp
    
    # Process player B's P_B probabilities
    P_B = defaultdict(lambda: defaultdict(float))
    dp_b = [defaultdict(float) for _ in range(N+2)]
    initial_mask = (1 << N) -1
    dp_b[1][initial_mask] = 1.0
    
    for step in range(1, N+1):
        current_dp = dp_b[step]
        next_dp = defaultdict(float)
        for mask, prob in current_dp.items():
            if prob ==0.0:
                continue
            if mask ==0:
                continue
            lsb = mask & -mask
            min_idx = (lsb).bit_length() -1
            min_card = sorted_B[min_idx]
            
            present_indices = []
            temp_mask = mask
            while temp_mask:
                lsb_i = temp_mask & -temp_mask
                idx_i = (lsb_i).bit_length() -1
                present_indices.append(idx_i)
                temp_mask ^= lsb_i
            
            size_mask = len(present_indices)
            for card_idx in present_indices:
                c = sorted_B[card_idx]
                if size_mask ==1:
                    prob_choose =1.0
                else:
                    if c == min_card:
                        prob_choose = PB
                    else:
                        prob_choose = (1.0 - PB)/ (size_mask -1)
                
                new_mask = mask ^ (1 << card_idx)
                next_dp[new_mask] += prob * prob_choose
                P_B[c][step] += prob * prob_choose
        
        dp_b[step +1] = next_dp
    
    # Calculate expected value
    expected =0.0
    for a in A:
        for b in B:
            if a > b:
                total =0.0
                for k in range(1, N+1):
                    pa = P_A[a].get(k, 0.0)
                    pb = P_B[b].get(k, 0.0)
                    total += pa * pb
                expected += (a + b) * total
    
    # Format the output with sufficient precision
    print("{0:.15f}".format(expected))

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