結果

問題 No.173 カードゲーム（Medium）
ユーザー gew1fw
提出日時 2025-06-12 19:38:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,624 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 301,964 KB
最終ジャッジ日時 2025-06-12 19:39:18
合計ジャッジ時間 4,817 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    N, P_A, P_B = map(float, sys.stdin.readline().split())
    N = int(N)
    P_A = float(P_A)
    P_B = float(P_B)
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

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

    memo = {}

    def dp(a_mask, b_mask, score_diff):
        key = (a_mask, b_mask, score_diff)
        if key in memo:
            return memo[key]
        a_remaining = bin(a_mask).count('1')
        b_remaining = bin(b_mask).count('1')
        if a_remaining == 0 and b_remaining == 0:
            memo[key] = 1.0 if score_diff > 0 else 0.0
            return memo[key]
        a_options = []
        a_cards = [i for i in range(N) if (a_mask & (1 << i))]
        if len(a_cards) == 1:
            a_options.append((a_cards[0], 1.0))
        else:
            min_a = min(a_cards, key=lambda x: A[x])
            prob_min_a = P_A
            other_prob = (1.0 - P_A) / (len(a_cards) - 1)
            for i in a_cards:
                if A[i] == A[min_a]:
                    a_options.append((i, prob_min_a))
                else:
                    a_options.append((i, other_prob))
        b_options = []
        b_cards = [i for i in range(N) if (b_mask & (1 << i))]
        if len(b_cards) == 1:
            b_options.append((b_cards[0], 1.0))
        else:
            min_b = min(b_cards, key=lambda x: B[x])
            prob_min_b = P_B
            other_prob = (1.0 - P_B) / (len(b_cards) - 1)
            for i in b_cards:
                if B[i] == B[min_b]:
                    b_options.append((i, prob_min_b))
                else:
                    b_options.append((i, other_prob))
        total_prob = 0.0
        for a_card, a_prob in a_options:
            for b_card, b_prob in b_options:
                a_val = A[a_card]
                b_val = B[b_card]
                if a_val > b_val:
                    new_diff = score_diff + (a_val + b_val)
                elif b_val > a_val:
                    new_diff = score_diff - (a_val + b_val)
                else:
                    new_diff = score_diff
                new_a_mask = a_mask & ~(1 << a_card)
                new_b_mask = b_mask & ~(1 << b_card)
                prob = a_prob * b_prob * dp(new_a_mask, new_b_mask, new_diff)
                total_prob += prob
        memo[key] = total_prob
        return total_prob

    result = dp(initial_a_mask, initial_b_mask, 0)
    print("{0:.15f}".format(result))

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