公式
A - 成績管理システム / Grade Management System 解説 by admin
DeepSeek V3概要
この問題は、生徒のスコアを管理し、スコアの移動・比較・一斉加点という3種類のクエリを処理するシステムを実装するものです。
考察
素朴なアプローチでは、各クエリをそのまま実装することが考えられます。しかし、制約条件(\(N, Q \leq 5000\))を考慮すると、種類2のクエリ(スコア比較)と種類3のクエリ(一斉加点)で単純にループ処理を行うと、最悪ケースで\(O(NQ)\)の計算量となり、\(5000 \times 5000 = 25,000,000\)回の操作が必要になります。これはPythonでは時間制限に間に合わない可能性があります。
しかし、実際の制約では\(N\)と\(Q\)が最大5000までという比較的小さな値であるため、適切に実装すれば単純なループ処理でも十分に実行可能です。この問題の特徴は、クエリが時系列順に与えられ、過去の操作結果がその後の操作に影響する点にあります。また、スコアが負の値になることも許容される点にも注意が必要です。
アルゴリズム
この実装では、単純な配列を用いた直接的なアプローチを採用しています:
- サイズ\(N+1\)の配列
scoresを用意し、すべての生徒のスコアを0で初期化 - 各クエリを順次処理:
- 種類1(スコア移動): 生徒\(a\)のスコアから\(v\)を減算、生徒\(b\)のスコアに\(v\)を加算
- 種類2(スコア比較): 生徒\(x\)のスコアを基準値とし、区間\([l, r]\)内の全生徒を走査して基準値より大きいスコアを持つ生徒数をカウント
- 種類3(一斉加点): 区間\([l, r]\)内の全生徒のスコアに\(v\)を加算
計算量
- 時間計算量: \(O(NQ)\)(最悪ケース)
- 空間計算量: \(O(N)\)
最悪ケースでは、すべてのクエリが種類2または種類3で、かつ毎回全範囲を処理する場合、\(5000 \times 5000 = 25,000,000\)回の操作が必要になりますが、これはPythonでも十分に処理可能な範囲です。
実装のポイント
- 入力処理: クエリの種類によって引数の数と順序が異なるため、注意深くパースする必要があります
- 配列のインデックス: 生徒番号は1-indexedですが、配列は0-indexedなので、インデックス調整が必要です
- 基準値の取得: 種類2のクエリでは、まず生徒\(x\)の現在のスコアを取得して基準値とします
- 範囲指定: 種類2と種類3では、区間\([l, r]\)を処理するため、ループの範囲を
range(l, r+1)とします
この実装はシンプルで直感的であり、制約条件内で効率的に動作します。
ソースコード
import sys
def main():
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
q = int(data[1])
index = 2
queries = []
for i in range(q):
t = int(data[index]); index += 1
if t == 1:
a = int(data[index]); b = int(data[index+1]); v = int(data[index+2]); index += 3
queries.append((1, a, b, v))
elif t == 2:
x = int(data[index]); l = int(data[index+1]); r = int(data[index+2]); index += 3
queries.append((2, x, l, r))
else:
l = int(data[index]); r = int(data[index+1]); v = int(data[index+2]); index += 3
queries.append((3, l, r, v))
scores = [0] * (n + 1)
output_lines = []
for query in queries:
if query[0] == 1:
_, a, b, v = query
scores[a] -= v
scores[b] += v
elif query[0] == 2:
_, x, l, r = query
base = scores[x]
count = 0
for i in range(l, r + 1):
if scores[i] > base:
count += 1
output_lines.append(str(count))
else:
_, l, r, v = query
for i in range(l, r + 1):
scores[i] += v
print("\n".join(output_lines))
if __name__ == "__main__":
main()
この解説は deepseekv3 によって生成されました。