この問題から得られる学び
- 何度も入力データを初めから見る処理になりそうなときは前処理を考える
- l番目からr番目みたいにある区間の和を求めるなら累積和の処理がおすすめかも
010 Score Sum Queries
（問題ページはこちら >>> 010 - Score Sum Queries（★2）)
（公式解説はこちら >>> 010 - 公式解説)
ABC 大学には N 人の一年生が在籍しています。クラスは 2 つあり、学籍番号 i 番の生徒のクラスは Ci組です。今日は期末試験が返却され、学籍番号 i 番の生徒の点数は Pi点でした。以下の形式の質問が Q 個与えられます。j=1,2,…,Q それぞれについて答えてください。
[query = lからr番までの1組の点数合計, 2組の点数合計を出力せよ] (一部表現変更)
環境
Python(3.8.2), PyPy3(7.3.0)
どちらでも動きます
どう考える？
- 1クエリごとに点数データを初めから見直すのは時間かかりそう
N<=10^6, Q<=10^6, O(N*Q) <= 10^12 - TLEになりそうなときは前処理ができないかを考えてみる
- i番目の入力を読み込む毎に, 1組/2組のi番目までの合計点数を出せないかな?
方針
solution.py
#lからr番までの合計点数 = [1~r番までの合計点数 - 1~l-1番までの合計点数]
|--------| |-------------------|----------|
1----(l-1) l-------------------r----------N
#図示すればこんな感じ, 2番目の区間出すためには, 1+2番目の区間 - 1番目の区間でできる
ACコード
main.py
N = int(input())
sum_array = [] # この配列に学籍番号i番目までの1組の点数合計, 2組の点数合計をappendしていく
c1_sum = 0
c2_sum = 0
for _ in range(N):
c, score = map(int, input().split())
if c == 1:
c1_sum += score
else:
c2_sum += score
sum_array.append([c1_sum, c2_sum])
Q = int(input())
for _ in range(Q):
l, r = map(int, input().split())
# 下端の処理をするとき, 1番目からn番目の合計みたいに引き算しなくていい場合を考慮
if l == 1:
c1_l = 0
c2_l = 0
else:
c1_l = sum_array[l-2][0] # 1~l-1番まで(下端)の1組の合計点数
c2_l = sum_array[l-2][1] # 1~l-1番までの2組の合計点数
c1_r = sum_array[r-1][0] # 1~r番まで(上端)の1組の合計点数
c2_r = sum_array[r-1][1] # 1~r番までの2組の合計点数
# 添字が0始まりであることに注意
ans_c1 = c1_r - c1_l
ans_c2 = c2_r - c2_l
print(ans_c1, ans_c2)
終わりに
可能な限りわかりやすくしたかったので冗長なコードになっています。また、自分用のメモとして記事を作成しましたので、何かしらのミスがあった場合にはスルーしていただくか、お手柔らかにご指摘していただけると嬉しいです。