【競プロ典型90問】010の解説（python）

概要

競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。

※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）

問題010-Score Sum Queries

問題概要

N人の生徒が2つの組に分けられている時、各クラスの学籍番号L~R番の合計点を求める。
これをQ個のクエリにて行う。

解き方

まず初めに、愚直にQ個のクエリ1つ1つに対して、L~R番までの合計を都度求める方法が考えられますが、
この考えでは、L~R番までの合計を求める処理で、最大N回、
これを最大Q回行うと $O(QN)$ となり、TLEになってしまいます。

そこで今回は、累積和を用います。
※累積和について知りたい方はこちらをご確認ください。

そうすると、
１. 各組の累積和Sを求める(N回)

２. Q個のクエリに対して、$S[R]-S[L-1]$を求める。（$O(1)$をQ回）

となり、これは$O(N+Q)$の計算量で十分に高速に求められます。

引用元：競プロ典型90問 Github

実装

N = int(input())

# 1組、2組で分けて得点を格納する
c1 = [0]*N
c2 = [0]*N

for i in range(N):
  c, p = map(int, input().split())
  if c == 1:
    c1[i] = p
  else:
    c2[i] = p

# 各組で累積和 s1, s2を求める
s1 = [0]*(N+1)
s2 = [0]*(N+1)

for i in range(N):
  s1[i+1] = s1[i] + c1[i]
  s2[i+1] = s2[i] + c2[i]

# Q個のクエリに対し、L~R番までの合計を求める
# L番は和に含めるため、L-1番までの合計をマイナスする
Q = int(input())

for _ in range(Q):
  l, r = map(int, input().split())
  sum1 = s1[r] - s1[l-1]
  sum2 = s2[r] - s2[l-1]
  print(sum1, sum2)

最後に

問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）

ここまでお読みいただきありがとうございました。