コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1624 (記事作成時点)
供養
解法1
- $(r, c) \to (r - i, c)$ の辺を全て作成すると辺の数が $O(RC^{2})$ となるので、各頂点 $(r, c)$ に対応する頂点 $(r^{'}, c^{'})$ を用意して以下のように辺の数を減らす
- $r \gt 1$ について、$(r, c) \to (r^{'}, c^{'})$ に重さ $1$ の辺を張る
- $r \gt 1$ について、$(r^{'}, c^{'}) \to (r^{'} - 1, c^{'})$ に重さ $1$ の辺を張る
- $r \lt R$ について、$(r^{'}, c^{'}) \to (r, c)$ に重さ $0$ の辺を張る
- 上記によって辺の数が $O(RC)$ となるのでDijkstraで解ける
実装
解法2
- その時点での $(r, c)$ への最短距離を $d_{r, c}$ としたとき、$(r, c) \to (r - i, c)$ について、$d_{r - k, c} \lt d_{r, c} + k + 1$ であるならば、$k \le i$ である $i$ については考える必要がない
- $d_{r - i, c} \le d_{r - k, c} + i - k + 1 \le (d_{r, c} + k + 1 - 1) + i - k + 1 = d_{r, c} + i + 1$ であるため
- これで枝刈りすると考慮する辺の数は $O(RC)$ になる
計算量は $O(RC\mathrm{log}(RC))$
公式解説
躓いた点