マンハッタン距離を扱う問題のテクニック
概要
幾何学における距離概念の 1 つ。各座標の差の総和を 2 点間の距離とする。
\[
d(X, Y) = \sum_{k=1}^n|x_k - y_k|
\]
2 次元の場合、2 点 \(A(x_a, y_a), B(x_b, y_b)\) の時のマンハッタン距離は \(|x_a-x_b|+|y_a-y_b|\) になる。
マンハッタン距離を扱う問題ではしばしば座標を45 度回転させてから考えると楽になる。
各点とのマンハッタン距離の総和
各点とのマンハッタン距離の総和が最も小さくなるのは各軸の中央値を座標とする点になる。
点の数が偶数個の場合は 2 つの中央値の間の値であれば何でもよい。
45 度回転とマンハッタン距離
2 点 \(A(x_a, y_a), B(x_b, y_b)\) のマンハッタン距離を考える。この時マンハッタン距離を改めて \(\textrm{max}(x, -x)\) のようにして考えると、
\[\begin{split}
|x_a-x_b|+|y_a-y_b| = \textrm{max}(&(x_a-x_b)+(y_a-y_b),\\
&-(x_a-x_b)+(y_a-y_b), \\
&(x_a-x_b)-(y_a-y_b), \\
&-(x_a-x_b)-(y_a-y_b))
\end{split}\]
これを整理すると
\[\begin{split}
|x_a-x_b|+|y_a-y_b| = \textrm{max}(&(x_a+y_a)-(x_b+y_b),\\
&-(x_a-y_a)+(x_b-y_b), \\
&(x_a-y_a)-(x_b-y_b), \\
&-(x_a+y_a)+(x_b+y_b))
\end{split}\]
ここで座標\((x, y)\)を45度回転した\((x\prime, y\prime)=(x+y,x-y)\)を考えると(定数倍は無視)マンハッタン距離は下記のようになる。 $$
|x_a-x_b|+|y_a-y_b|=\textrm{max}(|x\prime_a - x\prime_b|,|y\prime_a-y\prime_b|)
$$ したがって45度回転座標系ではマンハッタン距離を\(x\)軸,\(y\)軸それぞれを独立で考えることができるようになる。
例: 提出 #46706195 - AtCoder Beginner Contest 178