概要

数直線上の \(N\) 個の点 \(X_i\) から、ある点 \(P\) までの距離の総和 \(\sum_{i=1}^{N} |X_i - P|\) を最小化する問題です。この問題は、統計学や数学において「L1ノルムの最小化」として知られる典型的な問題です。

考察

この問題を解くための鍵は、「絶対値の和を最小にする地点 \(P\) は、与えられた座標の中央値（メディアン）である」という性質に気づくことです。

なぜ中央値なのか？

直感的に理解するために、待ち合わせ場所 \(P\) を動かしたときに総移動距離がどう変化するかを考えてみましょう。

1. \(P\) よりも左側に \(L\) 人、右側に \(R\) 人の友人がいるとします。
2. \(P\) を右にわずかに距離 \(d\) だけ動かすと、
   • 左側にいる \(L\) 人の移動距離はそれぞれ \(d\) ずつ増えます（合計 \(+L \times d\)）。
   • 右側にいる \(R\) 人の移動距離はそれぞれ \(d\) ずつ減ります（合計 \(-R \times d\)）。
   • 全体の変化量は \((L - R) \times d\) となります。

この式から、以下のことが分かります。 - \(L < R\) （右側に人が多い）なら、右に動かすほど総距離が減る。 - \(L > R\) （左側に人が多い）なら、左に動かすほど総距離が減る。 - \(L = R\) （左右の人数が同じ）のとき、総距離の変化が止まり、最小値となります。

つまり、左右の人数が均衡する地点、すなわち中央値が最適な \(P\) となります。

偶数の場合

\(N\) が偶数の場合、中央の値は 2 つ（\(X_{N/2}\) と \(X_{N/2 + 1}\)）存在しますが、その間のどの地点（整数）を \(P\) に選んでも、左右の人数が同じになるため総移動距離は変わりません。そのため、実装上は単純にソート後のリストの真ん中の要素を \(P\) とすれば十分です。

アルゴリズム

1. 与えられた \(N\) 個の座標 \(X_1, X_2, \ldots, X_N\) を昇順にソートします。
2. ソート後の配列において、中央に位置する要素を \(P\) とします（例：X[N // 2]）。
3. 各 \(X_i\) について \(|X_i - P|\) を計算し、その合計を求めます。

計算量

• 時間計算量: \(O(N \log N)\)
  • 座標のソートに \(O(N \log N)\) かかります。
  • 距離の合計の計算は \(O(N)\) です。
  • 全体としてソートが支配的になります。
• 空間計算量: \(O(N)\)
  • 入力された座標を保持するために長さ \(N\) の配列が必要です。

実装のポイント

• ソートの重要性: 中央値を正しく取得するために、必ず最初にソートを行う必要があります。

• 大きな値の扱い: \(X_i\) の値が最大 \(10^9\)、人数 \(N\) が \(2 \times 10^5\) であるため、総移動距離は最大で約 \(2 \times 10^{14}\) 程度になります。Pythonでは整数の大きさに制限はありませんが、他の言語（C++など）を使用する場合は 64bit 整数型（long long など）を使用する必要があります。

  ソースコード

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nの取得
    n = int(input_data[0])
    # X_iのリストを取得
    x = [int(val) for val in input_data[1:]]
    
    # 座標をソートする
    x.sort()
    
    # 総移動距離を最小にするPは中央値である。
    # Nが奇数の場合は中央の要素、偶数の場合は中央の2つの要素の間の任意の整数がPとなる。
    # ここでは x[n // 2] をPとして選択する。
    p = x[n // 2]
    
    # 各友人からの移動距離の合計を計算
    ans = 0
    for xi in x:
        ans += abs(xi - p)
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。