AtCoder ABC 177の復習

前回の続き

177のC問題ができなかったので、解説を見て再実装しました。
C - Sum of product of pairs

実際にTLEとなった実装は以下

n=int(input())
sum=0
a=list(map(int, input().split()))
for i in range(n):
  for j in range(i+1, n):
    #print(i,j)
    sum+=a[i]*a[j]
  sum = sum%((10**9)+7)

print(sum)

解き始め当初は、
あーどう考えてもO(n**2)やん、どうすればいいの・・・と頭が固ーくなってました。
配列の前後の数値を使ってみたり、pypy使ってみたりと小手先の手法を色々試しましたが当然ダメでした。

解説を見て、先に合計値を計算してから順に当てはめていくことを試すと、サクッと解けました
うーん、これはきちんと紙に書いて自分でひらめくべきだった・・・。

n=int(input())
sums=0
a=list(map(int, input().split()))
b = sum(a)
for i in range(n):
  b -= a[i]
  sums += a[i]*b
  sums = sums%((10**9)+7)
print(sums)

やっぱりじっくり腰を据えてやる時間が欲しいなぁ

それから、D, E, F問題の解説を一応確認しておきます。
アルゴリズムの名前だけでも知っておきたいから・・・。

D...Union-Findを用いて解ける問題
E...高速素因数分解、およびエラトステネスの篩を用いて解ける問題
F...セグメント木、順序集合を用いて解ける問題

エラトステネスの篩は後ほど実装したい！

以上。