2019年12月12日
情報オリンピック日本委員会
問題
２
|
いちご (Strawberry) (配点 100点)
時間制限 : 2 sec / メモリ制限 : 1024 MB
|
|
解説
いちご i が赤くなる時刻 Ti は max(Ai, Ti) に置き換えても問題ない．なぜなら，地点 Ai に到達するには少なくとも Ai 秒かかるため，時刻 Ai より早く赤くなるケースは 時刻 Ai に赤くなるとしても答えには影響ないからである．以降この置き換えを行った上で議論をすすめる．
いちご i を赤い状態で収穫して地点 0 に戻るのは最速でも時刻 Ai + Ti である．よって 1 ≦ i ≦ N に対する (Ai + Ti) の最大値を M とすると，この問題に対する答えは M 以上にならなければならない．
一番東にあるいちごをいちご e とする．まず地点 Ae まで行き，そのまま地点 0 へ直行するが，もしまだ青いいちごが実をつけている地点 (地点 Ae も含む) に到着したら，それが赤くなるまで待つ，という動き方を考える．このとき，地点 0 に到着するのはちょうど時刻 M となる．よって答えは M になる．
