脳log[20220615]

2022年06月15日 (水) [AtCoder] 精進。ABC204-E「Rush Hour 2」(青 diff)。コンテスト後に小数がどうのとか底が２乗付近にあるとかのヒントを読んでいた。■提出 #32477294 (AC / 1049 Byte / 560 ms)。といって、範囲を絞っても線形探索では special_*.txt ケースが１分近くかかって大いに苦しんだのだけど。範囲総当たりに代わる 56 行目の bsearch メソッドが非常に危なっかしく見える。■提出 #32477346 (AC / 1021 Byte / 569 ms)。底が２乗付近にあることの意味を理解していなかった。D/t と D/(t+1) の差が１以下になるまでは到着時刻が早まる可能性があるから調べなければいけないのだと思っていたけど、～までは可能性がある、ではなくて、～付近まで(階段状に)短縮するもしくは横ばいだからその近辺(悪化する直前)だけ調べればいい、だったみたい。実際１つめの提出で bsearch メソッドが調べてるのもそういう位置なんだから当たり前の話なんだけど。意外にも３地点だけを調べるこの提出と二分探索で範囲を調べる１つめの提出の(最悪)時間は変わらない。けれど内訳を見るとやはり special_*.txt には大きな差がついている。毎回の探索範囲が広いという点がスペシャルな所以なのだろう。だから線形、二分、定数の順にタイムが顕著に異なる。