概要

\(N\) 人の生徒の身長が与えられ、すべての異なる2人組について身長差の絶対値の総和を求める問題。

考察

素朴な方法として、すべてのペア \((i, j)\) （\(i < j\)）に対して \(|A_i - A_j|\) を計算して足し合わせる方法がある。しかし、この方法の計算量は \(O(N^2)\) であり、\(N\) が最大 \(2 \times 10^5\) まであるため、時間制限に間に合わない（TLE）。

そこで、効率的に計算する方法を考える。身長差の合計を高速に求めるためには、各要素が最終的な答えにどれだけ寄与するかを考えるのが有効である。

ここで、身長を昇順にソートしておくことを考える。ソートすることで、「ある要素より大きい要素との差」をまとめて扱うことができる。

例えば、身長が昇順に \(A_0, A_1, ..., A_{N-1}\) となったとする。このとき、ある要素 \(A_i\) について：

• \(A_i\) より左（インデックスが小さい）にある要素は \(i\) 個あり、それらはすべて \(A_i\) よりも身長が小さい（または等しい）。
• \(A_i\) より右（インデックスが大きい）にある要素は \(N - 1 - i\) 個あり、それらはすべて \(A_i\) よりも身長が大きい（または等しい）。

したがって、\(A_i\) が他の要素との差に寄与する分は： - 左側の要素との差の和：\(A_i\) が引かれる回数が \(i\) 回 → 合計で \(+A_i \cdot i\) - 右側の要素との差の和：\(A_i\) が引く回数が \(N - 1 - i\) 回 → 合計で \(-A_i \cdot (N - 1 - i)\)

これを整理すると、要素 \(A_i\) の寄与は：

\[ A_i \cdot i - A_i \cdot (N - 1 - i) = A_i \cdot (2i - N + 1) \]

この式を用いることで、各要素の答えへの寄与を \(O(1)\) で求めることができ、全体の計算量を \(O(N)\) に抑えることができる。

アルゴリズム

1. 入力を受け取り、身長のリストを昇順にソートする。
2. 各要素 \(A_i\) について、その要素が答えに寄与する量 \(A_i \cdot (2i - N + 1)\) を計算し、合計に加える。
3. 合計を出力する。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(1)\)（入力除く）

実装のポイント

• 必ず身長をソートすること。
• 式 \(A_i \cdot (2i - N + 1)\) の符号と係数に注意。
• Python では sort() を使うだけで昇順ソートされる。

## ソースコード

```python
n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = 0
for i in range(n):
    ans += a[i] * (2 * i - n + 1)

print(ans)

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