AtCoder Grand Contest 069 A
10分か20分ぐらいで、
それぞれの試合について、x 日までに終わらせるのに最低限必要なコストと
r の最大値がわかれば良いかなとか
凸というか単調減少だな、とか ↑書く各x について
tok
とかは考えていて
たぶんl とかr とかで出てくる点にだけ絞っても良いかなとも思ったけれど
どちらにせよ全部の試合でそれをやっていたら間に合わないかな
直線の集まりで凸っぽいかなと思って三分探索をしようとしてしまって無駄な時間を過ごしたかな
よく考えたら単調減少なんだから、もしそれで求まるなら、10^9 日までに終わらせるのに必要なコストを
素直に求めれば良いだけやんって
結局、試合ごとに
各 x についてx 日までに〜を求めることに
ただ、すべてのx について求めていてもあれやし
その試合までにかかわるl とr の値だけについて求めて
それに加えて、その間を考えるときにどれだけ補正すれば良いかも求めるようにしたかな
それでも答えが合わず、なかなか悩んだけれど
結局は端の方で、補正すべきはどれだけか、が間違っていたんやおね
そのあたりを適当に直したらAC になったかな
sai
最初から、直線と直線の交わりとして考えていたら
上のところも機械的にやるだけやったし、間違えなかったかなと
少し公開したかな
後悔