概要

\(N\) 個の倉庫があり、それぞれに初期在庫があります。\(M\) 個の配送指示に従って商品が移動するとき、最終的に最も在庫が多い倉庫の番号を求めます。

考察

この問題では、単純に配送指示ごとに在庫を更新していくと、最悪の場合 \(M\) 回の操作で各倉庫の在庫を変更することになり、計算量が多くなりすぎてしまいます。また、同じ倉庫間に複数回の移動があることもあります。

しかし、重要なのは 「各倉庫の最終的な在庫数」 だけなので、実際に在庫の移動をシミュレーションする必要はありません。代わりに、各倉庫に対して 「何個の商品が入ってきて、何個出ていったか」 を記録しておけば十分です。

この差分を管理するために、各倉庫ごとに 出入りの差（diff） を保持します。例えば、倉庫 \(u\) から倉庫 \(v\) に \(w\) 個移動する場合、
- 倉庫 \(u\) の在庫は \(w\) 減る → diff[u] -= w
- 倉庫 \(v\) の在庫は \(w\) 増える → diff[v] += w

これをすべての配送指示について処理したあと、初期在庫に差分を加えて最終在庫を計算し、最大値を持つ倉庫の番号を出力すればよいです。

アルゴリズム

1. 各倉庫の初期在庫をリスト \(P\) として読み込む。
2. 各配送指示 \(U_j, V_j, W_j\) に対して：
   • 倉庫 \(U_j - 1\)（0-indexed）の差分に \(-W_j\) を加える
   • 倉庫 \(V_j - 1\) の差分に \(+W_j\) を加える
3. 各倉庫の最終在庫を \(P_i + \text{diff}[i]\) で計算する。
4. 最終在庫の最大値を持つ倉庫の中で、最も番号が小さいものを選んで出力する。

計算量

• 時間計算量: \(O(N + M)\)
  （初期在庫の読み込み \(O(N)\)、配送指示の処理 \(O(M)\)、最終在庫計算と最大値探索 \(O(N)\)）
• 空間計算量: \(O(N)\)
  （初期在庫と差分配列のサイズ）

実装のポイント

• 倉庫番号は1-indexedで入力されるので、内部で扱う際は0-indexedに直す（-1する）必要があります。

• 差分の適用は一括で行い、最後に一度だけ最終在庫を計算することで効率よく処理できます。

• 最大値が複数ある場合は、最も小さい番号を選ぶことに注意してください。

  ソースコード

import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    P = [int(data[i + 2]) for i in range(N)]
    
    # 差分を記録するための配列（または辞書）
    diff = [0] * N
    
    index = 2 + N
    for _ in range(M):
        u = int(data[index]) - 1
        v = int(data[index + 1]) - 1
        w = int(data[index + 2])
        diff[u] -= w
        diff[v] += w
        index += 3
    
    # 各倉庫の最終的な商品数を計算
    final_counts = [P[i] + diff[i] for i in range(N)]
    
    # 最大値を持つ最初のインデックスを見つける
    max_count = final_counts[0]
    max_index = 0
    for i in range(1, N):
        if final_counts[i] > max_count:
            max_count = final_counts[i]
            max_index = i
    
    print(max_index + 1)

if __name__ == "__main__":
    main()

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