F以外の4点以下の問題は正解。後は部分点を拾った。もう少し取れないとまずい。
コンテスト後のツイート
I 大きい数字から見て、右端や左端に置くか？ で場合分け。二項係数で遷移できる。
— titia (@titia_til) May 5, 2026
K Aをソートしても同じ答えになるっぽい&大体連続した数になるのでは？ で部分点をもらえた。が、WAも出たので嘘か？
F - 集合
解説AC。テーマ一覧とArcAkiさんの記事を参考にしてAC。
そもそも考察が難しい。
最小値を使うか使わないかで考えると、その左側のみ、その右側のみ、両方を使う、で場合分けされるが、両方使う場合は最小値も必ず使わなくてはいけない。このことから、再帰を使って書けそうだと分かる。
……という考察部分に全く気付けなかった。
この考察通り、再帰で書こうとすると、Cartesian treeの順にやることになり、そこでは二乗の木DPを行うことになる、という流れ。
テーマを見てしまっていたので、この考察が分かった後はすんなり書けたけれど、実際はその後の部分も簡単ではない気がする。
J - 個数と総和
この問題と同じテーマというのを見てAC。
「繰り上がりを持つ桁 DP」と呼ばれているのは知らなかった。
類題をACしたときは理解していたのだろうけど、DPテーブルを使い回して解くという解法を忘れていた。結構汎用性がある解法のようなので、ちゃんと身に着けておきたい。
N - ナップサック
この解説記事を見てAC。
証明はよく分かってないが、「DP[j]を求めるのに、最大重量Bに対して、3*B*B/j個効率良いものを見れば良い」ということは押さえておく。