ABC204 E - Rush Hour 2 (500)
コンテスト中の考察
基本的にはダイクストラ法
最良の待機時間を求めれば良い
1分待ったときに移動コストが1下がらなくなったタイミングが最良
実は別の所にも最良のタイミングがある
これを愚直に求めると間に合わないので効率化したい
三分探索でできそうなので実装
駄目
解説の解法
最良のタイミングの一つは
$ \sqrt{D}
既にDより後の時間ならば今が最良
相加相乗平均で考えると
$ t = \frac{D}{t}
となる
問題:
https://atcoder.jp/contests/abc204/tasks/abc204_e
提出:
https://atcoder.jp/contests/abc204/submissions/23261036
#ABC204
#500pt
#E
#ABC
#AtCoder
#ダイクストラ法
#相加相乗平均