こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【19日目】」ということで、2020年12月19日に行われたABC186のD問題を解きたいと思います。

問題

D - Sum of difference

問題ページ

問題文

$N$ 個の整数 $A_1, ... ,A_N$ が与えられます。

$1 \leqq i \lt j \leqq N$ を満たす全ての $i,j$ の組についての $|A_i − A_j|$ の和を求めてください。

すなわち、 $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N} | A_i − A_j |$ を求めてください。

制約

$2 \leqq N \leqq 2 \times 10 ^ 5$
$|A_i| \leqq 10 ^ 8$
$A_i$ は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1\ ...\ A_N$

出力

答えを出力せよ。

ゆーてぃーの解法

絶対値の考え方がめんどくさいので、 $A_i$ を降順にソートします。求めるものが差の絶対値なので答えに影響はありません。各 $A_i -A_j$ を書いていきすべてを足していくと、 $(N-1) \times A_1 +(N-1-2) \times A_2 +(N-1-4) \times A_3 + ...$ となるのでこれをfor文を使って計算すれば求められます。