Next DP Contest

　F以外の4点以下の問題は正解。後は部分点を拾った。もう少し取れないとまずい。

コンテストへのリンク

コンテスト後のツイート

I 大きい数字から見て、右端や左端に置くか？　で場合分け。二項係数で遷移できる。
K Aをソートしても同じ答えになるっぽい&大体連続した数になるのでは？　で部分点をもらえた。が、WAも出たので嘘か？

— titia (@titia_til) May 5, 2026

F - 集合 

　解説AC。テーマ一覧とArcAkiさんの記事を参考にしてAC。

　そもそも考察が難しい。

　最小値を使うか使わないかで考えると、その左側のみ、その右側のみ、両方を使う、で場合分けされるが、両方使う場合は最小値も必ず使わなくてはいけない。このことから、再帰を使って書けそうだと分かる。

　……という考察部分に全く気付けなかった。

　この考察通り、再帰で書こうとすると、Cartesian treeの順にやることになり、そこでは二乗の木DPを行うことになる、という流れ。

　テーマを見てしまっていたので、この考察が分かった後はすんなり書けたけれど、実際はその後の部分も簡単ではない気がする。

J - 個数と総和

　この問題と同じテーマというのを見てAC。

　「繰り上がりを持つ桁 DP」と呼ばれているのは知らなかった。

　類題をACしたときは理解していたのだろうけど、DPテーブルを使い回して解くという解法を忘れていた。結構汎用性がある解法のようなので、ちゃんと身に着けておきたい。