ABC405 C問題 – Sum of Product

C - Sum of Product

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

本番ではTLEになってしまった。

例えばN=4の時、

A1*A2 + A1*A3 + A1*A4 + A2*A3 + A2*A4 + A3*A4 は

A1(A2+A3+A4)+ A2(A3+A4)+A3*(A4) になる。

先にAを合計して、都度合計から一つづつ引いていくとカッコ内は一発で求められるのでO(N)で解ける。

以下のコードでACできた。

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))


n = int(input())
a = i_list()

ans = 0

s = sum(a)

for i in range(n):
    s = s - a[i]
    ans += s * a[i]


print(ans)

競技プログラミングを始めてから累積和というキーワードを初めて聞いた

累積和使えるようになろう、、、