AtCoder Beginner Contest 391

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 391 Fが解けなかった。解説を見たらKの制約を見逃していたことに気付いた……。
C 各穴にいる鳩のsetと、鳩がどの穴にいるかを持つ
D 各列の一番小さい値が消える時間が分かる
E 再帰で書いた

— titia (@titia_til) February 1, 2025

F - K-th Largest Triplet

　解説AC。

　Kの制約に気付いていたら正解できたと思う。こういう致命的な制約見逃しはあまりやったことなかったのだが。

G - Many LCS

　自力AC。

　LCSを求めるのにDPが必要なので、この問題もDPで解くしかなさそう。

　N<=10という制約を見て、bit DPなどを考えたがちょっと違った。「i文字の部分列を構成するときの最短のindexはどこか？」を考え、それをDPのキーとしたいと考えると、それは単調増加なのでindexの部分集合の個数しかない。これを利用すれば解ける。