結果

問題 No.174 カードゲーム（Hard）
ユーザー lam6er
提出日時 2025-04-16 16:30:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,237 bytes
コンパイル時間 434 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 173,708 KB
最終ジャッジ日時 2025-04-16 16:32:12
合計ジャッジ時間 3,963 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    PA = float(input[idx]); idx +=1
    PB = 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)
    a_index = {a: i for i, a in enumerate(A_sorted)}
    b_index = {b: i for i, b in enumerate(B_sorted)}

    initial_maskA = (1 << N) - 1
    initial_maskB = (1 << N) - 1

    @lru_cache(maxsize=None)
    def dfs(maskA, maskB):
        if maskA == 0 or maskB == 0:
            return 0.0
        a_min_pos = (maskA & -maskA).bit_length() - 1
        a_min = A_sorted[a_min_pos]
        kA = bin(maskA).count('1')
        b_min_pos = (maskB & -maskB).bit_length() - 1
        b_min = B_sorted[b_min_pos]
        kB = bin(maskB).count('1')

        prob_a_min = PA if kA > 1 else 1.0
        prob_b_min = PB if kB > 1 else 1.0

        res = 0.0

        new_maskA_case1 = maskA ^ (1 << a_min_pos)
        new_maskB_case1 = maskB ^ (1 << b_min_pos)
        score1 = (a_min + b_min) if a_min > b_min else 0
        res += prob_a_min * prob_b_min * (score1 + dfs(new_maskA_case1, new_maskB_case1))

        if kB > 1:
            total = 0.0
            cnt = 0
            for b_pos in range(N):
                if (maskB & (1 << b_pos)) and b_pos != b_min_pos:
                    b = B_sorted[b_pos]
                    new_maskB_ = maskB ^ (1 << b_pos)
                    score = (a_min + b) if a_min > b else 0
                    total += score + dfs(new_maskA_case1, new_maskB_)
                    cnt += 1
            if cnt > 0:
                res += prob_a_min * (1 - prob_b_min) * (total / cnt)

        if kA > 1:
            total = 0.0
            cnt = 0
            for a_pos in range(N):
                if (maskA & (1 << a_pos)) and a_pos != a_min_pos:
                    a = A_sorted[a_pos]
                    new_maskA_ = maskA ^ (1 << a_pos)
                    score = (a + b_min) if a > b_min else 0
                    total += score + dfs(new_maskA_, new_maskB_case1)
                    cnt += 1
            if cnt > 0:
                res += (1 - prob_a_min) * prob_b_min * (total / cnt)

        if kA > 1 and kB > 1:
            total = 0.0
            cnt = 0
            for a_pos in range(N):
                if (maskA & (1 << a_pos)) and a_pos != a_min_pos:
                    a = A_sorted[a_pos]
                    for b_pos in range(N):
                        if (maskB & (1 << b_pos)) and b_pos != b_min_pos:
                            b = B_sorted[b_pos]
                            new_maskA_ = maskA ^ (1 << a_pos)
                            new_maskB_ = maskB ^ (1 << b_pos)
                            score = (a + b) if a > b else 0
                            total += score + dfs(new_maskA_, new_maskB_)
                            cnt += 1
            if cnt > 0:
                res += (1 - prob_a_min) * (1 - prob_b_min) * (total / cnt)

        return res

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

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