概要

数直線上に配置された \(N\) 人の友人に対し、総移動距離が最小となる待ち合わせ場所を求める問題です。最適な待ち合わせ場所は中央値の位置になります。

考察

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

総移動距離 \(\sum_{i=1}^{N} |X_i - P|\) を最小化する \(P\) は、座標の中央値です。

なぜ中央値が最適なのか？

具体例で考えてみましょう。友人が座標 \(1, 3, 7\) にいる場合（\(N=3\)）：

• \(P = 1\) のとき：\(|1-1| + |3-1| + |7-1| = 0 + 2 + 6 = 8\)
• \(P = 3\) のとき：\(|1-3| + |3-3| + |7-3| = 2 + 0 + 4 = 6\) ← 最小！
• \(P = 7\) のとき：\(|1-7| + |3-7| + |7-7| = 6 + 4 + 0 = 10\)

中央値である \(3\) を選ぶと最小になります。

直感的な理解

待ち合わせ場所 \(P\) を少し右に動かすと： - \(P\) より左にいる友人は全員、移動距離が増える - \(P\) より右にいる友人は全員、移動距離が減る

つまり、\(P\) の左右に同じ人数がいれば、\(P\) を動かしても増減が相殺されます。中央値はまさにこの条件を満たす位置です。

素朴なアプローチの問題点

すべての整数 \(P\)（\(-10^9\) から \(10^9\)）を試すと、約 \(2 \times 10^9\) 通りあり、TLE（時間超過）になります。中央値を直接計算すれば、ソートの \(O(N \log N)\) で済みます。

アルゴリズム

1. 座標をソートする
2. 中央値を求める
   • \(N\) が奇数：\(X[N/2]\)（0-indexed で真ん中の要素）
   • \(N\) が偶数：\(X[N/2 - 1]\) または \(X[N/2]\)（どちらでも最適）
3. 各友人の座標から中央値までの距離の総和を計算する

偶数個の場合の補足

\(N\) が偶数のとき、中央の2つの値の間（両端含む）のどの点を選んでも総移動距離は同じです。整数解を求める場合は、その2点のいずれかを選べば良いです。

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック）
• 空間計算量: \(O(N)\)（座標を格納する配列）

実装のポイント

• ソート後のインデックスに注意。0-indexed で \(N\) 個の要素がある場合、中央値は x[n // 2]（奇数）または x[n // 2 - 1] と x[n // 2] の間（偶数）

• 座標が \(-10^9\) から \(10^9\) の範囲で、\(N\) が最大 \(2 \times 10^5\) のため、総移動距離は最大で約 \(2 \times 10^{14}\) になり得る。Python では整数オーバーフローの心配はないが、他の言語では long long 型を使用する必要がある

  ソースコード

n = int(input())
x = list(map(int, input().split()))
x.sort()

# 中央値を待ち合わせ場所にすると総移動距離が最小になる
median = x[n // 2] if n % 2 == 1 else x[n // 2 - 1]

# 総移動距離を計算
total_distance = sum(abs(xi - median) for xi in x)
print(total_distance)

---

この解説は claude4.5opus によって生成されました。