概要

\(N\) 個の倉庫に対して \(M\) 件の配送指示（商品の移動）を一括で反映した後、最も商品数が多い倉庫の番号を求める問題です。

考察

重要な気づき：配送は「一括反映」である

問題文に「\(M\) 件の配送指示は逐次的にではなく一括で反映されます」と書かれています。これは、各配送指示を処理する順番は結果に影響しないことを意味します。各倉庫の最終的な商品数は以下の式で計算できます：

\[\text{最終商品数}_i = P_i + (\text{倉庫 } i \text{ に入ってくる商品数の合計}) - (\text{倉庫 } i \text{ から出て行く商品数の合計})\]

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

各配送指示を1つずつ読み、移動元の倉庫から \(W\) を引き、移動先の倉庫に \(W\) を足すという素朴な方法で考えます。この操作は1件あたり \(O(1)\) で処理でき、\(M\) 件全体で \(O(M)\) です。最後に \(N\) 個の倉庫から最大値を探すのに \(O(N)\) かかりますが、\(N, M \leq 2 \times 10^5\) なので十分高速です。

この問題では特別なアルゴリズムは不要で、素直にシミュレーションすれば解けます。

具体例

例えば、\(N = 3\)、初期商品数が \(P = [10, 20, 30]\) で、配送指示が「倉庫1 → 倉庫2 に 5個」「倉庫3 → 倉庫1 に 15個」の場合：

• 倉庫1：\(10 - 5 + 15 = 20\)
• 倉庫2：\(20 + 5 = 25\)
• 倉庫3：\(30 - 15 = 15\)

最も多いのは倉庫2の25個なので、答えは 2 です。

アルゴリズム

1. 配列 \(P\) に各倉庫の初期商品数を格納する。
2. \(M\) 件の配送指示を順に読み、各指示「倉庫 \(U_j\) から倉庫 \(V_j\) へ \(W_j\) 個移動」に対して：
   • \(P[U_j] \mathrel{-}= W_j\)（出て行く分を引く）
   • \(P[V_j] \mathrel{+}= W_j\)（入ってくる分を足す）
3. 配列 \(P\) を走査し、最大値を持つ倉庫のうち番号が最も小さいものを出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 初期商品数の読み込みに \(O(N)\)、配送指示の処理に \(O(M)\)、最大値の探索に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 各倉庫の商品数を保持する配列のみ

実装のポイント

• 1-indexed と 0-indexed の変換: 倉庫番号は1始まりですが、Pythonの配列は0始まりなので、U-1 や V-1 としてアクセスする必要があります。

• 整数のオーバーフロー: \(P_i\) や \(W_j\) が最大 \(10^9\) で、加算が繰り返されるため最終的な値が大きくなる可能性があります。Pythonでは整数のオーバーフローは起きないので問題ありませんが、C++等では long long を使う必要があります。

• 高速入力: \(N, M\) が最大 \(2 \times 10^5\) なので、Pythonでは sys.stdin.buffer.read() を使って一括で入力を読み込むことで高速化しています。

• 最大値が同じ倉庫が複数ある場合: 先頭から走査して最初に見つかった最大値の位置を採用すれば、自然に「番号が最も小さいもの」を選べます。

  ソースコード

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
    P = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    for _ in range(M):
        U = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        W = int(input_data[idx]); idx += 1
        P[U - 1] -= W
        P[V - 1] += W
    
    max_val = P[0]
    max_idx = 0
    for i in range(1, N):
        if P[i] > max_val:
            max_val = P[i]
            max_idx = i
    print(max_idx + 1)

main()

---

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