Official

A - 成績管理システム / Grade Management System Editorial by admin

GPT 5.2 High

概要

各生徒のスコアを配列でそのまま管理し、クエリの指示通りに更新・区間走査して「基準より大きい人数」を数える問題です。

考察

この問題の操作は次の3種類です。

  • 種類1:2点更新(\(a\) を \(-v\)、\(b\) を \(+v\))
  • 種類2:ある基準値(生徒 \(x\) のスコア)より大きい生徒を区間 \([l,r]\) で数える
  • 種類3:区間 \([l,r]\) の全員に \(+v\)

一見すると「区間加算」と「区間内で条件を満たす個数」という組み合わせなので、セグメント木やBITなどの高度なデータ構造を考えたくなります。しかし、種類2は「基準値が毎回変わる(しかも配列の任意要素)」ため、単純な区間和のようには扱えず、構造化が難しいです。

ここで重要なのは制約です:

  • \(N \le 5000\)
  • \(Q \le 5000\)

つまり最悪でも \(N \times Q = 25{,}000{,}000\) 程度のループ回数です。Pythonでも十分現実的な量なので、素直に配列を持って、必要な区間はその場で走査する方針で間に合います。

素朴なアプローチがTLEになり得る典型は \(N,Q \le 2\times 10^5\) のような場合ですが、本問ではそこまで大きくないため、むしろ実装が簡潔でバグりにくいこの方法が有効です。

アルゴリズム

スコアを score[1..N](初期値0)で管理します。

  • 種類1 1 a b v
    score[a] -= v, score[b] += v とする(2要素の更新)。

  • 種類2 2 x l r
    まず基準値 base = score[x] を取る。
    次に \(i=l..r\) を順に見て、score[i] > base ならカウントを増やす。
    最後にカウントを出力する。

  • 種類3 3 l r v
    \(i=l..r\) の全てについて score[i] += v を行う(区間をそのまま更新)。

例えば、種類2では「問い合わせ時点の \(score[x]\)」が基準なので、先に base を固定してから区間を走査するのがポイントです(走査中に基準が変わることはありません)。

計算量

  • 時間計算量: \(O(NQ)\)(種類2・3が最悪でそれぞれ区間長 \(O(N)\)、それが最大 \(Q\) 回)
  • 空間計算量: \(O(N)\)(スコア配列)

実装のポイント

  • 1-indexed(score = [0]*(N+1))にして、生徒番号と添字を一致させるとミスが減ります。

  • 入力が最大で \(Q=5000\) とはいえ、Pythonでは高速化のために sys.stdin.buffer.read() で一括読み込みしています。

  • スコアの絶対値が大きくなり得ますが、Pythonの int は任意精度なのでそのまま扱えます。

  • 種類2の比較は「真に大きい」なので条件は >(>= ではない)です。

    ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    score = [0] * (N + 1)
    out = []

    for _ in range(Q):
        t = next(it)
        if t == 1:
            a = next(it)
            b = next(it)
            v = next(it)
            score[a] -= v
            score[b] += v
        elif t == 2:
            x = next(it)
            l = next(it)
            r = next(it)
            base = score[x]
            cnt = 0
            s = score
            for i in range(l, r + 1):
                if s[i] > base:
                    cnt += 1
            out.append(str(cnt))
        else:  # t == 3
            l = next(it)
            r = next(it)
            v = next(it)
            s = score
            for i in range(l, r + 1):
                s[i] += v

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。