概要

\(N\) 個の植木鉢に番号の小さい方から順に水を注いでいき、各植木鉢の空き容量を満たしていくシミュレーション問題です。

考察

この問題は、操作の手順が明確に定められているため、その手順をそのまま忠実に再現（シミュレーション）すれば正解が得られます。

重要な気づき： - 各植木鉢 \(i\) の空き容量は \(C_i - S_i\) で計算できます。 - 残りの水が空き容量以上あれば、その植木鉢を満タンにして、残りの水を減らします。 - 残りの水が空き容量未満であれば、残りの水を全部注ぎ、以降の植木鉢には何も追加しません。

具体例：

\(N = 3, M = 5\) で、植木鉢が以下のような場合を考えます。

植木鉢	容量 \(C_i\)	現在 \(S_i\)	空き \(C_i - S_i\)
1	6	3	3
2	4	2	2
3	5	1	4

• 植木鉢1: 空き \(3\)、残り水 \(5 \geq 3\) → 満タン（\(6\) リットル）、残り水 \(5 - 3 = 2\)
• 植木鉢2: 空き \(2\)、残り水 \(2 \geq 2\) → 満タン（\(4\) リットル）、残り水 \(2 - 2 = 0\)
• 植木鉢3: 空き \(4\)、残り水 \(0 < 4\) → \(1 + 0 = 1\) リットルのまま

答えは \(6, 4, 1\) です。

素朴なアプローチとの比較：

この問題では1リットルずつ注ぐようなシミュレーションをすると、\(M\) が最大 \(10^{18}\) なのでTLEになります。しかし、各植木鉢ごとに「空き容量分をまとめて注ぐ」ことで、ループは \(N\) 回で済みます。

アルゴリズム

1. 残りの水量 remaining を \(M\) で初期化する。
2. 植木鉢 \(i = 1, 2, \ldots, N\) について順に以下を行う：
   • 空き容量 \(\text{space} = C_i - S_i\) を計算する。
   • \(\text{remaining} \geq \text{space}\) なら、植木鉢 \(i\) の水量を \(C_i\)（満タン）にし、\(\text{remaining}\) から \(\text{space}\) を引く。
   • \(\text{remaining} < \text{space}\) なら、植木鉢 \(i\) の水量を \(S_i + \text{remaining}\) にし、\(\text{remaining} = 0\) とする。
3. 各植木鉢の最終的な水量を出力する。

計算量

• 時間計算量: \(O(N)\) — 各植木鉢を1回ずつ見るだけ
• 空間計算量: \(O(N)\) — 入力と結果の格納

実装のポイント

• \(M\) が最大 \(10^{18}\) と非常に大きいため、C++ などでは long long を使う必要があります。Python では整数のオーバーフローを気にする必要はありません。

• 入力が最大 \(2 \times 10^5\) 行あるため、sys.stdin.buffer.read() でまとめて読み込むことで入力の高速化を図っています。

• 出力も '\n'.join(...) でまとめて1回で行うことで、高速に出力しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    C = []
    S = []
    for i in range(N):
        c = int(input_data[idx]); idx += 1
        s = int(input_data[idx]); idx += 1
        C.append(c)
        S.append(s)
    
    result = []
    remaining = M
    for i in range(N):
        space = C[i] - S[i]
        if remaining >= space:
            result.append(C[i])
            remaining -= space
        else:
            result.append(S[i] + remaining)
            remaining = 0
    
    sys.stdout.write('\n'.join(map(str, result)) + '\n')

if __name__ == '__main__':
    main()

---

この解説は claude4.6opus-thinking によって生成されました。