バグりにくい尺取り法の実装

尺取り法は、競プロでよく使われるテクニックですが、区間の扱い(特に境界の扱い)が難しくバグを引き起こしやすいです。そこで、(個人的に)バグを引き起こしにくい実装を紹介します。

実装

int l = 0, r = 0;
while(r < n){
    (rを1個右に動かす)
    while(l < r && (条件を満たさない)) (lを1個右に動かす);
    ans = max(ans, r-l); // (条件を満たす区間の最大値を求める場合)
}

実装のポイント

  • 区間を半開区間  \lbrack l, r) として持つ
    こうすると、区間の長さは r-lと簡単に計算できます。
  • 右端を固定して、条件を満たすまで左端を動かす
    右端を固定しても左端を固定しても、最終的な答えは変わりません。
    個人的には、右端を固定した方が扱いやすいですが、好みの問題かもしれません。

例題 : Problem - 279B - Codeforces

問題概要

長さ n の数列  a_1, a_2, \cdots , a_nが与えられる。連続部分列で、総和が t以下であるもののうち最長のものの長さを求めよ。

解答

この問題では、 \lbrack r, r)はかならず条件を満たすので、条件式のうち l \lt rの部分が不要になります。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    int l = 0, r = 0;
    int s = 0, ans = 0;
    while(r < n){
        s += v[r++];
        while(s > t) s -= v[l++];
        ans = max(ans, r-l);
    }
    cout << ans << "\n";
    return 0;
}

https://codeforces.com/contest/279/submission/54262670