概要

数直線上の \(N\) 人の位置 \(X_i\) に対し、待ち合わせ地点 \(P\)（整数）を 1 つ選んで、総移動距離 \(\\sum_{i=1}^{N} |X_i - P|\) を最小にする問題です。結論として、最適な \(P\) は 中央値 になります。

考察

重要な気づき（中央値が最適）

総移動距離 \(f(P)=\\sum |X_i-P|\) は、\(P\) を右に動かすと「左側の人の距離は増え、右側の人の距離は減る」という性質があります。

直感的には、\(P\) を少し右へ動かしたとき、 - \(P\) より左にいる人数を \(L\) - \(P\) より右にいる人数を \(R\) とすると、距離の増減は概ね - 左側の人は合計で \(+L\) - 右側の人は合計で \(-R\) となり、差分は \(L-R\) になります。

つまり、 - \(L < R\) なら右へ動かすと総距離は減る（まだ右に寄せた方が良い） - \(L > R\) なら右へ動かすと総距離は増える（左に戻した方が良い） - \(L = R\) 付近で最小になる

この「左右の人数が釣り合う点」が 中央値 です。
よって、\(X_i\) をソートしたときの真ん中（\(N\) が偶数なら中央 2 つの間のどこでも最適、整数条件でも中央のどちらかを選べば最小）を選べばよいです。

素朴な方法がダメな理由

\(P\) は任意の整数で範囲が最大 \([-10^9,10^9]\) と非常に広いので、全ての \(P\) を試すのは不可能です。また、候補を \(X_i\) のみに絞っても、各候補で合計を計算すると \(O(N^2)\) になり、\(N \\le 2\\times 10^5\) では間に合いません。

中央値という性質を使えば、探索なしで一発で最適点が決まります。

具体例

例えば \(X=[1,2,10]\) のとき、中央値は \(2\)。 - \(P=2\) なら総距離は \(|1-2|+|2-2|+|10-2|=1+0+8=9\) - \(P=1\) なら \(0+1+9=10\) - \(P=3\) なら \(2+1+7=10\)

確かに中央値のとき最小になります。

アルゴリズム

1. 配列 \(X\) を昇順にソートする。
2. 中央の要素 \(X_{\\lfloor N/2 \\rfloor}\) を中央値として選ぶ（0-indexed）。
3. \(\\sum |X_i - \\text{median}|\) を計算して出力する。

偶数 \(N\) の場合、中央値は「中央 2 要素の間」のどこでも最小になりますが、本問では \(P\) は整数なので、ソート後の \(X_{N/2}\)（あるいは \(X_{N/2-1}\)）を選べば最小値が得られます。コードでは \(X_{N//2}\) を採用しています。

計算量

• 時間計算量: \(O(N \\log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（座標配列の保持）

実装のポイント

• \(N\) が大きいので、入力は sys.stdin.buffer.read() を使うと高速です。

• 座標や距離の合計は最大で \(N \\times 2\\times 10^9\) 程度になり得ますが、Python の整数は多倍長なのでオーバーフローの心配はありません。

• 中央値を取った後は sum(abs(x - median) for x in xs) で素直に計算して大丈夫です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    xs = list(map(int, data[1:1+n]))
    xs.sort()
    median = xs[n // 2]
    ans = sum(abs(x - median) for x in xs)
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。