Official

C - Squared Error Editorial by QCFium


求める式をそのまま計算すると時間計算量が \(\Theta(N^2)\) となって TLE になります。

解法 \(1\)

\(|A_i| \le 200\) という制約を利用します。
\(N\) は大きくても出現する値の種類数は小さいので、同じ値の要素をまとめて処理します。
まず
\(\mathrm{cnt}_i : A\)\(i\) が何個出現するか
という数列を計算します。添字が負になる可能性があるため、実際の実装ではすべての添字に \(200\) を足すなどすると良いでしょう。
そして各 \(i, j (-200 \le i \lt j \le 200)\) について \(\mathrm{cnt}_i \times \mathrm{cnt}_j \times |i - j|^2\) を求めて足せば答えです。
同じ値同士は差の \(2\) 乗が \(0\) なので答えに影響せず、処理する必要がありません。
答えが32 bit整数型に収まらない可能性があることに注意して、64 bit整数型などを用いて計算してください。
時間計算量は \(O(N + (\max |A_i|)^2)\) です。

解法 \(2\)

\(|A_i| \le 200\) という制約を利用せずとも高速に求めることができます。
\(\sum_{i = 2}^n \sum_{j = 1}^{i - 1} (A_i - A_j)^2\)
\( = \frac{1}{2}(\sum_{i = 1}^n \sum_{j = 1}^{n} (A_i - A_j)^2)\) \(((A_i - A_i)^2 = 0\) なので \()\)
\( = \frac{1}{2}(\sum_{i = 1}^n \sum_{j = 1}^{n} (A_i^2 + A_j^2 - 2A_iA_j))\)
\( = \frac{1}{2}(2N \sum_{i = 1}^n A_i^2 -2 \sum_{i = 1}^n (A_i \sum_{j = 1}^n A_j))\)
\( = N\sum_{i = 1}^n A_i^2 - (\sum_{i = 1}^n A_i)^2\)

と変形でき、最後の式は \(O(N)\) で計算できます。
同様に32 bit整数型のオーバーフローには注意してください。

posted:
last update: