\(P\) として、\(X_1,\dots,X_N\) の中央値を選ぶのが最適です。

AI解説における、中央値が最適になることの説明は不完全です。例えば \(X=(1,2,3,10,10,10,10,101,102,103,104)\) のケースをうまく説明できていないことを確認してください。

以下、中央値が最適になることの証明をします。

\(X\) は昇順にソートされているとしてよいです。

もし、 座標が \(P\) 以下の友人の数が \(\frac{N}{2}\) 未満なら、\(P\) を右に少し(友人を追い越さない範囲で)動かす方が得です。同様に座標が \(P\) 以上の友人の数が \(\frac{N}{2}\) 未満なら、\(P\) を左に少し動かす方が得です。よって、最適な \(P\) は「座標が \(P\) 以下の友人の数が \(\frac{N}{2}\)以上かつ、座標が \(P\) 以上の友人の数が \(\frac{N}{2}\) 以上」を満たす必要があります。このような条件を満たす必要十分条件は、 \(N\) が奇数なら \(P=X_{\frac{N+1}{2}}\) 、\(N\) が偶数ならば \(X_{\frac{N}{2}}\leq P \leq X_{\frac{N}{2}+1}\) となります。逆に、この範囲のどの値を \(P\) としても \(|P-X_1|+\ldots+|P-X_N|\) の値は変化しないことが証明できます。中央値はどちらのケースも満たします。∎

なお、上の証明からわかるとおり、\(N\) が偶数の場合には、中央値(中央2要素の平均値)の代わりに中央2要素の間の任意の値で最適化を達成できます。よって、\(N\) の偶奇のケースを統一して、 \(P=X_{\left\lfloor\frac{N+1}{2}\right\rfloor}\) とすることができます。

ソートがボトルネックとなり計算量は \(O(N \log N)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int>x(n);
  for(int i=0; i<n; i++) cin >> x[i];
  sort(x.begin(), x.end());

  int p = x[n/2];
  long long ans = 0;
  for(int i=0; i<n; i++){
    ans += abs(p - x[i]);
  }
  cout << ans << endl;
}

実装例 (Python)

N = int(input())
X = list(map(int, input().split()))
X.sort()
P = X[N//2]
ans = sum(abs(P - x) for x in X)
print(ans)