ABC194 C問題

解法1(自力バージョン)

いくつかのパターンを試して計算の法則を強引に見つけた．

下式のように変形できることから，配列の要素を2乗した値が何回出てくるかと，2*(A_i * A_j) が何回どのように出てくるかを調べれば問題が解けると思いテストケースを試してみた．

結果，各要素の2乗は(N-1)個，-2*(A_i * A_j)の部分はその要素までの累積和を求めて2をかければよいことに気づいた．

import itertools
import operator
N = int(input())
A = list(map(int, input().split()))
#print(A)
A_sum = list(itertools.accumulate(A)) 
#print(A_sum)
A_2 = list(map(lambda x: x ** 2, A))
#print(A_2)
ans = 0
for i in range(N):
 ans += (N-1)* A_2[i]
 if i != 0:
   ans -= 2*(A[i] * A_sum[i-1])
print(ans)
        

解法2(模範解答)

上記のやり方は完全に根性で導き出しましたが，今回の問題は適切に式展開を行って行けばO(N)まで持っていくことができます．

おそらく引っかかるところは①と②の式変形だと思います．

①の部分は実際に計算する添え字の組み合わせをn=3の時を例にしたものを考えればわかりやすいです．上の図のように○の部分が計算すべき場所であり，i=jのときはここは0になります．つまり求める場所は全体/2と等しくなります．

②の部分は上の図のような式変形を基にしています．

あとは最後の式を実装すれば完成です