20211213 JOI 2021/2022 二次予選 D 「飴 2 (Candies 2)」
なぜ
正直書くかどうかは迷ったんですが（公式解説とほぼ同じなので）、思考過程だけでも残しておこうと思ったので書きました
DP は大の苦手なので、後から「過去の自分、どんな天才をしたらこれを思いつけたんだ……？」みたいに何もわからなくなりそう
問題ページ
小課題 $3$
$3$ 次元 DP をしろと制約が訴えかけてくるので DP を組みます。
$\mathrm{dp}[i][j][k]:=i$ 番目まで見て、最後に取った飴が $j$、最後から $2$ 番目に取ったのが $k$ のときのおいしさの合計の最大値
とします。便宜上、$j$ または $k$ が $0$ であるときは、それをまだ取っていないことを指すことにします。
配る DP 的な感じで書くと、
$$ \mathrm{dp}[i + 1][i + 1][j] = \max(\mathrm{dp}[i + 1][i + 1][j], \mathrm{dp}[i][j][k] + a[i]) $$
$$ \mathrm{dp}[j][k] = \max(\mathrm{dp}[i + 1][j][k], \mathrm{dp}[i][j][k]) $$
みたいな遷移が出来上がります。
満点解法
ここで、DP テーブルを出力させてみました。すると、こんなものが出てきました。
直感します。「$i$ の情報要らなくね？」
ということで DP を組みなおします。
$\mathrm{dp}[i][j]:=$ 最後に取った飴が $i$、最後から $2$ 番目に取ったのが $j$ のときのおいしさの合計の最大値
とします。今度は貰う DP で考えてみます。
いま、$\mathrm{dp}[i][j]$ を更新しようとしているとします。$i$ 番目の飴を取るとき注目すべきは、$\mathrm{dp}[j][*]$ です。$i$ との距離が $K$ 以上である必要があるので、$\mathrm{dp}[j][i-K]$ 以左からしか遷移できません。よって、
$$ \mathrm{dp}[i][j] = \max_{k=0}^{\max(0,i-K)} \mathrm{dp}[j][k] + a[i] $$
これは愚直にやるとまだ $\Theta(N^3)$ かかってキツいですが、DP テーブルの累積 max を取ってあげると高速に処理できます。
よって、この問題を $\Theta(N^2)$ で解くことが出来ました。
AC コード
感想
DP が大の苦手だったんですが、DP テーブルとにらめっこしていたら解けて嬉しい（添え字ガチャに成功）
難易度 7 はあるし、あっとこなら青 diff はあると思います（主張）
おわりに
C, D をどちらも通せたのでよかった……と思ったら 416 点が多すぎた
A ランクの基準点が出たら参加記も書きます
