結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:33:09
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,821 bytes
コンパイル時間 504 ms
コンパイル使用メモリ 81,688 KB
実行使用メモリ 399,660 KB
最終ジャッジ日時 2025-04-16 16:34:16
合計ジャッジ時間 5,255 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque
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

    A_idx = {a: i for i, a in enumerate(A)}
    B_idx = {b: i for i, b in enumerate(B)}

    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1

    dp = dict()
    dp[(initial_a_mask, initial_b_mask, 0)] = 1.0

    queue = deque()
    queue.append((initial_a_mask, initial_b_mask, 0))

    result = 0.0

    while queue:
        a_mask, b_mask, score_diff = queue.popleft()
        current_prob = dp.pop((a_mask, b_mask, score_diff), 0.0)
        if current_prob == 0:
            continue

        a_remaining = bin(a_mask).count('1')
        b_remaining = bin(b_mask).count('1')
        if a_remaining == 0:
            if score_diff > 0:
                result += current_prob
            continue

        max_possible = a_remaining * 2000
        min_possible = -max_possible
        if score_diff + max_possible <= 0:
            continue
        if score_diff - max_possible > 0:
            result += current_prob
            continue

        a_cards = []
        for i in range(N):
            if a_mask & (1 << i):
                a_cards.append(A[i])
        a_min = min(a_cards)
        a_min_i = A_idx[a_min]

        b_cards = []
        for i in range(N):
            if b_mask & (1 << i):
                b_cards.append(B[i])
        b_min = min(b_cards)
        b_min_i = B_idx[b_min]

        if len(a_cards) == 1:
            prob_a_min = 1.0
        else:
            prob_a_min = P_A

        if len(b_cards) == 1:
            prob_b_min = 1.0
        else:
            prob_b_min = P_B

        new_a_mask_case1 = a_mask ^ (1 << a_min_i)
        new_b_mask_case1 = b_mask ^ (1 << b_min_i)
        delta = (a_min > b_min) * (a_min + b_min) - (a_min <= b_min) * (a_min + b_min)
        new_score = score_diff + delta
        prob_case1 = current_prob * prob_a_min * prob_b_min
        key = (new_a_mask_case1, new_b_mask_case1, new_score)
        if key in dp:
            dp[key] += prob_case1
        else:
            dp[key] = prob_case1
            queue.append(key)

        if len(b_cards) > 1:
            prob_b_non = (1 - prob_b_min) / (len(b_cards) - 1)
            for b in b_cards:
                if b == b_min:
                    continue
                b_i = B_idx[b]
                new_b_mask = b_mask ^ (1 << b_i)
                delta = (a_min > b) * (a_min + b) - (a_min <= b) * (a_min + b)
                new_score = score_diff + delta
                prob = current_prob * prob_a_min * prob_b_non
                key = (new_a_mask_case1, new_b_mask, new_score)
                if key in dp:
                    dp[key] += prob
                else:
                    dp[key] = prob
                    queue.append(key)

        if len(a_cards) > 1:
            prob_a_non = (1 - prob_a_min) / (len(a_cards) - 1)
            for a in a_cards:
                if a == a_min:
                    continue
                a_i = A_idx[a]
                new_a_mask = a_mask ^ (1 << a_i)
                new_b_mask_case3 = b_mask ^ (1 << b_min_i)
                delta = (a > b_min) * (a + b_min) - (a <= b_min) * (a + b_min)
                new_score = score_diff + delta
                prob = current_prob * prob_a_non * prob_b_min
                key = (new_a_mask, new_b_mask_case3, new_score)
                if key in dp:
                    dp[key] += prob
                else:
                    dp[key] = prob
                    queue.append(key)

        if len(a_cards) > 1 and len(b_cards) > 1:
            prob_a_non = (1 - prob_a_min) / (len(a_cards) - 1)
            prob_b_non = (1 - prob_b_min) / (len(b_cards) - 1)
            for a in a_cards:
                if a == a_min:
                    continue
                a_i = A_idx[a]
                new_a_mask = a_mask ^ (1 << a_i)
                for b in b_cards:
                    if b == b_min:
                        continue
                    b_i = B_idx[b]
                    new_b_mask = b_mask ^ (1 << b_i)
                    delta = (a > b) * (a + b) - (a <= b) * (a + b)
                    new_score = score_diff + delta
                    prob = current_prob * prob_a_non * prob_b_non
                    key = (new_a_mask, new_b_mask, new_score)
                    if key in dp:
                        dp[key] += prob
                    else:
                        dp[key] = prob
                        queue.append(key)

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

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