ABC405 C問題 – Sum of Product

本番では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)

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

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

コメント

タイトルとURLをコピーしました