結果

問題 No.66 輝け☆全国たこやき杯
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:43:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 109 ms / 5,000 ms
コード長 1,084 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,900 KB
実行使用メモリ 77,840 KB
最終ジャッジ日時 2025-03-20 20:44:03
合計ジャッジ時間 1,243 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)

memo = {}

def compute(start, end, S):
    if (start, end) in memo:
        return memo[(start, end)]
    if start == end:
        prob = {start: 1.0}
        memo[(start, end)] = prob
        return prob
    mid = (start + end) // 2
    left = compute(start, mid, S)
    right = compute(mid + 1, end, S)
    current = defaultdict(float)
    for i in left:
        si = S[i - 1]  # S is 0-based list
        for j in right:
            sj = S[j - 1]
            p = left[i] * right[j]
            prob_i = (si ** 2) / (si ** 2 + sj ** 2)
            prob_j = 1 - prob_i
            current[i] += p * prob_i
            current[j] += p * prob_j
    memo[(start, end)] = current
    return current

def main():
    M = int(sys.stdin.readline())
    size = 2 ** M
    S = []
    for _ in range(size):
        S.append(int(sys.stdin.readline()))
    memo.clear()
    result = compute(1, size, S)
    prob_taro = result.get(1, 0.0)
    print("{0:.7f}".format(prob_taro))

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