概要

\(N\) 人の生徒のすべてのペアについて、その身長差（絶対値）を計算し、その総和を求める問題です。

考察

素朴なアプローチ

すべてのペア \((i, j)\) を二重ループで調べると、ペアの数は \(\frac{N(N-1)}{2}\) 個となります。制約の \(N \leq 2 \times 10^5\) では、計算回数が約 \(2 \times 10^{10}\) 回に達してしまい、実行時間制限（通常 2 秒程度）に間に合いません。計算量を落とす工夫が必要です。

ソートによる絶対値の解消

絶対値 \(|A_i - A_j|\) の計算を難しくしているのは、どちらの身長が高いかによって計算式が変わる点です。 ここで、身長のリスト \(A\) を昇順（小さい順）にソートしてみます。ソートしても「すべてのペアの差の総和」という答え自体は変わりません。

ソート後の配列を \(A_0, A_1, \dots, A_{N-1}\) とすると、常に \(i < j\) ならば \(A_i \leq A_j\) が成り立ちます。これにより、絶対値記号を外して \(|A_j - A_i| = A_j - A_i\) として計算できるようになります。

各要素の「貢献度」を考える

ソートされた配列において、各要素 \(A_i\) が最終的な総和にどのように寄与するかを数え上げます。

ある要素 \(A_i\)（0-indexed）に注目すると： - \(A_i\) より小さい（または等しい）要素は、自分より左側に \(i\) 個あります。これらの要素とのペアでは、 \(A_i\) は「引かれる側」ではなく「足される側」になり、計 \(i\) 回加算されます。 - \(A_i\) より大きい（または等しい）要素は、自分より右側に \((N - 1 - i)\) 個あります。これらの要素とのペアでは、 \(A_i\) は「引かれる側」になり、計 \((N - 1 - i)\) 回減算されます。

したがって、各 \(A_i\) が合計に与える影響は以下の式で表せます： $\(A_i \times (i - (N - 1 - i)) = A_i \times (2i - N + 1)\)$

この式をすべての \(i\) について計算し合計することで、 \(O(N)\) で答えを求めることができます。

アルゴリズム

1. 入力された身長のリスト \(A\) を昇順にソートする。
2. 総和を保持する変数 ans を \(0\) で初期化する。
3. \(i = 0\) から \(N-1\) まで以下を繰り返す：
   • ans に \(A_i \times (2i - N + 1)\) を加算する。
4. 最終的な ans の値を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 身長のソートに \(O(N \log N)\) かかります。その後の総和計算は \(O(N)\) であるため、全体の計算量はソートが支配的になります。
• 空間計算量: \(O(N)\)
  • \(N\) 個の要素を格納する配列が必要です。

実装のポイント

• 大きな数への対応: 答えは非常に大きな値になる可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

• 高速な入力: \(N\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと効率的です。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nを取得
    n = int(input_data[0])
    # 身長リストAを取得
    a = list(map(int, input_data[1:]))
    
    # 身長を昇順にソートする
    # ソートすることで絶対値記号を外して計算できるようになる
    a.sort()
    
    # 総和を計算する
    # 各要素 a[i] が何回足され、何回引かれるかを考える
    # インデックス i (0-indexed) の要素 a[i] について：
    # 自分より小さい要素は i 個あり、それらとの差では a[i] は正の項になる
    # 自分より大きい要素は (n - 1 - i) 個あり、それらとの差では a[i] は負の項になる
    # したがって、a[i] の係数は i - (n - 1 - i) = 2*i - n + 1 となる
    ans = 0
    for i in range(n):
        ans += (2 * i - n + 1) * a[i]
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

---

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