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 によって生成されました。