結果
5完。E問題で12回の誤答と、ハマりにハマって大変なことになった。
なんかレート更新がされていなくていつもの成績表が貼れない。
A - Curtain
問題文が理解できなかったが、結局こういうことを要求されているんだろうという推測を書いたら通った。
B - TAKOYAKI FESTIVAL 2019
for文が書けますかというだけの問題では。
C - Slimes
終端の処理とかがやや怖かと一瞬疑ったけど別にそうでもなくてfor文が書けますかというだけの問題。
解説PDF見ていて知ったけど、std::uniqueという手段があるのか。うーん、そりゃあるよな。
D - Triangles
最初はやや混乱したけど、まぁ辺のうち二つは全探索して残りは条件に合うものを適切に探すんだろうなという方針は早めに立った。後は冷静に条件を考えてコード中のような考察をしてAC。解説PDFの通り、大きい二つを全探索というようにすればもっと無駄が省けたんだな。
E - Travel by Car
正確な計算量の見積もりはできていないけど、結局（給油回数, 現在の燃料量）をコストとしてダイクストラを回やれば良いと判断した。感覚だけど、各ノードに到達したとき給油回数は最善に比べてせいぜい1多い場合があり得るだけなので計算量的には大丈夫そう。だが重要な問題として「給油回数は少ない方が良いが、現在の燃料量は多い方が良い」というこの二つで比較方法が逆である点にめちゃくちゃ苦しめられた。
コストの更新部分でまず間違えて1WAをくらい、そこを修正すると1ケースだけTLEになるというところから地獄が始まる。1ケースだけTLEだとcinの高速化とか変数をグローバルに置くとかで行けそうだと錯覚してしまい、そういう些細なお気持ち程度の高速化をして提出してはTLEということを繰り返した結果12ペナ。最終的にpriority_queueから取り出す順番の比較関数で現在の燃料量を小さい順に取り出していたところを修正したらAC。そうなんだよ、ダイクストラ法でTLEくらう場合ってたいていpriority_queueから取り出す順番が間違っているっていうことをすっかり忘れていた。最近はもう全然競技プログラミングに触ってないのでこういう典型的なミスに対する嗅覚が錆びついていく一方だ。AtCoderがシビアな時間制限にすることもそんなにないし、感覚がダメ。コンテスト中にしっかり考えていく根気が足りてなくて、高速化で通ってくれと思考停止してしまっていたのが最悪だった。
解説PDFとはやや違うけど、まぁ別に嘘解法ではないと思う。というか解説の方法がむしろよくわからないな。それでいけるのか、うーん。言われればそんな気もするが確信が持てなくて実装し始めるには躊躇するくらいだなぁ。
F - Distinct Numbers
個ビンを用意して、現在最小値のものに詰めていく感じだと
だなぁという考察しか進まなかった。解説PDF読んで通したが、なにこれ頭が良すぎる。こういう発想ができるようになれる気がしない。
