2017/11/01の精進

・ARC060E 高橋君とホテル

a番目のホテルからb番目のホテルまでなるべく早く移動する方法をかんがえると、明らかに今いるホテルから1日でたどり着けるできるだけ遠いホテルに移動することを繰り返すだけ。(a>bのときはスワップすればいいので常に移動先は右にあるとおもっていい)

そこで、まず各ホテルから1日でたどり着けるできるだけ遠いホテルを二分探索で見つける。この情報を利用すると各ホテルから2日でたどり着けるホテルが見つかる。これを繰り返すと、2^k日でたどり着けるホテルがわかる。

a番目のホテルからb番目のホテルをこえないようになるべく大きく動くことを繰り返せば高々log N回で済み、間に合う。