AtCoder Beginner Contest 243

　ABCDGで五完でした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 243　ABCDGの五完
A Aとしては難し過ぎませんか？
B 2-1はsetで
C yごとに、Rの左端、Lの右端を見る
D R/LとUを相殺させる。シミュレーションしようとして2TLEしました。
G 実験すると（√xについて）https://t.co/RpyStxYvEH　が出てくるので頑張る

— titia (@titia_til) March 12, 2022

E - Edge Deletion

　解説AC。

　制約からワーシャルフロイドをすることは思いつくけど、その後が難しい。

　解説の条件で良いことを思い付くのも簡単ではないし、証明も容易ではない。

　ただ、コンテスト中全く考えなかったか？　と聞かれると、頭を掠めた気はするので、試すことはできたかもしれない。

F - Lottery

　解説ACしたが、解説を見てもしばらく分からなかった。

　N種類のどれが既に手に入ったか？　を持ってDPしたくなるが、それだと間に合わない。「くじを一回引く」ごとに更新していくようなDPではダメ。これに捉われていると解説を読んでも全く分からなくなってしまう。

　発想を転換して、K個のマスに1～Nの数字を埋める、と考える。

　「各商品について考えて、その商品は何回目のくじで当たったか？」でDPテーブルを更新していく。これだと、「残っているマスx個のうちy個にi番目の商品が当選した」のなら、(x, y)という二項係数を掛けることで更新できる。

　詰まったら発想を転換しよう、という気持ちでいれば難しくないはずなのだが。