【競プロ典型90問】「010 - Score Sum Queries（★2）」解法

2021年12月5日 2022年4月5日

TheLogicalBear

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

010 - Score Sum Queries（★2）

ポイント

素直に考えると、1組と2組の点数リストをそれぞれ作成し、クエリの度に合計を計算すれば良さそう

ですが、残念ながらこの方法だとTLEとなってしまいます。

そこで、もっと処理を早くするために、具体的にはクエリの度に合計を計算しなくても良いように

各クラスごとにリストを作成し、各出席番号の生徒までの合計点を格納します。

そして、各クエリに対して

　R番目までの生徒の合計点数から L-1番目までの生徒の合計点数を引いた値を返します。

入力例1では下記の処理を行います。

コード

def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline

    # 各クラスごとにリストを作成し、各出席番号の生徒までの合計点を格納
    N = int(input())
    c1 = [0]  # クラス1のリスト
    c2 = [0]  # クラス2のリスト

    for _ in range(N):
        _c, _p = map(int, input().split(" "))
        if _c == 1:  # 入力がクラス1の生徒の場合
            c1.append(c1[-1] + _p)  # 1つ前の生徒までの合計点に新しい点数を足した値を追加する
            c2.append(c2[-1])  # クラス2は新しい点数を0として追加する
        else:
            c1.append(c1[-1])
            c2.append(c2[-1] + _p)

    # クエリの処理
    Q = int(input())
    for _ in range(Q):  # R番目までの生徒の合計点数 から L-1番目までの生徒の合計点数を引いた値を返す
        _l, _r = map(int, input().split(" "))
        print(c1[_r] - c1[_l - 1], c2[_r] - c2[_l - 1])


if __name__ == '__main__':
    main()

この記事を書いた人

TheLogicalBear