結果

問題 No.173 カードゲーム（Medium）
ユーザー lam6er
提出日時 2025-04-16 00:06:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,251 bytes
コンパイル時間 478 ms
コンパイル使用メモリ 81,408 KB
実行使用メモリ 274,084 KB
最終ジャッジ日時 2025-04-16 00:07:47
合計ジャッジ時間 4,937 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    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]))
    idx += N

    A_sorted = tuple(sorted(A))
    B_sorted = tuple(sorted(B))

    @lru_cache(maxsize=None)
    def dfs(a_cards, b_cards, score_diff):
        if len(a_cards) == 0:
            return 1.0 if score_diff > 0 else 0.0
        
        a_list = list(a_cards)
        b_list = list(b_cards)
        
        # Calculate probabilities for A's choices
        a_min = a_list[0]
        kA = len(a_list)
        a_probs = {}
        if kA == 1:
            a_probs[a_min] = 1.0
        else:
            a_probs[a_min] = PA
            other_prob = (1.0 - PA) / (kA - 1)
            for card in a_list[1:]:
                a_probs[card] = other_prob
        
        # Calculate probabilities for B's choices
        b_min = b_list[0]
        kB = len(b_list)
        b_probs = {}
        if kB == 1:
            b_probs[b_min] = 1.0
        else:
            b_probs[b_min] = PB
            other_prob = (1.0 - PB) / (kB - 1)
            for card in b_list[1:]:
                b_probs[card] = other_prob
        
        total = 0.0
        for a_card, a_p in a_probs.items():
            for b_card, b_p in b_probs.items():
                new_score = score_diff
                if a_card > b_card:
                    new_score += (a_card + b_card)
                else:
                    new_score -= (a_card + b_card)
                
                new_a = [x for x in a_list if x != a_card]
                new_a.sort()
                new_a_tuple = tuple(new_a)
                
                new_b = [x for x in b_list if x != b_card]
                new_b.sort()
                new_b_tuple = tuple(new_b)
                
                prob = dfs(new_a_tuple, new_b_tuple, new_score)
                total += a_p * b_p * prob
        
        return total

    result = dfs(A_sorted, B_sorted, 0)
    print("{0:.15f}".format(result))

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