以下のようなDPを考えます。

\(DP[i][j]=i\) 駅目まで見て、現在 \(j\) 駅連続で採用しているような方法の個数

遷移は以下の通りです。

\(DP[i+1][0]=\sum_{k=0}^{K}DP[i][k]\)

\(DP[i+1][j]=DP[i][j-1](1\leq j\leq K)\)

ナイーブな実装では \(O(NK)\) となり明らかに間に合いませんが、DPテーブルを使いまわすことを考えると、これは

• 先頭にDPテーブルの総和を挿入し、DPテーブルの末尾を削除する

と解釈することができるので、総和を持ちながらDequeを使用することで \(O(N)\) で処理できます。

実装例(PyPy3,120ms)