概要

整理時間の合計が \(K\) 以下になるような連続区間を選び、その中に含まれる本の冊数（区間長）の最大値を求めます。

考察

この問題は「連続部分列の和が \(K\) 以下」という条件付きで最長区間を探す問題です。

素朴に全ての区間 \([l,r]\) を試すと、区間は \(O(N^2)\) 個あり、それぞれの和を計算すると最悪 \(O(N^3)\)、累積和で和を \(O(1)\) にしても \(O(N^2)\) となります。
制約 \(N \le 2 \times 10^5\) では \(O(N^2)\) でも間に合いません。

ここで重要な観察は次です：

• \(A_i \ge 1\) なので、区間を右に広げる（\(r\) を増やす）と区間和は単調に増える
• 逆に、左端を右に縮める（\(l\) を増やす）と区間和は単調に減る

この単調性により、「右端を1つ進めたら、条件を満たすまで左端を進める」という操作を繰り返せば、全体を \(O(N)\) で処理できます。

例：\(A=[3,1,4,1,5],\ K=6\)
右端を伸ばしていき、和が \(6\) を超えたら左端を動かして調整します。こうすると常に「いま見ている区間は条件を満たす最大限の（できるだけ長い）区間」になり、最大長を更新できます。

アルゴリズム

しゃくとり法（Two Pointers / Sliding Window）を使います。

• 左端 \(l\)、右端 \(r\)、現在の区間和 \(s\) を持つ
• \(r\) を左から右へ1つずつ動かしながら \(s += A[r]\)
• もし \(s > K\) になったら、\(s \le K\) になるまで
  • \(s -= A[l]\)
  • \(l += 1\) を繰り返す（区間を左から縮める）
• 条件を満たしているとき、区間長 \(r-l+1\) で答えを更新する

このとき、\(l\) も \(r\) も最大で \(N\) 回しか増えないため、全体は線形時間で動きます。

計算量

• 時間計算量: \(O(N)\)（各要素は高々1回ずつ区間に入って1回出る）
• 空間計算量: \(O(1)\)（入力配列以外は定数個の変数）

実装のポイント

• \(K\) は最大 \(10^{15}\)、和も大きくなるので、Python の int（多倍長整数）で安全に扱えます（C++なら long long が必要）。

• while s > K のループで左端を縮める際、必ず \(l\) を進めて区間和を減らすこと。

• どの本も整理できない場合は更新が起きず ans=0 のままなので、そのまま 0 が出力されます。

  ソースコード

import sys

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

    l = 0
    s = 0
    ans = 0
    for r, x in enumerate(A):
        s += x
        while s > K and l <= r:
            s -= A[l]
            l += 1
        if s <= K:
            ans = max(ans, r - l + 1)

    print(ans)

if __name__ == "__main__":
    main()

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