概要

連続する区間の合計が \(K\) 以下となるような、最長の区間の長さを求める問題です。尺取り法（しゃくとり法）を使って効率的に解くことができます。

考察

素朴なアプローチとその問題点

まず思いつくのは、すべての区間 \([l, r]\) を試す方法です。

for l in 1..N:
    for r in l..N:
        区間[l,r]の合計を計算して K 以下か判定

この方法では区間の選び方が \(O(N^2)\) 通り、各区間の合計計算に \(O(N)\) かかるため、全体で \(O(N^3)\) となります。\(N = 2 \times 10^5\) では到底間に合いません。

累積和を使えば合計計算を \(O(1)\) にできますが、それでも \(O(N^2)\) で TLE になります。

重要な気づき

ここで重要な観察があります：

配列の要素がすべて正であるため、区間を右に伸ばすと合計は必ず増加し、左端を右に動かすと合計は必ず減少する

この単調性を利用すると、左端 \(l\) を固定したとき、条件を満たす最大の \(r\) が一意に定まります。さらに、\(l\) を 1 増やすと、対応する最大の \(r\) も同じか増加します（減少しない）。

例えば、\(A = [3, 1, 2, 4, 1]\)、\(K = 6\) の場合： - \(l=1\) のとき: \([3,1,2]\) まで可能（合計 \(6\)）、\(r=3\) - \(l=2\) のとき: \([1,2,4]\) まで可能（合計 \(7 > 6\) なので）\([1,2]\) で \(r=3\)、または先に進めて \(r=4\) で合計 \(7\) は不可 - 実際には \(l=2\) で \(r=3\) （合計 \(3\)）か \(r=4\)（合計 \(7\)）で、\(r=3\) まで可能

この性質により、\(l\) と \(r\) を同時に右方向にのみ動かす「尺取り法」が使えます。

アルゴリズム

尺取り法（Two Pointers） を使います。

1. 左端 \(l\)、右端 \(r\) を両方 \(0\)（先頭）から始める
2. \(r\) を右に1つ進めて、\(A[r]\) を区間の合計に加える
3. 合計が \(K\) を超えている間、\(l\) を右に進めて \(A[l]\) を引く
4. 現在の区間の長さ \(r - l + 1\) で答えを更新
5. \(r\) が末尾に達するまで 2〜4 を繰り返す

具体例（\(A = [3, 1, 2, 4, 1]\)、\(K = 6\)）：

ステップ	\(l\)	\(r\)	区間	合計	長さ
1	0	0	[3]	3	1
2	0	1	[3,1]	4	2
3	0	2	[3,1,2]	6	3
4	1	3	[1,2,4]	7→左を縮める	-
4’	2	3	[2,4]	6	2
5	3	4	[4,1]	7→5	2

答え: 3

計算量

• 時間計算量: \(O(N)\)
  • \(l\) と \(r\) はそれぞれ最大 \(N\) 回しか増加しないため、while ループを含めても全体で \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保持するための領域

実装のポイント

• \(K\) の上限が \(10^{15}\) と大きいため、合計を格納する変数は 64 ビット整数が必要です（Python では自動的に対応されます）

• while current_sum > K and left <= right の条件で left <= right を入れることで、すべての要素が \(K\) より大きい場合にも対応できます

• 条件を満たす区間が1つもない場合（各 \(A_i > K\)）は、max_count が \(0\) のまま出力されます

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    max_count = 0
    current_sum = 0
    left = 0
    
    for right in range(N):
        current_sum += A[right]
        
        while current_sum > K and left <= right:
            current_sum -= A[left]
            left += 1
        
        if current_sum <= K:
            max_count = max(max_count, right - left + 1)
    
    print(max_count)

solve()

---

この解説は claude4.5opus によって生成されました。