概要

与えられた順番に植木鉢に水を注ぎ、最終的な各植木鉢の水量を求めます。

考察

この問題は、前から順番に植木鉢を見て、必要なだけ水を注いでいくというシンプルなシミュレーションです。

各植木鉢 \(i\) について、すでに \(S_i\) リットル入っていて、最大容量が \(C_i\) なので、追加で注げる水量は \(C_i - S_i\) です。今持っている残りの水の量を remaining として管理しながら、この「注げる水量」と比較して処理をしていけば良いです。

重要なのは、以下の2つの場合分けです： - 残りの水がその植木鉢を満たすのに十分であれば、その植木鉢は満杯（\(C_i\)）になり、残りの水は remaining -= (C_i - S_i) だけ減る。 - 残りの水が足りなければ、S_i + remaining だけ水が入り、それ以上水はないので remaining = 0 とする。

この処理を先頭から順に行えばよいので、特別なデータ構造やアルゴリズムは必要ありません。

素朴なアプローチでも間に合う理由は、各植木鉢に対して定数時間の処理しか行わないためです。ただし、入力を高速に読み込む工夫が必要な場合があります（特に \(N\) が大きいとき）。

アルゴリズム

1. 入力をすべて読み込み、植木鉢の容量 \(C_i\) と現在の水量 \(S_i\) を配列に格納する。
2. 残りの水の量 remaining を \(M\) で初期化する。
3. 各植木鉢について以下を行う：
   • 必要な水量 \(needed = C_i - S_i\) を計算する。
   • remaining >= needed なら、その植木鉢は満杯（\(C_i\)）になり、remaining を減らす。
   • そうでないなら、S_i + remaining だけ水が入り、remaining を0にする。
4. 各植木鉢の最終的な水量を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力が非常に多いので、sys.stdin.read を使って一度に読み込むと効率的。
• 各植木鉢に対して定数時間で処理を行うため、ループ内で無駄な計算をしないようにする。
• 最終結果はリストに保持しておき、最後にまとめて出力する方が高速。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    C = [0] * N
    S = [0] * N
    
    index = 2
    for i in range(N):
        C[i] = int(data[index])
        S[i] = int(data[index+1])
        index += 2
    
    remaining = M
    result = []
    
    for i in range(N):
        needed = C[i] - S[i]
        if remaining >= needed:
            result.append(C[i])
            remaining -= needed
        else:
            result.append(S[i] + remaining)
            remaining = 0
    
    for r in result:
        print(r)

if __name__ == "__main__":
    main()

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