Codeforces Round #806 (Div. 4)

 　Div. 4で全完できなかったのは初めてだと思うのでショック。

コンテストへのリンク

コンテスト後のツイート

F BITを使って平面走査。最初、座標圧縮が必要な気がして混乱（結局必要なかった）。
G 何回badな鍵を使ったかもってDP。これは、いっぱい鍵を使ったらお金が0になることを利用しているので、そのときのDPの値は維持される、ということを忘れてはダメ（忘れた上、コンテスト中気付かなかった……）

— titia (@titia_til) July 12, 2022

G. Good Key, Bad Key

　他の人のコードを見て理解し、AC。

　ただ、コードを見てもすぐには理解できなかった……。ランダムケースで実行して、自分のコードが負を吐く場合があることに気付き、理解できた。

　しかし、このことに気付けなかったのはひどい。このケースを書かないというのは、「何回badな鍵を使ったかもってDP」という正当性が理解できていないこととほとんど同じだ。（いや、最初考えたときは理解していたはずなのに）

　答えが負になるはずがない、ということは分かっていたので、コンテスト中もランダムケースを実行すべきだった。Nが小さい場合の愚直を書いて比較したりしたが、Nが小さければ答えが一致してしまうため、今回のミス発見には至れない。

　そこから、Nが小さい場合は上手くいっているみたいだから、Nが大きい場合に何が起こるか考えよう（もしくは、Nが大きい場合のランダムケースを実行してみよう）、と思うべきだった。