初めに
いすも法と尺取り法は別記事でやります
累積和とは
簡単に言えば、最初に下準備してその後の質問に爆速で答えるものです
例えば、、、
１ ２ ３ ４ ５ ６ ７ ８ ９
ていう配列があるとする（最初は０番目と考える）
０番目から２番目まで全て足すと？
６だよね
じゃあ０番目から５番目は？
２１だよね
でもいちいち足すのめんどくさいよね
ここで累積和を使う
１ ３ ６ １０ １５ ２１ ２８ ３６ ４５
↑０番目から足したやつ
これ見たら答えるの速くなる
実装
１ ２ ３ ４ ５ ６ ７ ８ ９
↓ 最初を足す
０ ０ ０ ０ ０ ０ ０ ０ ０ ←数ぶん作る
１ ２ ３ ４ ５ ６ ７ ８ ９
↓ 足す
１ ０ ０ ０ ０ ０ ０ ０ ０
↑ 前の足す
プログラミング
この問題をやる
N = int(input())
A = list(map(int, input().split()))
# 累積和を求める
# acc[k]: 左から k 個分の総和
acc = [0] * (N+1)
for idx, a in enumerate(A):
acc[idx+1] = acc[idx] + a
# 質問に答える
Q = int(input())
for _ in range(Q):
k = int(input())
print(acc[k])こんな感じ
最後に
累積和は、まだ簡単にできるので極めれば強い
がんばれ！！
コメント