D - 身長差の総和 / Sum of Height Differences Editorial
by 
MMNMM
必要なら少しの摂動を加えることで、答えに影響しないまま \(A _ i\) はすべて異なるとしてよいです。
\(|A _ i-A _ j|\) は \(i,j\) について対称なので、\(A _ i\) を好きに並べ替えても答えは変わりません。
並べ替えてよいことの証明
列 \(A\) と \(f(x,y)=f(y,x)\) を満たす \(f\) について、\((A _ i,A _ j)\ (1\le i\lt j\le N)\) すべてに対する \(f(A _ i,A _ j)\) の値の合計を求めることを考えます。
\(1\le i\lt N\) に対して、\(A _ i,A _ {i+1}\) を入れ替えたときに答えが変わらないことを示します。
\(1\le k\lt i\) に対する \((A _ k,A _ i),(A _ k,A _ {i+1})\) や、\(i+1\lt k\le N\) に対する \((A _ i,A _ k),(A _ {i+1},A _ k)\) については、入れ替えによる組としての変化はありません。
\((A _ i,A _ {i+1})\) についての計算のみ \((A _ {i+1},A _ i)\) についての計算になりますが、対称性よりこれの計算結果が等しいので、答えが変わらないことが示されました。
隣接する \(2\) 要素を入れ替えることを繰り返して列を好きなように並べ替えることができるので、\(A _ i\) の値を自由に並べ替えても答えが変わらないことが示されました。
よって、\(A _ i\) を昇順に並べ替えておきます。 すると、\(1\le i\lt j\le N\) に対する \(|A _ i-A _ j|\) の値は \(A _ j-A _ i\) となります。 このことから、\[\begin{aligned}\sum _ {i=1} ^ {N-1}\sum _ {j=i+1} ^ N(A _ j-A _ i)&{}=\sum _ {i=1} ^ {N-1}\sum _ {j=i+1} ^ NA _ j-\sum _ {i=1} ^ {N-1}\sum _ {j=i+1} ^ NA _ i\\&{}=\sum _ {j=2} ^ N(j-1)A _ j-\sum _ {i=1} ^ {N-1}(N-i)A _ i\\&{}=\sum _ {i=1} ^ N(2i-N-1)A _ i\end{aligned}\] と整理できます。
あとは、これに従って答えを求めればよいです。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int& a : A) {
cin >> a;
}
ranges::sort(A); // 昇順に並べ替える
long ans = 0;
for (int i = 0; i < N; ++i) {
ans += A[i] * static_cast<long>(i * 2 - N + 1); // 0-indexed なので少し式が変わることに注意
}
cout << ans << endl;
return 0;
}
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i, a in enumerate(sorted(A)): # 昇順に並べ替える
ans += a * (i * 2 - N + 1) # 0-indexed なので少し式が変わることに注意
print(ans)