概要

高橋君の家計簿において、指定された日付の取引を順次削除した後の最終残高を求める問題です。

考察

この問題では、毎回すべての取引を足し直さなくても、初期の合計金額から削除された取引を引いていけば良いことに気づくことが重要です。

例えば、最初に全取引の合計を計算しておけば、ある日 \(d\) の取引 \(A_d\) を削除する操作は、単純にその金額を合計から引くだけで済みます。これにより、毎回 \(N\) 個の要素全てを走査する必要がなくなり、効率よく処理できます。

また、同じ日を二度削除しないという制約があるため、すでに削除済みの日を再度処理しないようにフラグ管理を行う必要があります。

このように、全体の合計を前計算しておき、そこから差分だけを更新していくという考え方がポイントです。

アルゴリズム

1. 最初に全取引の合計値 total を計算します：
   $\( \text{total} = \sum_{i=1}^{N} A_i \)$

2. 各操作について以下のように処理します：

   • 削除する日 \(D_j\) に対応する取引 \(A[D_j - 1]\) がまだ削除されていなければ、
     • total からその金額を引く
     • 削除済みフラグを立てる
   • 現在の total を結果リストに追加

この方法により、各クエリに対して定数時間で処理が可能になります。

計算量

• 時間計算量: \(O(N + Q)\)
  • 初期合計計算が \(O(N)\)、各クエリ処理が \(O(1)\) × \(Q\) 回
• 空間計算量: \(O(N)\)
  • 入力配列と削除フラグ用の配列による

実装のポイント

• インデックスは0始まりなので、日付 \(D_j\) は \(D_j - 1\) として扱う必要があります。

• 同じ日を複数回削除しないよう、bool型の配列で管理します。

• 高速入力が必要な場合のために、sys.stdin.readなどの使用を検討するとよいです。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    A = list(map(int, data[2:2+N]))
    D = list(map(int, data[2+N:2+N+Q]))
    
    # 初期の合計を計算
    total = sum(A)
    
    # 削除されたかどうかを管理する配列
    removed = [False] * N
    
    results = []
    for d in D:
        idx = d - 1  # 0-indexedにする
        if not removed[idx]:
            total -= A[idx]
            removed[idx] = True
        results.append(total)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。