結果
問題 |
No.66 輝け☆全国たこやき杯
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()