コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1570 (記事作成時点)
供養
解法
- 自明な上界として、隣接する2地点に駅を建て、距離1の線路で繋いだものの最小値がある
- 距離2以上の線路を、点 $(h, w)$ から東西南北のうち2方向に伸びた線路とその先に建った駅と考える
- $(h, w)$ から東方向に線路を伸ばして駅を建てる場合を考える
- $1 \le j \le W - w$ について、$(h, w + j)$ まで線路を伸ばして駅を建てる場合のコストは $A_{h, w + j} + jC$ である
- よって、東方向に伸ばした場合の最小コスト $E_{h, w}$ は $\min_{j = 1}^{W - w}(A_{h, w + j} + jC) = \min_{j = w + 1}^{W}(A_{h, j} + jC) - wC$
- $\min_{j = w + 1}^{W}(A_{h, j} + jC)$ の部分を $E^{'}_{h, w}$ とすると、$E^{'}_{h, w}$ は $E^{'}_{h, w + 1}$ の結果を使えるので $w = W - 1, \dots, 1$ の順番で効率的に求めることができる
- 同様に西、南、北に線路を伸ばした場合の最小コストをそれぞれ $W_{h, w}, S_{h, w}, N_{h, w}$ と求めることができる
- $\min_{h, w}\left(\min(E_{h, w} + W_{h, w}, E_{h, w} + S_{h, w}, E_{h, w} + N_{h, w}, W_{h, w} + S_{h, w}, W_{h, w} + N_{h, w}, S_{h, w} + N_{h, w})\right)$ と $U$ を比較して小さいほうが答え
実装
計算量は $O(HW)$
公式解説
躓いた点
- 各方向絵の最短距離を毎回探索で求めようとしてTLE
