AtCoder 🟢 AT_dp_i Coins

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 AT_dp_i Coins

Problem Statement

題目簡述

有 $N$ 枚硬幣（$N$ 為奇數），第 $i$ 枚硬幣投擲出正面的機率為 $p_i$。

求投擲所有硬幣後，正面出現的次數嚴格多於反面出現次數的機率。

Constraints

約束條件

• $N$ 是奇數且 $1 \le N \le 2999$。
• $0 < p_i < 1$。

---

思路：機率 DP

狀態定義

定義 $dp[i][j]$ 為投擲前 $i$ 枚硬幣後，恰好有 $j$ 枚為正面的機率。

狀態轉移

考慮第 $i$ 枚硬幣的結果：

• 正面（機率 $p_i$）：需從 $dp[i-1][j-1]$ 轉移，貢獻 $dp[i-1][j-1] \times p_i$。
• 反面（機率 $1-p_i$）：需從 $dp[i-1][j]$ 轉移，貢獻 $dp[i-1][j] \times (1-p_i)$。

狀態轉移方程

$$dp[i][j] = dp[i-1][j] \cdot (1 - p_i) + dp[i-1][j-1] \cdot p_i$$

空間優化

由於 $dp[i]$ 只依賴 $dp[i-1]$，可使用滾動陣列優化空間。程式碼中以 defaultdict 實作：

• f：儲存上一輪的機率分佈
• nf：計算當前輪的機率分佈

答案計算

最終答案為正面數嚴格多於反面數的機率總和，即 $j > N - j \Rightarrow j > \frac{N}{2}$：

$$\text{Ans} = \sum_{j = \lfloor N/2 \rfloor + 1}^{N} dp[N][j]$$

複雜度分析

• 時間複雜度：$\mathcal{O}(N^2)$
• 空間複雜度：$\mathcal{O}(N)$

---

Code

from collections import defaultdict

def solve():
    n = int(input())
    P = list(map(float, input().split()))

    # f[i][j] 表示考慮前 i 個硬幣，得到 j 個正面的機率
    f = defaultdict(float)
    f[0] = 1
    for p in P:
        nf = defaultdict(float)
        for j, q in f.items():
            nf[j + 1] += q * p
            nf[j] += q * (1 - p)
        f = nf
    print(sum(q for j, q in f.items() if j > n - j))

if __name__ == "__main__":
    solve()