結果

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

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    P_A = float(input[idx])
    idx += 1
    P_B = float(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+n]))
    idx += n
    B = list(map(int, input[idx:idx+n]))
    idx += n

    A_sorted = sorted(A)
    B_sorted = sorted(B)

    @lru_cache(maxsize=None)
    def dfs(mask_a, mask_b):
        if mask_a == 0 or mask_b == 0:
            return 0.0

        # Get a_min
        a_min_pos = (mask_a & -mask_a).bit_length() - 1
        a_min = A_sorted[a_min_pos]
        k_a = bin(mask_a).count('1')

        # Get b_min
        b_min_pos = (mask_b & -mask_b).bit_length() - 1
        b_min = B_sorted[b_min_pos]
        k_b = bin(mask_b).count('1')

        # Calculate probabilities for A
        if k_a == 1:
            prob_a_min = 1.0
            prob_a_other = 0.0
        else:
            prob_a_min = P_A
            prob_a_other = (1.0 - P_A) / (k_a - 1)

        # Calculate probabilities for B
        if k_b == 1:
            prob_b_min = 1.0
            prob_b_other = 0.0
        else:
            prob_b_min = P_B
            prob_b_other = (1.0 - P_B) / (k_b - 1)

        total = 0.0

        # Iterate over all possible choices of A
        for a_idx in range(n):
            if not (mask_a & (1 << a_idx)):
                continue
            a_val = A_sorted[a_idx]
            if a_val == a_min:
                prob_a = prob_a_min
            else:
                prob_a = prob_a_other if k_a > 1 else 0.0
            if prob_a == 0:
                continue

            # Iterate over all possible choices of B
            for b_idx in range(n):
                if not (mask_b & (1 << b_idx)):
                    continue
                b_val = B_sorted[b_idx]
                if b_val == b_min:
                    prob_b = prob_b_min
                else:
                    prob_b = prob_b_other if k_b > 1 else 0.0
                if prob_b == 0:
                    continue

                # Calculate the probability of this choice pair
                current_prob = prob_a * prob_b
                new_mask_a = mask_a & ~(1 << a_idx)
                new_mask_b = mask_b & ~(1 << b_idx)
                score = (a_val + b_val) if a_val > b_val else 0
                res = dfs(new_mask_a, new_mask_b)
                total += current_prob * (score + res)

        return total

    initial_mask_a = (1 << n) - 1
    initial_mask_b = (1 << n) - 1
    result = dfs(initial_mask_a, initial_mask_b)
    print("{0:.15f}".format(result))

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