Competitive Programing Typical 90 Problem day10

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の高速化
• いずれも面白そうなので、別の機会に入門するとする。

バイバイ！