概要

\(N\) 個の倉庫にある初期在庫に対し、\(M\) 件の「倉庫 \(U\) から倉庫 \(V\) へ \(W\) 個移動させる」という指示を一括で反映させた後、在庫が最も多い倉庫の番号（複数ある場合は最小の番号）を求める問題です。

考察

この問題のポイントは、「一括で反映する」という操作をどのように効率よく処理するかにあります。

各配送指示 \((U_j, V_j, W_j)\) は、最終的な在庫量に対して以下のような影響を与えます。 - 倉庫 \(U_j\) の在庫が \(W_j\) 減る - 倉庫 \(V_j\) の在庫が \(W_j\) 増える

「一括で反映」とありますが、これは「すべての指示による増減を合算してから初期値に適用する」ことと同じです。したがって、各指示を順番に読み込み、該当する倉庫の現在の在庫量を更新していくシミュレーションを行うことで、最終的な在庫量を正しく計算できます。

\(N\) と \(M\) が最大で \(2 \times 10^5\) と大きいため、各指示に対して複雑な処理を行わず、配列の値を直接更新する \(O(1)\) の操作で済ませる必要があります。

アルゴリズム

1. 初期化: 長さ \(N\) の配列 \(P\) を用意し、各倉庫の初期在庫数を格納します。
2. 指示の処理: \(M\) 件の指示を 1 つずつ読み込みます。
   • 倉庫 \(U_j\) の在庫を \(W_j\) 減らす： P[U_j - 1] -= W_j
   • 倉庫 \(V_j\) の在庫を \(W_j\) 増やす： P[V_j - 1] += W_j
   • ※配列のインデックスは 0 から始まるため、倉庫番号から 1 を引いて調整します。
3. 最大値の探索: 配列 \(P\) を先頭（倉庫 1）から順番に確認し、現在の最大在庫数とその倉庫番号を記録していきます。
   • 「最大値が複数ある場合は番号が最小のものを出力する」という条件があるため、「現在の最大値よりも厳密に大きい」値が見つかったときのみ、倉庫番号を更新するようにします。
4. 出力: 記録された倉庫番号を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、指示の処理に \(O(M)\)、最大値の探索に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 各倉庫の在庫を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python では input() よりも sys.stdin.read().split() などを用いて一括で入力を取得する方が実行時間を短縮できます。

• 数値の範囲: 在庫数 \(P_i\) や移動量 \(W_j\) は最大 \(10^9\) であり、最終的な在庫数も大きな値になります。Python は標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

• インデックスの調整: 問題文は 1-indexed（1番から始まる）ですが、プログラムの配列は 0-indexed（0番から始まる）であることが多いため、U-1 や V-1 のように補正を忘れないようにします。

  ソースコード

import sys

def solve():
    # 入力を一度に読み込み、空白で分割してトークンのリストを作成します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 倉庫の数 N と配送指示の数 M を取得します
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 各倉庫の初期の商品数 P をリストに格納します
    # P[i] は倉庫 i+1 の商品数を表します
    P = [0] * N
    for i in range(N):
        P[i] = int(next(it))
        
    # M 件の配送指示を順番に処理します
    for _ in range(M):
        u = int(next(it))
        v = int(next(it))
        w = int(next(it))
        
        # 倉庫 U_j から W_j 個減らし、倉庫 V_j に W_j 個加えます
        # 倉庫番号は 1-indexed なので、インデックスを調整します
        P[u-1] -= w
        P[v-1] += w
        
    # すべての指示を実行した後の各倉庫の商品数から、最大値を特定します
    # 最大値が複数ある場合は、最も小さい倉庫番号を保持します
    max_stock = -1
    ans_warehouse = -1
    for i in range(N):
        if P[i] > max_stock:
            max_stock = P[i]
            ans_warehouse = i + 1
            
    # 結果を出力します
    sys.stdout.write(str(ans_warehouse) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。