ABC177 C - Sum of product of pairs から学んだ

4566 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

無心になったが、とりあえず
サンプルも読む。

なるほど。
例えば** 1 2 3 4 が与えられたとすると
**1x2+(1+2)x3+(1+2+3)x4とならないか？

後は表現方法が問題だ。
だがしかし、tle & wa

ans.py
N = int(input())
A = list(map(int,input().split()))

score = A[0]*A[1]

for i in range(2,N):          #計算量 O(N)
    score += sum(A[:i])*A[i]  #計算量 O(N)...合算してほぼ O(N^2)
    score %= 7+10**9
print(score)

配列の sum の計算量は配列長さに依存する。
なので最終的には、それだけで O(N) となりうる。
っということで書き換えたら、通った。

ans_r1.py
N = int(input())
A = list(map(int,input().split()))

X = sum(A)
score = 0

for i in range(N-1,0,-1):
    score += (X-A[i])*A[i]
    score %= 7+10**9
    X -= A[i]
print(score)