概要

\(N\) 個の植木鉢に、用意した \(M\) リットルの水を先頭から順番に注いでいくシミュレーション問題です。各植木鉢の容量を超えないように水を補充したとき、最終的にそれぞれの植木鉢に何リットルの水が入っているかを求めます。

考察

この問題のポイントは、「今持っている水」と「植木鉢の空き容量」のどちらが少ないかを順番に判断していくことです。

1. 空き容量の計算: \(i\) 番目の植木鉢の最大容量が \(C_i\)、現在の水の量が \(S_i\) なので、あと \(C_i - S_i\) リットルの水を入れることができます。
2. 注ぐ水の決定:
   • もし残りの水 \(M\) が空き容量より多ければ、空き容量をすべて満たします。
   • もし残りの水 \(M\) が空き容量より少なければ、持っている水 \(M\) をすべてその植木鉢に注ぎます。
   • これは、数学的には \(\min(M, C_i - S_i)\) という式で表せます。
3. 残量の更新: 水を注いだ分だけ、手持ちの水 \(M\) は減っていきます。水が \(0\) になったら、それ以降の植木鉢には水を追加することはできません。

制約を見ると \(N\) が \(2 \times 10^5\) と大きいため、各植木鉢に対して \(1\) 回ずつ計算を行う \(O(N)\) のアルゴリズムで解く必要があります。また、\(M\) が最大 \(10^{18}\) に達するため、大きな数（64ビット整数）を扱える必要があります（Pythonでは標準で扱えます）。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 入力から \(N\) と \(M\) を受け取る。
2. \(i = 1, 2, \dots, N\) の順に以下の操作を繰り返す：
   • \(i\) 番目の植木鉢の空き容量 empty_space \(= C_i - S_i\) を計算する。
   • 実際に注ぐ水の量 water_to_add \(= \min(M, \text{empty\_space})\) を計算する。
   • 最終的な水の量 \(S_i + \text{water\_to\_add}\) を記録する。
   • 手持ちの水の量を更新する： \(M = M - \text{water\_to\_add}\)。
3. すべての植木鉢の最終的な水の量を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 植木鉢の数 \(N\) に対して \(1\) 回のループで処理が終わるため、非常に高速です。
• 空間計算量: \(O(N)\)
  • 結果を保持するための配列や、入力データを格納するためのメモリが必要です。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Pythonで input() を繰り返すと実行時間制限（TLE）になる可能性があります。sys.stdin.read().split() で一括で読み込んだり、最後に sys.stdout.write でまとめて出力したりすることで高速化できます。

• 逐次更新: ループの中で \(M\) を更新していくことで、常に「今使える水の量」を正しく管理できます。一度水が \(0\) になれば、min(0, empty_space) は \(0\) になるため、自然に「水を追加しない」という挙動になります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 植木鉢の数, M: 用意した水の量
    N = int(input_data[0])
    M = int(input_data[1])
    
    results = []
    # 植木鉢の情報を順番に処理する
    # 2番目のインデックスから開始し、2つずつ読み取る (C_i, S_i)
    for i in range(N):
        C_i = int(input_data[2 + 2 * i])
        S_i = int(input_data[3 + 2 * i])
        
        # この植木鉢に入れられる水の最大量
        empty_space = C_i - S_i
        
        # 実際に注ぐ水の量 (残り容量と所持している水の量の小さい方)
        water_to_add = min(M, empty_space)
        
        # 操作後の水の量を計算
        final_water = S_i + water_to_add
        results.append(str(final_water))
        
        # 残りの水の量を更新
        M -= water_to_add
        
    # 結果をまとめて出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == "__main__":
    solve()

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