https://kanpurin.hatenablog.com/entry/2021/07/17/232213

問題概要

${H}$ 行 ${W}$ 列のグリッド上の異なる ${2}$ マス ${(i,j),(i',j')}$ を選ぶ， ${C×(|i-i'|+|j-j'|)+A_{ij}+A_{i'j'}}$ の最小値を求めよ．

${2\leq H,W\leq 1000\\ 1\leq C\leq 10^9\\ 1\leq A_{ij}\leq 10^9}$

解説

式の中に絶対値があって面倒なので ${i' \leq i\land j'\leq j}$ と決めることで絶対値を外す．グリッド全体を反転させれば他の場合も表せるので， ${i' \leq i\land j'\leq j}$ の場合で求められればいい．

${\downarrow}$

各 ${(i,j)}$ で ${C×(i-i'+j-j')+A_{ij}+A_{i'j'}}$ の最小を求める．この式を変形すると，

${\underset{i'\leq i\land j'\leq j\land (i,j)\neq(i',j')}{\min}(C×(i-i'+j-j')+A_{ij}+A_{i'j'})\\ =\underset{i'\leq i\land j'\leq j\land (i,j)\neq(i',j')}{\min}(A_{i'j'}-C×(i'+j'))+A_{ij}+C×(i+j)}$

となるので ${A_{i'j'}-C×(i'+j')}$ の2次元の累積minを求めながら計算すれば各マス ${O(1)}$ で求められる．全体の計算量は ${O(HW)}$

提出プログラム

https://atcoder.jp/contests/abc210/submissions/24331401

ABC210 D - National Railway

問題概要

解説

提出プログラム

感想