F - 準急 解説 by hirayuu_At
ユーザ解説以下のような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)
投稿日時:
最終更新: