結果

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

ソースコード

diff # 

import sys
from functools import lru_cache

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

    a_index = {v: i for i, v in enumerate(A)}
    b_index = {v: i for i, v in enumerate(B)}

    @lru_cache(maxsize=None)
    def get_a_min(mask):
        for i in range(N):
            if mask & (1 << i):
                return A[i]
        return None

    @lru_cache(maxsize=None)
    def get_b_min(mask):
        for i in range(N):
            if mask & (1 << i):
                return B[i]
        return None

    @lru_cache(maxsize=None)
    def dfs(a_mask, b_mask, score_diff):
        a_remaining = bin(a_mask).count('1')
        b_remaining = bin(b_mask).count('1')
        if a_remaining == 0 and b_remaining == 0:
            return 1.0 if score_diff > 0 else 0.0

        a_min = get_a_min(a_mask)
        b_min = get_b_min(b_mask)

        a_choices = []
        a_probs = []
        if a_remaining == 1:
            a_choices = [a_min]
            a_probs = [1.0]
        elif a_remaining > 1:
            a_choices.append(a_min)
            a_probs.append(PA)
            other_count = a_remaining - 1
            other_prob = (1.0 - PA) / other_count
            for i in range(N):
                if (a_mask & (1 << i)) and A[i] != a_min:
                    a_choices.append(A[i])
                    a_probs.append(other_prob)

        b_choices = []
        b_probs = []
        if b_remaining == 1:
            b_choices = [b_min]
            b_probs = [1.0]
        elif b_remaining > 1:
            b_choices.append(b_min)
            b_probs.append(PB)
            other_count_b = b_remaining - 1
            other_prob_b = (1.0 - PB) / other_count_b
            for i in range(N):
                if (b_mask & (1 << i)) and B[i] != b_min:
                    b_choices.append(B[i])
                    b_probs.append(other_prob_b)

        total_prob = 0.0
        for a_val, a_p in zip(a_choices, a_probs):
            for b_val, b_p in zip(b_choices, b_probs):
                if a_val > b_val:
                    new_score = score_diff + (a_val + b_val)
                else:
                    new_score = score_diff - (a_val + b_val)
                a_idx = a_index[a_val]
                new_a_mask = a_mask & ~ (1 << a_idx)
                b_idx = b_index[b_val]
                new_b_mask = b_mask & ~ (1 << b_idx)
                prob = dfs(new_a_mask, new_b_mask, new_score)
                total_prob += a_p * b_p * prob

        return total_prob

    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1
    result = dfs(initial_a_mask, initial_b_mask, 0)
    print("{0:.15f}".format(result))

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