尺取り法

読了目安 約3分

右を伸ばし左を縮める尺取り法で、条件を満たす最長の連続区間を O(N) で見つける。

「条件を満たす連続した区間のうち、最長のもの」を探すとします。 区間の両端の組み合わせは約 N² / 2 通りあるので、順に試すと O(N²) 以上かかります。 区間の両端を交互に前へ進める尺取り法なら、O(N) で答えが出ます。

右を伸ばし、左を縮める

例として、合計が 10 以下になる最長の区間を探します。 要素はすべて 0 以上とします。

手順は 2 つの動きの繰り返しです。 右端を 1 つ伸ばし、その値を合計に足します。 合計が 10 を超えていたら、超えなくなるまで左端を縮めます。

こうすると、右端を動かし終えるたびに「いまの区間は条件を満たす」という不変条件が戻ります。 そのつど長さで答えを更新すれば、各右端について条件を満たす最長の区間を調べたことになります。

let a = [2, 3, 4, 5, 6]
let k = 10

var sum = 0
var left = 0
var best = 0
for right in 0..<a.count {
    sum += a[right]          // 右端を伸ばす
    while sum > k {          // 条件が破れている間は
        sum -= a[left]       // 左端を縮める
        left += 1
    }
    best = max(best, right - left + 1)
    print("右端が a[\(right)] のとき、条件を満たす長さは \(right - left + 1)")
}
print("最長: \(best)")

試してみよう: k を 5 に変えると、答えが 2 になります。確かめてください。

なぜ O(N) で終わるのか

内側に while があるので、一見 O(N²) に見えます。 しかし左端は一度進んだら戻りません。 右端の移動が N 回、左端の移動も全体で最大 N 回なので、合計 O(N) です。

使える条件

尺取り法が頼っているのは、条件の単調性です。 「右に伸ばすと破れる方向、左を縮めると直る方向にしか変わらない」ことが必要です。 要素に負の数が混ざると合計はこの性質を失うので、この問題では使えません。

スライディングウィンドウ

同じ手法はスライディングウィンドウとも呼ばれます。 窓を滑らせるイメージの名前です。 コーディング面接や英語の資料では、こちらの名前が一般的です。

学びどころ

演習

1 行目に整数 N と K、2 行目に 0 以上の整数 A_1 … A_N が空白区切りで入力されます。 合計が K 以下になる最長の連続部分列の長さを出力してください。 どの 1 個を取っても K を超える場合は 0 を出力してください。

制約: 1 ≤ N ≤ 100000、0 ≤ K ≤ 1000000000、0 ≤ A_i ≤ 1000000000。

入力例:
5 10
2 3 4 5 6

出力例:
3

2 + 3 + 4 = 9 が K = 10 以下で、長さ 3 が最長です。

let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let n = firstLine[0]
let k = firstLine[1]
let a = readLine()!.split(separator: " ").map { Int($0)! }

var ans = 0
var sum = 0
var left = 0
for right in 0..<n {
    sum += a[right]
    while sum > k {
        sum -= a[left]
        left += 1
    }
    ans = max(ans, right - left + 1)
}
print(ans)