概要

\(N\) 台の作業台に部品が置かれており、スイッチ操作によって部品を隣の作業台に移動（または排出）する処理を \(Q\) 回シミュレーションし、最終的な各作業台の部品数を求める問題です。

考察

まず、各操作で何が起こるかを整理しましょう。

• 作業台 \(i\) (\(1 \leq i \leq N-1\)) のスイッチを押す → 作業台 \(i\) の部品がすべて作業台 \(i+1\) に移動する
• 作業台 \(N\) のスイッチを押す → 作業台 \(N\) の部品がすべて排出される（0個になる）

各操作は「1つの作業台の値を0にして、隣に加算する（または消す）」だけなので、1回の操作は \(O(1)\) で処理できます。

具体例で確認してみましょう。\(N = 3\), 初期状態 \(A = [5, 3, 2]\) のとき：

1. 作業台 \(1\) のスイッチを押す → \(A = [0, 8, 2]\)（5個が作業台2に移動）
2. 作業台 \(2\) のスイッチを押す → \(A = [0, 0, 10]\)（8個が作業台3に移動）
3. 作業台 \(3\) のスイッチを押す → \(A = [0, 0, 0]\)（10個が排出される）

このように、操作の順番が結果に大きく影響するため、操作をまとめて処理するような工夫は難しく、愚直に1つずつシミュレーションするのが最も自然なアプローチです。

幸い、\(N, Q \leq 2 \times 10^5\) であり、各操作が \(O(1)\) なので、全体で \(O(N + Q)\) となり十分高速です。

アルゴリズム

1. 配列 \(A\) に各作業台の初期部品数を格納する（1-indexed で管理すると分かりやすい）。
2. \(Q\) 回の操作を順に処理する。操作対象が作業台 \(b\) のとき：
   • \(b = N\) なら：\(A[b] \leftarrow 0\)（部品を排出）
   • \(b < N\) なら：\(A[b+1] \leftarrow A[b+1] + A[b]\) としてから \(A[b] \leftarrow 0\)（部品を右隣に移動）
3. すべての操作が終わった後、\(A[1], A[2], \ldots, A[N]\) を出力する。

計算量

• 時間計算量: \(O(N + Q)\)
  • 初期値の読み込みに \(O(N)\)、各操作の処理に \(O(1)\) × \(Q\) 回で \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 部品数を保持する配列のみ

実装のポイント

• 1-indexed の配列を使うと、問題文の作業台番号とそのまま対応するため、添字のずれによるバグを防ぎやすいです。

• 部品数が最大 \(2 \times 10^{14}\) に達する可能性がありますが、Python は整数のオーバーフローがないため、特別な対処は不要です（C++ などでは long long を使う必要があります）。

• sys.stdin.buffer.read() で入力を一括読み込みすることで、Python でも高速に入力を処理できます。\(Q\) が最大 \(2 \times 10^5\) のとき、1行ずつ input() を呼ぶよりも大幅に高速です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    A = [0] * (N + 1)  # 1-indexed
    for i in range(1, N + 1):
        A[i] = int(input_data[idx]); idx += 1
    
    for j in range(Q):
        b = int(input_data[idx]); idx += 1
        if b == N:
            # Eject parts from station N
            A[b] = 0
        else:
            # Move parts from station b to station b+1
            A[b + 1] += A[b]
            A[b] = 0
    
    print(' '.join(str(A[i]) for i in range(1, N + 1)))

main()

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