【ABC194 C】「Squared Error」を解く【Python3】

コンテスト一覧へ

 

与えられた数列Aの各要素同士の差の2乗の和を求める問題です。

提出
n = int(input())
a = list(map(int, input().split()))

ans = (n-1)*a[0]**2
b = a[0]

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

print(ans)

2≦N≦3×105 なので、 (Ai – Aj)2 の計算を愚直にする方法では間に合いません。

そこで、

(Ai – Aj)2 = Ai2 – 2AiAj + Aj2

となることを利用して計算します。

問題文から、i > j となる (Ai – Aj)2 を求めればいいことが分かります。

for文を用いて、それぞれのAiに対して、(N-1)×Ai2、2×Ai×b を求めます。

b は、それまでのAiの総和です。

A2 のときは、2×A2×(A1)、A3 のときは、2×A3×(A1+A2)となります。

これらを「ans」に加えていき、最後に「ans」を出力します。

【ABC194】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。