結果

問題 No.174 カードゲーム（Hard）
ユーザー gew1fw
提出日時 2025-06-12 14:18:02
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,212 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 856,992 KB
最終ジャッジ日時 2025-06-12 14:18:07
合計ジャッジ時間 4,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input_line = sys.stdin.readline().split()
    N = int(input_line[0])
    P_A = float(input_line[1])
    P_B = float(input_line[2])
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

    sorted_A = sorted(A)
    sorted_B = sorted(B)

    def compute_probs(sorted_cards, P):
        n = len(sorted_cards)
        card_to_index = {card: i for i, card in enumerate(sorted_cards)}
        prob = [[0.0] * (n + 1) for _ in range(n)]

        queue = deque()
        queue.append((tuple(sorted_cards), 1.0))

        while queue:
            remaining, curr_prob = queue.popleft()
            m = len(remaining)
            if m == 0:
                continue
            t = (n - m) + 1
            if m == 1:
                card = remaining[0]
                idx = card_to_index[card]
                prob[idx][t] += curr_prob
                continue

            min_card = remaining[0]
            idx_min = card_to_index[min_card]
            prob_min = P
            new_remaining_min = remaining[1:]
            prob[idx_min][t] += curr_prob * prob_min
            queue.append((new_remaining_min, curr_prob * prob_min))

            other_prob = (1 - P) / (m - 1)
            for i in range(1, m):
                card = remaining[i]
                idx = card_to_index[card]
                prob_curr = curr_prob * other_prob
                prob[idx][t] += prob_curr
                new_rem = remaining[:i] + remaining[i+1:]
                queue.append((tuple(new_rem), prob_curr))
        return prob

    prob_A = compute_probs(sorted_A, P_A)
    prob_B = compute_probs(sorted_B, P_B)

    a_index = {card: i for i, card in enumerate(sorted_A)}
    b_index = {card: i for i, card in enumerate(sorted_B)}

    total = 0.0
    for a in A:
        a_idx = a_index[a]
        for b in B:
            if a > b:
                b_idx = b_index[b]
                for t in range(1, N + 1):
                    pa = prob_A[a_idx][t]
                    pb = prob_B[b_idx][t]
                    total += pa * pb * (a + b)

    print("{0:.15f}".format(total))

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