AtCoder Beginner Contest 177 C - Sum of product of pairs の解法考察 Pythonで書いてます
問題はこちら
C - Sum of product of pairs
これ数列Aがもし
1, 2, 3, 4, 5
だとしたら求めたい答えって
1*2+1*3+1*4+1*5
2*3+2*4+2*5
3*4+3*5
4*5
の総和
つまり
1*(2+3+4+5)
2*(3+4+5)
3*(4+5)
4*5
の総和じゃん、までは分かって以下のコードを提出するとTLEじゃん
N = int(input()) A = list(map(int, input().split())) ans = 0 for i in range(N): ans += A[i] * sum(A[i + 1 :]) ans %= 10 ** 9 + 7 print(ans)
んで累積和ってやつを知りました。
N = int(input()) A = list(map(int, input().split())) sum_A = sum(A) C = [0] * N - 1 # 累積和作成 for i in range(N - 1): sum_A -= A[i] C[i] = sum_A ans = 0 for i in range(N - 1): ans += A[i] * C[i] ans %= 10 ** 9 + 7 print(ans)
ループの中で和を計算するよりも予め作っておくってわけですが、そうですね。その方が早いですね。
まだまだ精進が足りません、、
累積和がどうゆうもので、どうゆうときに使うのかが初歩の初歩レベルで分かる良い問題でした。