ABC179D
しばらく悩んで、飛ばしてEへ
悩み「え、これ範囲が広いと困るのでは？」←正しい
素朴にメモ化再帰DPで書いてみて案の定TLE
小さい方からループで塗りつぶすDPにしてもTLE
でもそのコードを見て「あ、要するにこの最内ループを潰せばいいんだな」と気づく
少し綺麗にしたコード
pythondef solve(N, K, SS):
count = [0] * (N + 10)
count[0] = 1
accum = [0] * (N + 10)
accum[0] = 1
for pos in range(1, N):
ret = 0
for left, right in SS:
start = pos - right - 1
end = pos - left
ret += (accum[end] - accum[start])
ret %= MOD
count[pos] = ret
accum[pos] = accum[pos - 1] + ret
ret = count[N - 1]
return ret % MODTwitter見てたら「いもす法だ」とか言ってる人がいたけど、そうかな。僕はそういう意識はなかった。
DPの計算をする上で範囲の和を計算する部分が、範囲が広い時に「たくさんの数を足し合わせる」になって遅いのが解決すべき問題
そこで「今までに計算した数の和」の配列を別途作ってやる
これは「新しい値を前の値に足す」で作れる
これを累積和と言ってる
いざ広い範囲の和が必要になった時には、範囲終了点での累積和から範囲開始点の一つ手前の累積和を引けば得られる
Twitter見てたらセグメント木だと言ってる人もいる
セグメント木は範囲和がO(logN)なので、ループで回して和を計算するO(N)よりは速くなる
今回使った累積和はO(1)なのでさらに速い
累積和は先頭からしか値を入れられないが、セグメント木では任意の位置に入れられる。この柔軟性の分だけ遅いと言えるだろう。
今回は先頭からDPするので任意位置に入れられる必要はなかった。