ただのメモ

他の人に見せても良い方のメモ

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

バイバイ!