yukicoder 1353 Limited Sequence

DPということは自明. しかし愚直にやると$$dp_{i,j,k}$$ := 条件を満たす数列のうち長さ$$i$$の数列であって要素の総和が$$j$$, 最後の要素が$$k$$であるようなものの数 となり, これは時間計算量・空間計算量ともに$$O(NR^2)$$となって間に合わない.

ここでDPで持つ情報を削減することを考える. 具体的には, $$dp_{i,j}$$ := 条件を満たす数列のうち要素の総和が$$i$$, 最後の要素が$$j$$であるようなものの数と定義してみる. すると空間計算量は$$O(NR)$$に削減できる. 時間計算量について削減することを考える. まず愚直な遷移を考えると, 累積和で高速化できるような形をしているということがわかる. また, コードの$$k$$の部分は$$O(R \log R)$$になっていることがわかる. よってこの問題を$$O(NR \log R)$$で解くことができた.

実装例: https://yukicoder.me/submissions/610670