ARC 060 E - 高橋君とホテル

• 問題
• AC

$R[k][x] :=$ ホテル$x$から$2^k$日以内にたどり着けるもっとも右のホテル

というテーブルを作ってクエリに答えればいいのだが、ダブリングの実装でいつももたついているのでメモしておく。

$R$のサイズについて。制約より、高々$10^5$日でどの地点からどの地点にも移動できるので、テーブルは$2^d < 10^5$であるような最大の$d$まで作ってあれば十分である。この場合は$\lfloor \log_2 10^5 \rfloor = 16$、ただし、$2^0 = 1$日のデータも必要なので、$R$のサイズとしては$17$になる。計算が面倒or不安なら多めに取っても問題ない。

更新について。$k = 0$のデータだけ二分探索等で作れば、$k = 1, ..., 16$については$R[k][x] := R[k-1][R[k-1][x]]$で得られる。

クエリについて。クエリ$(a, b) (a< b)$を処理する時は、$R[16][x], R[15][x], ..., R[0][x]$の順で$b$にたどり着かないように採用していって、最後に1を足すのが一番簡単そう。疑似コードで書くと、

sum := 0
for k from 16 downto 0
    if R[k][a] < b
        sum += 2^k
        a := R[k][a]
return sum + 1

---

最初、なぜか非対称だと思って右に行く場合のテーブルと左に行く場合のテーブルを作ってしまった。