概要

\(N\) 人の会員のポイント残高に対して \(M\) 件の加算処理を順番に行い、残高が負にならないよう \(0\) で下限を設けながら、最終的な各会員の残高を求める問題です。

考察

この問題で押さえるべきポイントは以下の通りです。

基本的な操作

各処理は「指定された会員のポイントに値を加算する」だけですが、加算後に残高が \(0\) 未満になった場合は \(0\) にするというルールがあります。

例えば、会員1の残高が \(100\) のとき、\(V = -150\) の処理が来ると： - \(100 + (-150) = -50\) → 負なので \(0\) に修正

素朴なアプローチで十分か？

\(M\) 件の処理を1つずつ順番にシミュレーションする方法を考えます。各処理は： 1. 対象会員の残高に \(V_j\) を加算 2. 負なら \(0\) にする

この1回の処理は \(O(1)\) で済むため、全体で \(O(N + M)\) となります。\(N, M \leq 10^5\) なので、この素朴なアプローチで十分高速に動作します。

なぜ一括処理ではダメなのか？

「同じ会員への処理をまとめて一括加算すればよいのでは？」と思うかもしれませんが、途中で \(0\) に切り上げる処理が入るため、処理の順番が結果に影響します。例えば：

• 初期残高 \(10\)、処理①: \(-20\)、処理②: \(+30\)
  • 順番通り: \(10 → -10 → 0 → +30 → 30\)（答え: \(30\)）
  • まとめて加算: \(10 + (-20 + 30) = 20\)（答え: \(20\)、不正解）

したがって、必ず順番にシミュレーションする必要があります。

アルゴリズム

1. \(N\) 人分の初期ポイント残高を配列 \(S\) に読み込む。
2. \(M\) 件の処理を順に読み込み、それぞれについて：
   • 対象会員 \(T_j\)（1-indexed）の残高に \(V_j\) を加算する。
   • 加算後の値が \(0\) 未満であれば \(0\) に設定する。
3. 最終的な配列 \(S\) の内容をスペース区切りで出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 初期残高の読み込みに \(O(N)\)、\(M\) 件の処理にそれぞれ \(O(1)\) で合計 \(O(M)\)
• 空間計算量: \(O(N)\)
  • 各会員の残高を保持する配列のみ

実装のポイント

• 1-indexed と 0-indexed の変換: 問題では会員番号が \(1\) から始まりますが、配列は \(0\) から始まるため、S[t - 1] のようにインデックスを \(1\) 引く必要があります。

• 高速な入力: Python では sys.stdin.buffer.read() を使って入力を一括で読み込み、split() で分割する方法が高速です。\(N, M\) が最大 \(10^5\) の場合、通常の input() を繰り返すと遅くなることがあるため、この工夫は重要です。

• 下限の処理: if S[t-1] < 0: S[t-1] = 0 は S[t-1] = max(S[t-1], 0) とも書けますが、条件分岐の方がわずかに高速です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    for _ in range(M):
        t = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        S[t - 1] += v
        if S[t - 1] < 0:
            S[t - 1] = 0
    print(' '.join(map(str, S)))

main()

---

この解説は claude4.6opus-thinking によって生成されました。