[Python] 累積和 ABC179D

#ABC179D
素朴な解法としては、

dp[i]:= マスiに到達するまでの操作列の個数

として、各場所 i についてすべての移動を試す動的計画法が考えられるが、時間計算量 $O(N^2)$ となります。更新式は次の通り。

dp[i] = \sum_{v\in S} dp[i-v] \\

こんなときは累積和を用いて DP 高速化するのは定番ではある。まず、集合 S が K 個の区間からなることに着目すると、$\sum_{v\in S} dp[i-v]$ の部分は、K 個の区間についての「区間内の総和」を足し上げたものになることがわかる。
ここで一般に、配列 a の累積和を s としたとき、配列 a の区間 [l, r) の総和は s[r] - s[l] で表せることを思い出そう。よって配列 dp の累積和を sumdp とすると、更新式は次のように変形できる。

dp[i] = \sum_{k=1}^K (sumdp[i-l_k+1]-sumdp[i-r_k]) \\

計算量は$O(NK)$となる。

（参考）累積和を何も考えずに書けるようにする！

サンプルコード

MOD = 998244353
N, K = map(int, input().split()) #Nはマス目の数、Kは区間の数(Kは10以下)
sec = [tuple(map(int, input().split())) for _ in range(K)]

dp = [0] * (N+1)
dp[1] = 1

sumdp = [0] * (N+1)
# i-l=1(現在いるマス)になったとき、dp[i]を1増やす
sumdp[1] = 1

# i=2からNまで順番にsumdp[i]を更新する
for i in range(2, N+1):
    # それぞれの区間で累積和sumdpによってdp[i]を更新する
    for l, r in sec:
        li = max(i - l, 0)
        ri = max(i - r - 1, 0)

        dp[i] += sumdp[li] - sumdp[ri]
        dp[i] %= MOD

    sumdp[i] = sumdp[i-1] + dp[i]

print(dp[N])