バグりにくい尺取り法の実装
尺取り法は、競プロでよく使われるテクニックですが、区間の扱い(特に境界の扱い)が難しくバグを引き起こしやすいです。そこで、(個人的に)バグを引き起こしにくい実装を紹介します。
実装
int l = 0, r = 0; while(r < n){ (rを1個右に動かす) while(l < r && (条件を満たさない)) (lを1個右に動かす); ans = max(ans, r-l); // (条件を満たす区間の最大値を求める場合) }
実装のポイント
- 区間を半開区間 として持つ
こうすると、区間の長さはと簡単に計算できます。 - 右端を固定して、条件を満たすまで左端を動かす
右端を固定しても左端を固定しても、最終的な答えは変わりません。
個人的には、右端を固定した方が扱いやすいですが、好みの問題かもしれません。
例題 : Problem - 279B - Codeforces
問題概要
長さ の数列 が与えられる。連続部分列で、総和が以下であるもののうち最長のものの長さを求めよ。
解答
この問題では、はかならず条件を満たすので、条件式のうちの部分が不要になります。
#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; }