【C++】マンハッタン距離の合計が最小になる点を求める方法

K次元空間上にn個の異なる点が与えられているとします。ここで、nは(2, 10⁵)の範囲、kは1〜5の範囲に収まるとします。このとき、与えられたn個の点それぞれへのマンハッタン距離の合計が最小となる点を求めるのが本記事の目的です。

まず、2つの点P1(x1, y1)とP2(x2, y2)間のマンハッタン距離は、次のように定義されます。

|x1 − x2| + |y1 − y2|

例えば、次元が3で、(1, 1, 1)、(2, 2, 2)、(3, 3, 3)という3つの点が与えられた場合、答えは(2, 2, 2)となります。

解法の考え方

マンハッタン距離は各次元ごとに独立した絶対値の和として表せるため、問題を各次元単位に分解できます。そして、1次元上で「ある点からの絶対偏差の合計」を最小化する値は中央値（メディアン）であることが知られています。

したがって、この問題は以下の手順で解くことができます。

• すべてのk次元について、それぞれの座標リストをソートする
• 各次元の中央に位置する要素（中央値）を取り出す
• それらを組み合わせた点が答えとなる

C++での実装例

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

void minimizeManhattan(int n, int k, vector<vector<int>>& pointList) {
    // すべてのk次元でソート
    for (int i = 0; i < k; ++i)
        sort(pointList[i].begin(), pointList[i].end());

    // 各次元の中央値を出力
    for (int i = 0; i < k; ++i)
        cout << pointList[i][(ceil((double)n / 2) - 1)] << " ";
}

int main() {
    int n = 4, k = 4;
    vector<vector<int>> point = { { 1, 5, 2, 4 },
                                  { 6, 2, 0, 6 },
                                  { 9, 5, 1, 3 },
                                  { 6, 7, 5, 9 } };
    minimizeManhattan(n, k, point);
}

出力結果

2 2 3 6

このコードでは、まず各次元の座標を昇順にソートしています。その後、要素数nに対して中央位置（ceil(n/2) − 1番目）の値を取り出し、それらを連結して答えの点としています。

計算量は、各次元のソートにO(n log n)かかるため、全体でO(k・n log n)となり、nが10⁵程度でも十分高速に動作します。