概要

\(N\) 個のバケツがあり、先頭から順に水が流れ込みます。各バケツが満杯になると水が次のバケツに流れていきます。合計 \(W\) リットルの水が流れ込んだとき、最終的に満杯になるバケツの数を求めます。

考察

この問題では、水がバケツ \(1\) から順に流れていき、あるバケツが満杯になると次のバケツに水が流れていきます。そのため、前から順に各バケツに水がどれだけ入るかシミュレーションすれば良さそうですが、制約を見ると \(W\) が最大 \(10^{18}\) と非常に大きいため、1リットルずつ追加するようなシミュレーションは現実的ではありません（TLEになります）。

そこで、「最終的に何個のバケツが満杯になるか？」という問いに対して、「ある \(k\) 番目までのバケツがすべて満杯になるのに必要な水量」を考えることにします。これは、バケツの容量の累積和で求められます。つまり、最初の \(k\) 個のバケツすべてが満杯になるには、\(C_1 + C_2 + \cdots + C_k\) リットルの水が必要です。

これをすべての \(k\) について愚直に計算するのも非効率なので、累積和＋二分探索のテクニックを使います。具体的には、累積和配列 \(S\) を用意し、\(S[k] = C_1 + \cdots + C_k\) となるようにしておきます。そして、\(S[k] < W\) となる最大の \(k\) を二分探索で求めます。

さらに、最後のバケツが満杯にならなくても、部分的に満たされている場合もあるので、その分を考慮して最終的な答えを調整します。

アルゴリズム

1. 各バケツの容量 \(C_i\) から、累積和配列 \(S\) を構築します。
   \(S[i] = C_1 + C_2 + \cdots + C_i\)

2. 二分探索により、「すべて満杯になるのに必要な水量が \(W\) 未満であるような最大のバケツ数」を求めます。

   • 条件：\(S[\text{mid}] < W\)

3. 得られたバケツ数に加えて、次にあるかないかの「部分的に満たされたバケツ」が存在するか確認します。

   • もし \(S[\text{answer}] + C[\text{answer}] \leq W\) なら、そのバケツも満杯になるため、答えに +1 します。

計算量

• 時間計算量: \(O(N)\)（累積和の計算）+ \(O(\log N)\)（二分探索） → 全体で \(O(N + \log N) = O(N)\)
• 空間計算量: \(O(N)\)（累積和配列）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。
• 累積和を前もって計算しておくことで、各区間の合計を定数時間で取得できます。
• 二分探索の終了条件や更新方法に注意し、境界ケース（例えばすべてのバケツが満杯になる場合）も考慮しましょう。

## ソースコード

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

def main():
    data = input().split()
    N = int(data[0])
    W = int(data[1])
    C = list(map(int, data[2:]))

    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + C[i]

    # 二分探索で満杯になるバケツの数を求める
    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if S[mid] < W:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    # 最後に部分的に満たされるバケツがあるか判定
    if answer < N and S[answer] + C[answer] <= W:
        answer += 1

    print(answer)

if __name__ == "__main__":
    main()

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