概要

\(N\) 日間の取引記録の合計から、指定された日の取引を順次削除していき、各削除後の口座残高を求める問題です。

考察

重要な気づき

口座残高は、すべての取引の総和に等しいという点がポイントです。

例えば、\(A = [100, -50, 200]\) の場合： - 1日目終了時：\(100\) 円 - 2日目終了時：\(100 + (-50) = 50\) 円 - 3日目終了時：\(100 + (-50) + 200 = 250\) 円

最終的な残高は \(A_1 + A_2 + \cdots + A_N\) という単純な総和になります。

素朴なアプローチの問題点

もし各クエリごとに「削除されていない日の取引をすべて足し合わせる」という方法を取ると、1回のクエリで \(O(N)\) の計算が必要です。\(Q\) 回のクエリがあるので、全体で \(O(NQ)\) となり、\(N, Q\) が最大 \(2 \times 10^5\) の場合は TLE（時間超過）の危険があります。

解決方法

差分更新を使います。

• 最初に全取引の総和 total を計算しておく
• 取引を削除するたびに、total からその取引額を引くだけで新しい残高が求まる

こうすれば、各クエリを \(O(1)\) で処理できます。

アルゴリズム

1. 前処理: 配列 \(A\) の総和を計算し、変数 total に格納する
2. 各クエリの処理:
   • 削除する日 \(D\) を読み込む
   • total から \(A_{D}\)（\(D\) 日目の取引額）を引く
   • 更新後の total を出力する

具体例

\(N = 4, Q = 2\)、\(A = [100, -30, 50, -20]\) の場合：

• 初期の total = \(100 + (-30) + 50 + (-20) = 100\)

クエリ1: \(D = 2\)（2日目を削除） - total = \(100 - (-30) = 130\) - 出力: 130

クエリ2: \(D = 4\)（4日目を削除） - total = \(130 - (-20) = 150\) - 出力: 150

計算量

• 時間計算量: \(O(N + Q)\)
  • 初期の総和計算に \(O(N)\)
  • 各クエリの処理に \(O(1)\) × \(Q\) 回 = \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保持するため

実装のポイント

• 1-indexed と 0-indexed の変換: 問題文では日数が 1 から始まる（1-indexed）ですが、Python のリストは 0 から始まる（0-indexed）ため、\(D\) 日目の取引は A[D - 1] でアクセスします。

• 整数の範囲: \(A_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、総和は最大で約 \(2 \times 10^{14}\) になります。Python では整数のオーバーフローを気にする必要はありませんが、他の言語では long long 型などを使う必要があります。

  ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 初期の合計を計算
    total = sum(A)
    
    # 各クエリを処理
    for _ in range(Q):
        D = int(input())
        # D日目の取引を削除（1-indexed なので D-1）
        total -= A[D - 1]
        print(total)

if __name__ == "__main__":
    main()

---

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