概要

バケツは前から順に満杯になるまで水を受け取り、満杯になったら次のバケツへ流れるので、合計 \(W\) リットルで「先頭から何個のバケツを満杯にできるか」を求める問題です。

考察

重要な観察は「水は必ずバケツ \(1 \rightarrow 2 \rightarrow 3 \rightarrow \cdots\) の順にしか溜まらない」ことです。
バケツ \(i\) が満杯になるまでは水はすべてバケツ \(i\) に入り、満杯になった瞬間から余りが \(i+1\) に流れるため、途中のバケツを飛ばして後ろだけ満杯になることは起こりません。

したがって、最終的に満杯になるバケツの個数は

• \(C_1\) を満たせるか？
• できるなら次に \(C_2\) も満たせるか？
• ……

というように、先頭から容量の和（累積和）が \(W\) 以下である限り数えるだけで決まります。

素朴に「毎秒 1 リットル流れるから \(W\) 秒シミュレーションする」ようにすると、\(W \le 10^{18}\) なので到底間に合いません（TLE）。
しかしこの問題では時間の概念は本質的ではなく、必要なのは「合計量 \(W\) でいくつのバケツの容量を払い切れるか」だけです。

例：\(C=[3,5,2],\ W=8\) のとき
累積和は \(3,\ 8,\ 10\) なので、\(8\) 以下は 2 個分まで → 満杯は 2 個。

アルゴリズム

1. 変数 total=0（これまでに満杯にするため使った水量）と ans=0（満杯になった個数）を用意する。
2. バケツを先頭から順に見て、容量を c とする。
3. もし total + c <= W なら、そのバケツを満杯にできるので
   • total += c
   • ans += 1
4. そうでなければ、そのバケツは満杯にならず、以降も満杯になり得ない（先頭から順にしか満杯にならないため）のでループを打ち切る。
5. ans を出力する。

要するに「容量の前からの累積和が \(W\) を超える直前までの個数」を求めています。

計算量

• 時間計算量: \(O(N)\)（先頭から1回走査するだけ）
• 空間計算量: \(O(1)\)（入力配列以外は定数）

実装のポイント

• \(W \le 10^{18}\) なので、累積和 total は 64bit 整数が必要です（Python は整数が自動で大きくなるので安心）。

• total + c > W になった時点で break すると無駄な処理が減ります。

• 入力が最大 \(2 \times 10^5\) なので、sys.stdin.buffer.read() のような高速入力が有効です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, W = data[0], data[1]
    C = data[2:2+N]

    total = 0
    ans = 0
    for c in C:
        if total + c <= W:
            total += c
            ans += 1
        else:
            break
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。