AtCoder - Score Sum Queries -

AtCoder - Score Sum Queries

問題リンク

AtCoder Typical90 J

解法

この問題は、範囲クエリに対する累積和（prefix sum）の応用で解くことができます。

アプローチ

1. 累積和の事前計算

   • 各クラスごとに累積和を計算します。

2. 効率的な範囲内合計の計算

   • 各クエリに対して、事前に計算した累積和を用いて範囲内の合計を求めます。

ステップ

1. 1組と2組の生徒それぞれの点数に対する累積和を別々に持つ配列を作成します。
2. 各クエリに対して、指定された範囲で累積和を使い、合計を計算します。

実装

# 入力の読み込み
N = int(input())
C = []
P = []
for _ in range(N):
    c, p = map(int, input().split())
    C.append(c)
    P.append(p)

# 累積和を計算
# class1_sum[i]: 学籍番号1~iまでの1組の点数合計
# class2_sum[i]: 学籍番号1~iまでの2組の点数合計
class1_sum = [0] * (N + 1)
class2_sum = [0] * (N + 1)

for i in range(1, N + 1):
    class1_sum[i] = class1_sum[i - 1]
    class2_sum[i] = class2_sum[i - 1]

    if C[i - 1] == 1:
        class1_sum[i] += P[i - 1]
    else:
        class2_sum[i] += P[i - 1]

# クエリの処理
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    # LからRまでの1組と2組の点数合計を出力
    sum_class1 = class1_sum[R] - class1_sum[L - 1]
    sum_class2 = class2_sum[R] - class2_sum[L - 1]
    print(sum_class1, sum_class2)

解説

1. Cリストには各生徒のクラス番号が、Pリストには各生徒の点数が格納されます。
2. class1_sumとclass2_sumの配列を用いて、それぞれ1組、2組の累積和を計算します。累積和は各インデックスまでの点数の合計を保持しています。
3. 各クエリに対して、class1_sum[R] - class1_sum[L-1]で1組の合計点を、class2_sum[R] - class2_sum[L-1]で2組の合計点を効率的に計算し、出力します。

計算量

• 生徒の数に対する累積和を計算する処理はO(N)です。
• 各クエリに対して合計点を計算する処理はO(1)です。
• したがって、全体の計算量はO(N + Q)となり、N, Qが最大100,000でも十分高速に処理できます。