尺取り法(コピペ用)
(library/sequence/two_pointer_approach_memo.hpp)

• View this file on GitHub
• Last update: 2026-02-09 15:31:01+09:00
• Include: #include "library/sequence/two_pointer_approach_memo.hpp"

尺取り法

できること

• 条件を満たす連続な区間について、区間の最大数とかを求める

イメージ

配列  0 1 2 3 4 5 6 7 8 9 ....
t=0  l        r         rが条件を満たす限り、行けるだけ行く
t=1     l     r         rはそのままに、lを左にずらす
t=2     l          r    また、rを行けるだけ行く
t=3     <---------->    この区間長とかをchmaxとかしながら走査
...

※lとrが左から右に移動してるだけなので実質1周 = O(N)
※lをずらすたびにrを元に戻さないこと。
  既にみてるから省略できるぞ、というのが肝。
  rを元に戻すとただの2重ループと同じなので意味ないぞ。

計算量

$O(N)$

使い方

コピペして使う

Code

#pragma once
// 尺取り法 !!コピペ用!! 関数内をペーストして書き換えて使う
void two_pointer_approach(int N, auto test) {
    int ans = 0;
    //      左手     右手     上限
    for (int l = 0, r = 0; l < N; ++l) {
        // 伸ばせるだけ右手を伸ばす
        //               rがtest条件を満たす間伸ばす
        while (r < N and test) ++r;
        // 伸ばしきったら、区間数でansを緩和
        ans = max(ans, r - l);
    }
}

#line 2 "library/sequence/two_pointer_approach_memo.hpp"
// 尺取り法 !!コピペ用!! 関数内をペーストして書き換えて使う
void two_pointer_approach(int N, auto test) {
    int ans = 0;
    //      左手     右手     上限
    for (int l = 0, r = 0; l < N; ++l) {
        // 伸ばせるだけ右手を伸ばす
        //               rがtest条件を満たす間伸ばす
        while (r < N and test) ++r;
        // 伸ばしきったら、区間数でansを緩和
        ans = max(ans, r - l);
    }
}

Back to top page