マンハッタン距離とチェビシェフ距離

マンハッタン (r=2)     チェビシェフ (r=2)
    . . * . .            * * * * *
    . * * * .            * * * * *
    * * * * *            * * * * *
    . * * * .            * * * * *
    . . * . .            * * * * *

将棋の王将が \((0,0)\) から \((5,2)\) へ移動する手数は、斜め \(2\) 回 \(+\) 横 \(3\) 回 \(= \rm{max}(5,2)\)。

マンハッタン距離とチェビシェフ距離の変換

\(45^{\circ}\) 回転 \((u = x + y, v = x \ – \ y)\) で、マンハッタン距離とチェビシェフ距離は入れ替わる。
「和」と「\(\rm{max}\)」を行き来できるので、求めたいものに合う形に直すと軸ごとに分けて解ける。

変換公式

\(u = x + y, v = x \ – \ y\) と置く。

ひし形を \(45^{\circ}\) 回すと正方形になる、という関係。

証明（\(a = \Delta x, b = \Delta y\)）

マンハッタン → チェビシェフ : 絶対値は「符号を選んで大きいほう」なので \(|a| + |b| = \rm{max}(a + b, a \ – \ b, -a + b, -a \ – \ b) = \rm{max}(|a + b|, |a \ – \ b|) = \rm{max}(| \Delta u |, | \Delta v |)\)

チェビシェフ → マンハッタン : \(|a + b| + |a \ – \ b|\) は、同符号なら \((|a| + |b|) + |a| \ – \ |b|\)、異符号でも同様で、どちらも \(2 \cdot \rm{max} (|a|, |b|)\) よって \(\rm{max} (|\Delta x|, |\Delta y|) = (|\Delta u| + |\Delta v|) / 2\)

どちらに直すか

求めたいものと同じ形の距離に直すと、軸ごとに分けられる。

• マンハッタンの最大値 → \(u, v\) に直して（最大 − 最小）の大きいほう。
• チェビシェフの総和 → \(u, v\) に直して \(u\) の \(1\) 次元距離和 ＋ \(v\) の \(1\) 次元距離和を \(2\) で割る。
• マンハッタンの総和 → 回転不要。そのまま \(x, y\) に分ける。
• チェビシェフの最大値 → 回転不要。そのまま \(\rm{max}(x\) の範囲\(, y\) の範囲\()\)

実装パターン

1.マンハッタン距離の最大値

ll umax = LLONG_MIN;
ll umin = LLONG_MAX;
ll vmax = LLONG_MIN;
ll vmin = LLONG_MAX;

rep(i, N) {
  ll u = x[i] + y[i];
  ll v = x[i] - y[i];
  umax = max(umax, u);
  umin = min(umin, u);
  vmax = max(vmax, v);
  vmin = min(vmin, v);
}

ll ans = max(umax - umin, vmax - vmin);

2.1次元の距離の総和（全ペア）

総和系の部品。
ソートして、各点について「自分より左の点との距離の和」を足す。

// Σ_{i<j} |a_i - a_j|
ll sum_abs_pairs(vector<ll> a) {
  sort(a.begin(), a.ned());
  ll res = 0;
  ll pre = 0;
  rep(i, (int) a.size()) {
    res += a[i] * i - pre;
    pre += a[i];
  }
  return res; 
}

• マンハッタン距離の総和 = sum_abs_pairs(x) + sum_abs_pairs(y)
• チェビシェフ距離の総和 = (sum_abs_pairs(u) + sum_abs_pairs(v)) / 2

3.1点からの重み付き距離和を全位置について

位置 \(k\) に重み \(\rm{W}[k]\) があるとき、各 \(x\) について \(\sum \rm{W}[k] \cdot | x \ – \ k| \) を \(\rm{O}(k)\) で。

vector<ll> dist_sum(const vector<ll>& W) {
  int K = W.size();
  vector<ll> res(K);

  ll cntL = 0;
  ll sumL = 0;
  ll cntR = 0;
  ll sumR = 0;

  rep(k, K) {
    cntR += W[k];
    sumR += W[k] * k;
  }

  rep(x, K) {
    res[x] = (x * cntL - sumL) + (sumR - x * cntR);
    cntL += W[x];
    sumL += W[x] * x;
    cntR -= W[x];
    sumR -= W[x] * x;
  }

  return res;
}

グリッド上のチェビシェフ距離の和に使うときは、人数を斜めのラインごとにまとめる。

int K = 2 * N - 1;
vector<ll> WU(K);
vector<ll> WV(K);
rep(i, N) {
  rep(j, N) {
    WU[i + j] += w[i][j];
    WV[i - j + N - 1] += w[i][j];
  }
}
auto GU = dist_sum(WU);
auto GV = dist_sum(WV);

4.斜め移動だけの距離

\(\pm 1, \pm 1\) にしか動けないとき：

• \(x + y\) の偶奇は変わらない → 偶奇が違う \(2\) 点は到達不可能。
• 偶奇が同じなら、必要な回数は \(\rm{max}(| \Delta x | , | \Delta y |) = (| \Delta u | + | \Delta v |) / 2\)。

偶奇でグループを分けてから、各グループでパターン２を使う。

練習問題

• ABC178 E – Dist Max … マンハッタン距離の最大値
• 典型90問 036 Max Manhattan Distance … 指定された点からの最大距離をクエリで
• ABC351 E – Jump Distance Sum … 斜め移動の距離の総和。
• ABC476 F Chebyshev Cafe … 重み付きグリッドでチェビシェフ距離の和を全マスについて