結果

問題 No.173 カードゲーム（Medium）
ユーザー gew1fw
提出日時 2025-06-12 21:27:41
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,174 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 365,492 KB
最終ジャッジ日時 2025-06-12 21:28:34
合計ジャッジ時間 5,017 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    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

    current_dp = defaultdict(lambda: defaultdict(float))
    full_a_mask = (1 << N) - 1
    full_b_mask = (1 << N) - 1
    current_dp[(full_a_mask, full_b_mask)][0] = 1.0

    for step in range(N):
        next_dp = defaultdict(lambda: defaultdict(float))
        for (a_mask, b_mask), diffs in current_dp.items():
            for current_diff, current_prob in diffs.items():
                # Generate available_a_indices and available_a_cards
                available_a_indices = []
                available_a_cards = []
                for i in range(N):
                    if a_mask & (1 << i):
                        available_a_indices.append(i)
                        available_a_cards.append(A[i])
                # Generate available_b_indices and available_b_cards
                available_b_indices = []
                available_b_cards = []
                for i in range(N):
                    if b_mask & (1 << i):
                        available_b_indices.append(i)
                        available_b_cards.append(B[i])
                # Generate a_choices
                a_choices = []
                if len(available_a_cards) == 0:
                    continue
                if len(available_a_cards) == 1:
                    a_card = available_a_cards[0]
                    a_idx = available_a_indices[0]
                    a_choices.append((a_card, a_idx, 1.0))
                else:
                    smallest_a = min(available_a_cards)
                    count_other = len(available_a_cards) - 1
                    for i in range(len(available_a_cards)):
                        card = available_a_cards[i]
                        idx_a = available_a_indices[i]
                        if card == smallest_a:
                            prob = P_A
                        else:
                            prob = (1.0 - P_A) / count_other
                        a_choices.append((card, idx_a, prob))
                # Generate b_choices
                b_choices = []
                if len(available_b_cards) == 0:
                    continue
                if len(available_b_cards) == 1:
                    b_card = available_b_cards[0]
                    b_idx = available_b_indices[0]
                    b_choices.append((b_card, b_idx, 1.0))
                else:
                    smallest_b = min(available_b_cards)
                    count_other = len(available_b_cards) - 1
                    for i in range(len(available_b_cards)):
                        card = available_b_cards[i]
                        idx_b = available_b_indices[i]
                        if card == smallest_b:
                            prob = P_B
                        else:
                            prob = (1.0 - P_B) / count_other
                        b_choices.append((card, idx_b, prob))
                # Process all combinations of a_choices and b_choices
                for a_card, a_idx, a_prob in a_choices:
                    for b_card, b_idx, b_prob in b_choices:
                        trans_prob = a_prob * b_prob
                        new_a_mask = a_mask ^ (1 << a_idx)
                        new_b_mask = b_mask ^ (1 << b_idx)
                        if a_card > b_card:
                            new_diff = current_diff + (a_card + b_card)
                        else:
                            new_diff = current_diff - (a_card + b_card)
                        next_dp[(new_a_mask, new_b_mask)][new_diff] += current_prob * trans_prob
        current_dp = next_dp

    total = 0.0
    for (a_mask, b_mask), diffs in current_dp.items():
        if a_mask == 0 and b_mask == 0:
            for diff, prob in diffs.items():
                if diff > 0:
                    total += prob
    print("{0:.15f}".format(total))

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