概要

植木鉢に順番に水を注いでいくシミュレーション問題で、各植木鉢の空き容量を満たすように水を補充していきます。

考察

問題の操作をそのままシミュレーションすれば解けます。各植木鉢に対して、現在の空き容量を計算し、残りの水の量と比較しながら注いでいきます。重要な点は、注ぐ順番が植木鉢の番号が小さい方から順であることと、すべての水を使い切るかすべての植木鉢を使い切るまで操作を続けることです。

制約条件から、\(N\) が最大 \(2 \times 10^5\) と大きいですが、各植木鉢に対する操作は単純な計算のみなので、線形時間で処理できます。

アルゴリズム

1. 入力値 \(N\), \(M\) と各植木鉢の容量 \(C_i\)、現在の水量 \(S_i\) を読み込む
2. 残りの水の量 remaining を \(M\) で初期化
3. 各植木鉢 \(i\) (\(0 \leq i < N\)) について順に処理：
   • 空き容量 space = C[i] - S[i] を計算
   • remaining が space 以下なら：
     • 現在の植木鉢に remaining を追加
     • remaining を 0 に設定
   • そうでなければ：
     • 現在の植木鉢を満杯（\(C[i]\)）にする
     • remaining から space を減算
4. 各植木鉢の最終的な水量を出力

計算量

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

実装のポイント

• 大きな数値（\(M\) が最大 \(10^{18}\)）を扱うため、整数型のオーバーフローに注意（Pythonでは自動で多倍長整数を扱うため問題なし）

• 入力データの読み込みを効率的に行う

• 各植木鉢を順番に処理し、残りの水の量を更新しながら進める

• 水が尽きたらそれ以降の植木鉢には水を注がない

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    M = int(data[1])
    idx = 2
    C = []
    S = []
    for i in range(n):
        c = int(data[idx])
        s = int(data[idx+1])
        idx += 2
        C.append(c)
        S.append(s)
    
    remaining = M
    for i in range(n):
        space = C[i] - S[i]
        if remaining <= space:
            S[i] += remaining
            remaining = 0
        else:
            S[i] = C[i]
            remaining -= space
    
    for s in S:
        print(s)

if __name__ == "__main__":
    main()

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