DP I
コインが何枚かあり、それぞれの表になる確率が与えられる、表の枚数が裏より多くなる確率を求める問題
先頭からコインを見て行った時に、表である枚数を定義域とし、その確率を値とするDP
from 動的計画法
Python TLE PyPy AC
pythondef solve(N, probs):
m = [0.0] * (N + 1)
m[0] = 1.0
for i in range(N):
n = [0.0] * (N + 1)
for j in range(N):
n[j + 1] += m[j] * probs[i]
for j in range(N + 1):
n[j] += m[j] * (1 - probs[i])
m = n
return sum(m[N // 2 + 1:])Related Pages
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]