コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1710 (記事作成時点)

供養

解法

基本的には経路探索
時刻 $t$ 以降に辺 $i$ を使って移動する際に最も早く移動できるとき、移動先に到達する時刻は $f(x) = x + C_{i} + \lfloor \frac{D_{i}}{x + 1} \rfloor$ を $x \ge t$ の整数領域で最小化した値
$g(x) = f(x) - C_{i} + 1 = x + 1 + \lfloor \frac{D_{i}}{x + 1} \rfloor$ とし、さらに $y = x + 1$ とした $g(y) = y + \lfloor \frac{D_{i}}{y} \rfloor$ を $y \ge 1$ の整数領域で最小化することを考える
$g(y) - g(y + 1) = y + \lfloor \frac{D_{i}}{y} \rfloor - \left( y + 1 + \lfloor \frac{D_{i}}{y + 1} \rfloor \right) = \lfloor \frac{D_{i}}{y} \rfloor - \lfloor \frac{D_{i}}{y + 1} \rfloor - 1$ について、
- $\frac{D_{i}}{y} - \frac{D_{i}}{y + 1} \gt 1$ ならば $\lfloor \frac{D_{i}}{y} \rfloor - \lfloor \frac{D_{i}}{y + 1} \rfloor \ge 1$ より $g(y) - g(y + 1) \ge 0$ なので $g(y)$ は広義単調増加
- $\frac{D_{i}}{y} - \frac{D_{i}}{y + 1} \le 1$ ならば $\lfloor \frac{D_{i}}{y} \rfloor - \lfloor \frac{D_{i}}{y + 1} \rfloor \le 1$ より $g(y) - g(y + 1) \le 0$ なので $g(y)$ は広義単調減少
最小値を求めるため、$g(y)$ が広義単調増加であるような最小の $y$ を求める
- 狭義単調減少であるような最大の $y$ を求めようとすると、$g(y)$ が非線形なので最小値とならない可能性がある
- 広義単調減少であるような最大の $y$ を求める計算でも大差はない
$\frac{D_{i}}{y} - \frac{D_{i}}{y + 1} \le 1$ より $y(y + 1) - D_{i} \ge 0$、$y \ge 1$ である最小の整数より $y = \lceil \frac{-1 + \sqrt{4D_{i} + 1}}{2} \rceil$
展開して $y - 1 \lt \frac{-1 + \sqrt{4D_{i} + 1}}{2} \le y$ より $2y - 1 \lt \sqrt{4D_{i} + 1} \le 2y + 1$
$y \ge 1$ より $2y - 1 \ge 1$ なので、$(2y - 1)^{2} \le 4D_{i} + 1 \le (2y + 1)^{2}$
展開して $4y^{2} - 4y + 1 \lt 4D_{i} + 1 \le 4y^{2} + 4y + 1$ より $y(y - 1) \lt D_{i} \le y(y + 1)$
$h(y) = y(y - 1)$ としたとき、$h(y^{'}) \lt D_{i}$ となる最大の $y^{'}$ を求める
$t^{'} = \mathrm{max}(y^{'} - 1, t)$ が出発するべきタイミング