Day 10.
It is easy game, because it is just cumulative sumation of array until i th element.
Now I know how much pre-processing is important when we want to decrease calculation cost.
Code is below.
#day 10
N = int(input())
sum_score = [[0]*2 for _ in range(N+1)]
for j in range(N):
c,p = map(int,input().split())
sum_score[j+1][c%2] = sum_score[j][c%2] + p
sum_score[j+1][(c+1)%2] = sum_score[j][(c+1)%2]
Q = int(input())
for i in range(Q):
l,r = map(int,input().split())
score_1 = sum_score[r][1]-sum_score[l-1][1]
score_2 = sum_score[r][0]-sum_score[l-1][0]
print(score_1,score_2)
- 区間の総和を求めたいなら、累積和を利用すれば、毎回アクセスするだけで、すぐに求まるという話。
- 累積和について、こちらの記事がわかりやすかった。まとめる。
- 出来ること
- 配列のうち、K個の連続する整数の和の最大値を求める。
- 愚直にも出来る
- 2017に似た数字の数
- ある条件を満たす数がこれまでいくつあったか、という累積和
- エラストテネスのふるい
- 文字列が区間の中に、何回登場するか
- 区間内の値の総和が0になるものの個数
- 累積和のリストを作って、累積和に出てきた数をカウント
- 累積和は引き算以外にも使える。(加減乗除)
- しゃくとりは、芋虫みたいに、後ろを固定して、前を進めて、何かしらの条件を満たしたら、後ろをちょっと進める、のを繰り返す。
- ただ、この時、前を後ろに戻さない
- なので、今回の問題には適していない。
- 累積和のリストを作って、累積和に出てきた数をカウント
- 二次元累積和
- 二次元で累積和をとると、長方形の面積が出てくる。
- それを包除原理と組み合わせれば、特定の場所の値の総和が出てくる。
- 他の手法
- いもす法
- しゃくとり法
- BIT, Segment Tree
- ローリングハッシュ
- DPの高速化
- 配列のうち、K個の連続する整数の和の最大値を求める。
- いずれも面白そうなので、別の機会に入門するとする。
バイバイ!