結果

問題 No.173 カードゲーム（Medium）
ユーザー lam6er
提出日時 2025-04-16 16:35:05
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,393 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,136 KB
実行使用メモリ 326,036 KB
最終ジャッジ日時 2025-04-16 16:38:05
合計ジャッジ時間 4,721 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 2 -- * 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()))

    # Sort A and B, and create a list of sorted cards with their original indices
    sorted_A = sorted((a, i) for i, a in enumerate(A))
    sorted_B = sorted((b, i) for i, b in enumerate(B))

    # Create mappings from original index to sorted index
    a_index_map = {original_idx: sorted_idx for sorted_idx, (a, original_idx) in enumerate(sorted_A)}
    b_index_map = {original_idx: sorted_idx for sorted_idx, (b, original_idx) in enumerate(sorted_B)}

    # Convert A and B to sorted lists (values only)
    A_sorted = [a for a, i in sorted_A]
    B_sorted = [b for b, i in sorted_B]

    # Precompute the initial bitmasks (all bits set)
    initial_a_mask = (1 << N) - 1
    initial_b_mask = (1 << N) - 1

    @lru_cache(maxsize=None)
    def dfs(a_mask, b_mask, score_diff):
        if a_mask == 0 and b_mask == 0:
            return 1.0 if score_diff > 0 else 0.0

        # Get remaining cards for A and B
        a_remaining = []
        for i in range(N):
            if (a_mask >> i) & 1:
                a_remaining.append(A_sorted[i])
        a_remaining.sort()

        b_remaining = []
        for i in range(N):
            if (b_mask >> i) & 1:
                b_remaining.append(B_sorted[i])
        b_remaining.sort()

        # If one has no cards left, the other must play all remaining cards
        # But according to the problem statement, the number of matches is N, so both should have the same number of cards left at each step
        # So this situation should not occur
        # So we can proceed under the assumption that both have the same number of cards left

        # Get possible choices for A
        a_min = a_remaining[0] if a_remaining else None
        a_choices = []
        a_count = bin(a_mask).count('1')
        if a_count == 0:
            pass  # should not happen
        elif a_count == 1:
            a_choices = [a_remaining[0]]
        else:
            # Probability to choose a_min is PA
            # Others are (1-PA)/(a_count-1)
            a_choices = a_remaining.copy()

        # Get possible choices for B
        b_min = b_remaining[0] if b_remaining else None
        b_choices = []
        b_count = bin(b_mask).count('1')
        if b_count == 0:
            pass
        elif b_count == 1:
            b_choices = [b_remaining[0]]
        else:
            b_choices = b_remaining.copy()

        total_prob = 0.0

        # For A's choices
        a_probs = {}
        if a_count == 1:
            a_probs[a_remaining[0]] = 1.0
        else:
            a_min_val = a_remaining[0]
            a_probs[a_min_val] = PA
            prob_other = (1.0 - PA) / (a_count - 1)
            for val in a_remaining[1:]:
                a_probs[val] = prob_other

        # For B's choices
        b_probs = {}
        if b_count == 1:
            b_probs[b_remaining[0]] = 1.0
        else:
            b_min_val = b_remaining[0]
            b_probs[b_min_val] = PB
            prob_other = (1.0 - PB) / (b_count - 1)
            for val in b_remaining[1:]:
                b_probs[val] = prob_other

        # Iterate all possible choices for A and B
        for a_val in a_probs:
            a_prob = a_probs[a_val]
            # Find the original index of a_val in A_sorted
            a_idx = A_sorted.index(a_val)
            new_a_mask = a_mask & ~(1 << a_idx)
            for b_val in b_probs:
                b_prob = b_probs[b_val]
                # Find the original index of b_val in B_sorted
                b_idx = B_sorted.index(b_val)
                new_b_mask = b_mask & ~(1 << b_idx)
                # Compute the score difference change
                if a_val > b_val:
                    delta = a_val + b_val
                else:
                    delta = - (a_val + b_val)
                # Recursive call
                prob = a_prob * b_prob
                res = dfs(new_a_mask, new_b_mask, score_diff + delta)
                total_prob += prob * res

        return total_prob

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

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