概要

連続する本の区間で、所定の時間内に整理できる最大の冊数を求める問題。

考察

この問題では、連続する区間 \([l, r]\) のうち、その区間に含まれる本の整理時間の合計が \(K\) 以下であり、かつ区間の長さ \(r - l + 1\) が最大となるものを求めます。

単純な方法として、全ての区間 \([l, r]\) を全探索して、それぞれの合計時間を計算するという方法があります。しかし、その計算量は \(O(N^2)\) となり、\(N\) が最大で \(2 \times 10^5\) なので現実的ではありません（TLEします）。

重要な観察として、「ある長さ \(L\) の区間で時間内に整理できるなら、それより短い長さの区間でも整理可能」であるという単調性があります。つまり、整理可能な最大の区間の長さを二分探索で求めることができるのです。

さらに、固定長の区間和を高速に求めるために、尺取り法（スライディングウィンドウ）または累積和を利用できます。今回の実装では、区間和を差分更新することで、各長さに対して線形時間で判定を行っています。

アルゴリズム

1. 区間の長さ \(L\) を二分探索で探索する。
2. 各 \(L\) に対して、長さ \(L\) の連続部分列のうち、総和が \(K\) 以下になるものがあるかを判定する。
3. 判定には、最初の区間和を計算し、その後1つずつスライドさせて加減算しながらチェックする（スライディングウィンドウ）。
4. 最大の整理可能長さを更新しながら二分探索を進める。

例えば、入力が N=5, K=10, A=[1, 2, 3, 4, 5] のとき： - 長さ3の区間 [1,2,3], [2,3,4], [3,4,5] のどれかが総和10以下か調べる。 - [2,3,4] の和は9でOK → 長さ3は可能。 - 長さ4を試す → [1,2,3,4] の和は10でOK。 - 最終的に最大の長さは4と分かる。

計算量

• 時間計算量: \(O(N \log N)\)
  各二分探索ステップで \(O(N)\) の判定処理を行う。ステップ数が \(O(\log N)\)。
• 空間計算量: \(O(N)\)
  入力配列 \(A\) を保持するだけ。

実装のポイント

• 二分探索の範囲を left = 0, right = N とし、mid = 0 のときもちゃんと処理できるように is_possible(0) は True にする。
• 区間和の更新は current_sum += A[i] - A[i - length] のように差分で行うことで効率化。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 二分探索で最大の長さを求める
    def is_possible(length):
        if length == 0:
            return True
        current_sum = sum(A[:length])
        if current_sum <= K:
            return True
        for i in range(length, N):
            current_sum += A[i] - A[i - length]
            if current_sum <= K:
                return True
        return False

    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    print(answer)

if __name__ == "__main__":
    main()

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