マンハッタン距離と45度回転

マンハッタン距離またはL1-距離とは幾何学における距離概念の一つで、各座標の差の絶対値の総和を2点間の距離とするものです。

平面上であれば、座標(x1, y1)と(x2, y2)のマンハッタン距離は |x1 – x2| + |y1 – y2| となります。

ところで |x1 – x2| は (x1 – x2) と -(x1 – x2) の大きい方と考えることもできます。Max(a, b) を a と b のうち大きいほうを返す関数と定義するとMax(x1 – x2, x2 – x1) と書けます。

|x1 – x2| + |y1 – y2| であれば Max(x1 – x2, x2 – x1) + Max(y1 – y2, y2 – y1) です。
これをさらに式変形すると、

①式のかっこをはずして並べ替えると

となります。

ここで xi + yi = zi, xi – yi = wi とおくと ②式は Max(z1 – z2, w1 – w2, – w1 + w2, – z1 + z2) となり、|x1 – x2| は Max(x1 – x2, x2 – x1) であることから ②式は Max(|z1 – z2|, |w1 – w2|) と変形できます。

つまり、|x1 – x2| + |y1 – y2| = Max(|z1 – z2|, |w1 – w2|) です。これがいわゆる45度回転です。

こんなことをしてなにが嬉しいのか？

45度回転のなにが嬉しいのか？

E – Dist Max

E – Dist Max

二次元平面上に N 個の点があり、i 番目の点の座標は (x_i, y_i) です。 同じ座標に複数の点があることもあります。異なる二点間のマンハッタン距離として考えられる最大の値はいくつでしょうか。

入力されるデータ
N
x_1 y_1
x_2 y_2
:
x_N y_N
（ただし、2 ≦ N ≦ 2 × 10^5, 1 ≦ x_i, y_i ≦ 10^9 ）

N が最大 2 × 10^5 なので、2点のすべての組み合わせでマンハッタン距離を求めて比較していては制限時間内に間に合いません。そこで45度回転で計算量を落とします。

問題文は「i と j が 1 ≦ i, j ≦ N のとき |x_i – x_j| + |y_i – y_j| の最大値を求めよ」と言っているわけですが、これは Max(|zi – zj|, |wi – wj|) の最大値を求めよと同じ意味です。

さらにこれは i と j が 1 ≦ i, j ≦ N のとき |zi – zj|の最大値と |wi – wj|の最大値を比較し、大きい方を求めよと書き換えることができます。

なぜならすべての i, j の組み合わせで |zi – zj| と |wi – wj| の大きいほうを求めてそのなかから最大値を求めるのと、先に |zi – zj| の最大値、|wi – wj| の最大値を求めておいて、両者のうち大きい方を採用するのは同じことだからです。

では |zi – zj| が最大になるのはどのような場合でしょうか？ N 個の値から 2 つを取り出してその差の絶対値が最大になるのは z の最大値から最小値を引いたときです。

この問題の解は Max(Max(zi) – Min(zi), Max(wi) – Min(wi)) です。これまでは i, j というふたつの変数があったのですが、i だけになりました。計算量を O(N^2) から O(N) に落とすことができたのです。

マンハッタン距離の総和の最小化

マンハッタン距離の最大値ではなく総和を考えるときはどうすればよいでしょうか？ 総和を最小化するときは中央値を使う方法が有効です。

最初に平面上ではなく数直線上の数で考えます。配列 A = {A[0], A[1], … A[N-1]} が与えられたとして |A[i] – x| の総和を最小にする整数 x とその時の総和の値を求めるにはどうすればよいでしょうか？

「x は A の中央値にする」が答えです。A の長さが偶数のときは 2 つの中央値の間の数であればなんでもかまいません。

では 2 次元平面上であればどうなるのでしょうか？ 与えられた各座標を(x_i, y_i)、求める座標を(X, Y)とすると求めるマンハッタン距離の総和は |x_i – X| + |y_i – Y| の総和となります。

|x_i – X| + |y_i – Y| の総和は、(|x_i – X| の総和) + (|y_i – Y| の総和) となります。そしてこれを最小化するのであれば |x_i – X| の総和を最小化する X と |y_i – Y| の総和を最小化する Y を探せばよいということになります（一次元についてのこの問題を 2 回解けばよい）。

C – Linear Approximation

C – Linear Approximation

すぬけ君は、長さ N の整数列 A を持っています。

すぬけ君は、整数 b を自由に選びます。 この時、A_i と b + i が離れているとすぬけ君は悲しいです。より具体的には、すぬけ君の悲しさの値は次の式で計算されます。

|A_1 – (b + 1)| + |A_2 – (b + 2)| + … + |A_N – (b + N)|

すぬけ君の悲しさの値の最小値を求めてください。

入力されるデータ
N
A_1 A_2 … A_N
（ただし、1 ≦ N ≦ 2×10^5, 1 ≦ A_i ≦ 10^9 ）

すぬけ君、こんなことで悲しまないでくれ！ 鳩は毎週レーティングがあがらず悲しいよ！ 君はレッドコーダーなのだから明るくいこうよ！

冗談はさておき、これは |A_1 – (b + 1)| + |A_2 – (b + 2)| + … + |A_N – (b + N)| を最小化する問題です。式を変形すると |(A_1 – 1) – b| + |(A_2 – 2) – b| + … + |(A_N – N) – b| となります。また配列 C_i = A_i – i を定義すると |C_1 – b| + |C_2 – b| + … + |C_N – b| となり、一次元についてのマンハッタン距離の総和の最小化問題になります。