そのうち誰かの役に立つ

もしくは誰の役にも立たない

競プロチャレンジ供養会場: ZONeエナジー プログラミングコンテスト “HELLO SPACE” E - 潜入

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

問題

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))$

公式解説

躓いた点

  • 探索で枝刈りしようとして失敗