概要

数直線上にいる \(N\) 人の友人全員から最も総移動距離が小さくなるような待ち合わせ場所を選び、その距離の合計を求める問題です。

考察

この問題では、待ち合わせ場所 \(P\) をどこにするかが鍵となります。目標は $\( \sum_{i=1}^{N} |X_i - P| \)\( を最小にする \)P$ の値を求めることです。

これは典型的な「絶対値の和を最小化する問題」であり、数学的に知られている性質があります：

数直線上の点集合に対して、それらからの絶対距離の和を最小にする点は中央値である。

例えば、友人が座標 \([1, 2, 4]\) にいたとします。候補となる待ち合わせ場所をいくつか試してみましょう：

• \(P = 1\): \(|1-1| + |2-1| + |4-1| = 0 + 1 + 3 = 4\)
• \(P = 2\): \(|1-2| + |2-2| + |4-2| = 1 + 0 + 2 = 3\)
• \(P = 3\): \(|1-3| + |2-3| + |4-3| = 2 + 1 + 1 = 4\)

最も小さいのは \(P = 2\)（つまり中央値）となっています。

ただし注意すべきは、要素数が偶数の場合です。例えば \([1, 2, 4, 5]\) のとき、中央値は「真ん中の2つの値の間にある任意の値」が最適です。この場合、\(P = 2\), \(3\), \(4\) のどれを選んでも同じ結果になります。

したがって、奇数なら真ん中の値、偶数なら真ん中2つのうち左側（または右側でもよい）を選ぶことで最適解を得られます。

素朴な方法として、全探索で全ての \(P\) を試すことは考えられますが、制約より最大で \(2 \times 10^5\) 人いるため、計算量的に無理があります（時間計算量 \(O(N \cdot (\max(X)-\min(X)))\)）。また、負の座標もあるので扱いも大変です。

そこで、「ソートして中央値を使う」というテクニックを使います。これにより効率的に最適な待ち合わせ場所を求めることができます。

アルゴリズム

1. 友人の座標リスト \(X\) を昇順にソートします。
2. ソート後のリストの中央値を求めます：
   • \(N\) が奇数のときは \(X[N//2]\)
   • \(N\) が偶数のときは \(X[N//2 - 1]\) （どちらでも良いが、便宜上左側を使用）
3. 中央値を待ち合わせ場所 \(P\) として、各 \(X_i\) との差の絶対値を足し合わせ、総移動距離を求めます。
4. 結果を出力します。

計算量

• 時間計算量: \(O(N \log N)\) （主にソートによるオーバーヘッド）
• 空間計算量: \(O(1)\) （入力を除けば定数メモリ）

実装のポイント

• Pythonでは list.sort() または sorted() 関数で簡単にソートできます。
• 偶数長の場合でも、中央値の取り方によって結果が変わらないことを理解しておくと混乱を避けられます。
• 絶対値の和を高速に計算するために、中央値以外の選択肢を考える必要はありません。

## ソースコード

```python
N = int(input())
X = list(map(int, input().split()))

X.sort()

if N % 2 == 1:
    median = X[N // 2]
else:
    median = X[N // 2 - 1]

total_distance = sum(abs(x - median) for x in X)

print(total_distance)

---

この解説は qwen3-coder-480b によって生成されました。