はじめに
こんにちは！競技プログラミングをやっている高校生のButterFlvです！
問題の問題（ABC372-F）
間違い等あればコメントやTwitterのDMにお願いします
InlineDPとは
InlineDPとはDPをするときに、その結果を記録している配列が操作によって一部しか変更がないときに、同じ配列を使いまわすことによって時間・空間計算量を落とすテクニックです。
最も有名な例だと、最長増加部分列を求めるアルゴリズム（LIS）とかになります。
本題
この記事で書きたいのは僕が陥ってコンテスト中に問題をACできなかった原因になったInlineDPの落とし穴です。また、そこから言えるInlineでないDPにおいて、Inlineでないことから起こるやりがちなミスも書きたいと思います。
InlineDPでDPに使う部分を並行して更新するべからず
InlineDPではほとんどの場合
- $\mathrm{dp}[i][j]=\mathrm{process}(\mathrm{dp}[i-1][0],\mathrm{dp}[i-1][1],\ldots ,\mathrm{dp}[i-1][N-1])$
を
- $\mathrm{dp}[i]=\mathrm{process}(\mathrm{dp}[0],\mathrm{dp}[1],\ldots ,\mathrm{dp}[N-1])$ ・・・①
のように変更することになります。
しかし、ここで安易に①を $i=0,1,\ldots ,N-1$ の順にやってしまったりすると右辺の項にすでにそのループで更新済みのものが出てきてしまうため計算結果が不正になってしまいます。
改善する方法としては、以下の方法などがあります。
- dpの操作を行った後に、実際に変化した項のみを別の配列で持っておいて操作をすべて終えた後に $\mathrm{dp}$ を更新する
- 更新に自明な順序が存在するときはその順で更新していく（降順など）
逆に、Inlineじゃないときの注意点
InlineDPの注意点を考えたときにInlineじゃないDPで気を付けなければならないことを思い出したので書いていきます。
配列のコピーを忘れるべからず
$\mathrm{dp}[i-1][j]$ から $\mathrm{dp}[i][j]$ への変更が必要ないとき、$\mathrm{dp}[i-1][j]$ が初期値のままになっていて計算結果が不正になっていたことはありませんか？（思い返してみれば僕は結構やってしまっているなと思いました。）
対策は、
- DPの本計算を行う前に一周走査してコピーしておく
とかでしょうか。（２倍の定数倍がつくかも。。。）
さいごに
解法があっているのにACできないのは本当に悲しいので未然に防ぐ意識を持ちたいです。