概要

各倉庫の初期在庫と倉庫間の配送指示が与えられ、すべての配送指示を一括で反映した後の在庫数が最大の倉庫番号を求める問題です。

考察

この問題の重要な点は、配送指示が「逐次的ではなく一括で反映される」という点です。つまり、各配送指示を順番に処理する必要はなく、各倉庫の最終的な在庫数は以下のように計算できます：

• 各倉庫の最終在庫 = 初期在庫 + (その倉庫に入ってくる商品の総量) - (その倉庫から出ていく商品の総量)

配送指示は単純に「倉庫Uから倉庫VへW個移動」という形式なので、各倉庫について： - 出ていく商品の総量：その倉庫が移動元となるすべての配送指示のWの合計 - 入ってくる商品の総量：その倉庫が移動先となるすべての配送指示のWの合計

この観察から、各配送指示に対して移動元の倉庫からWを引き、移動先の倉庫にWを足す操作をすべて行えば、最終的な在庫数が計算できることがわかります。

アルゴリズム

1. 各倉庫の初期在庫を配列Pに格納する
2. 各配送指示について：
   • 移動元倉庫UからWを減算する
   • 移動先倉庫VにWを加算する
3. 最終的な在庫数が最大となる倉庫番号を探す（同値の場合は最小の番号を選択）

計算量

• 時間計算量: \(O(N + M)\)
  • 初期在庫の読み込みに\(O(N)\)
  • 配送指示の処理に\(O(M)\)
  • 最大値探索に\(O(N)\)
• 空間計算量: \(O(N)\)
  • 在庫数を格納する配列のサイズが\(N\)

実装のポイント

• 配送指示の処理では、倉庫番号が1-indexedで与えられるため、0-indexedに変換する必要があります

• すべての配送指示を処理した後、各倉庫の在庫数が0以上になることが保証されているため、負の値に対する考慮は不要です

• 最大値探索時には、同値の場合に最小の番号を選択するため、大きい値が見つかったときのみ更新する単純なループで十分です

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); idx += 2
    P = list(map(int, data[idx:idx+N]))
    idx += N
    
    for _ in range(M):
        u = int(data[idx]); v = int(data[idx+1]); w = int(data[idx+2]); idx += 3
        u -= 1
        v -= 1
        P[u] -= w
        P[v] += w
        
    max_val = -1
    ans = -1
    for i in range(N):
        if P[i] > max_val:
            max_val = P[i]
            ans = i + 1
            
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。