尺取り法で左端も動かす

区間の右端を伸ばし、条件が崩れたら左端を進める。左端を戻さなくてよい理由が、速さの根拠です。

言語：Python / 計算量：O(N)

前提：二分探索は「境界」を探す

考え方

1. 非負数の区間和は右に伸ばすと減りません。
2. 和が K を超えたら、左端を削ります。
3. 各要素は1回追加、最大1回削除されます。

具体例

[2,1,3]、K=3。右端を伸ばすと長さ2の[2,1]が成立。3を足したら左から削ります。

実装

a = [2, 1, 3]
k = 3
l = total = ans = 0
for r, x in enumerate(a):
    total += x
    while total > k:
        total -= a[l]
        l += 1
    ans = max(ans, r - l + 1)
print(ans)

注意する条件

負数があると、超過してもさらに右へ進むことで和が下がるため、この方法は使えません。

確認問題

[1,2,1,1]、和が3以下の最長区間長は？

実装課題

N K と非負配列 A が2行。和≤K の連続区間の最大長。N ≤ 200000、K,A_i ≥ 0、≤10^9。空区間は長さ0。

入力:
3 3
2 1 3
出力:
2

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = s = ans = 0
for r, x in enumerate(a):
    s += x
    while s > k:
        s -= a[l]
        l += 1
    ans = max(ans, r-l+1)
print(ans)

実戦につなげる補講

一度に全て読まなくて大丈夫です。今日は1節と1問から。

窓の中身を言葉で固定する

ここでは全要素が非負で、区間和がK以下になる区間の個数を数えます。右端を1つ進めたらその値を合計へ足し、Kを超えた間だけ左端の値を引いて進めます。sumは常に現在の窓の和です。

なぜ左端を戻さなくてよいか

非負の値しかないので右へ足すと和は減らず、左を削ると和は増えません。前に不適だった左端が、右端を伸ばして適切に戻ることはありません。この単調性が、捨てた候補を見直さなくてよい理由です。

二重ループの総回数を数える

右端はN回進み、左端も全体で高々N回進みます。各操作がO(1)ならO(N)。whileがforの中にあるだけでO(N²)とはなりません。窓を毎回sumで計算し直すと、この利点を失います。

負数が入ると何が壊れるか

a=[5,−4],K=3だと、最初の5を捨てても、後から−4を足せば和1の区間が作れます。一度不適だった候補が適切に戻るため、同じ方法は使えません。「区間問題だから尺取り」と決めないようにします。

段階式の追加演習

1. 手で追う

a=[2,1,3],K=3。条件を満たす空でない連続区間は何個？

2. 実装：区間の数

非負整数列aとK>=0について、和がK以下の空でない連続区間数を返すcount_windowsを書いて。

def count_windows(a, k):
    left = total = answer = 0
    for right, x in enumerate(a):
        total += x
        while total > k:
            total -= a[left]
            left += 1
        answer += right - left + 1
    return answer

3. 0が続く境界

a=[0,0,0],K=0の答えは？

4. 反例を作る

負数も許して同じコードを使うとどうなる？ a=[5,−4],K=3で確認して。

公式過去問への橋渡し

ABC212 C / 公式解説

2つの列から選ぶ全組合せは最大400億組。ソート後に比較対象を減らす判断を練習する。

見本を閉じて確認

• 何を繰り返しているかを説明できる
• 使える条件と使えない条件を1つずつ言える
• 見本を閉じて実装し、小さい入力で確かめられる

読了の記録・下書き・メモへ