7K12B blog

猫でも分かる何か

ABC350 に参加した感想


極度精進してた頃の自分だったら時間に焦ってバグり散らかしてた気がするけど、今の自分はレーティングを最大化したいみたいな気持ちが消えてしまっているため、逆にノーペナで通せて結果的に良い成績だった。


クイックソートという最も効率の良いソートを知っていますか?僕は知っています。というのは冗談で、クイックソートが想定解では競技にならないので主客転倒するとO(1)で順番に確定していくことに気づけて全体計算量がO(N)になる。vectorやmapを組み合わせて連結リストを実現させるみたいなの5000兆回くらい出題されているので、いい加減ライブラリ化したいと思った。
https://atcoder.jp/contests/abc350/submissions/52592193


第一感でufかsccか二部マッチングを予想したけど、どれも上手くいかないので主客転倒したら完全グラフの数学であることに気づけた。こういうのを解くには完全グラフが数学で計算できるみたいな知識に日頃から興味を持っている必要があるみたいなところがあると思っていて400くらいあるかと思ったけど配点が350でインフレみを感じた。
https://atcoder.jp/contests/abc350/submissions/52602925