尺取り法について

概要

いくつか実装の選択肢があるので迷ってしまうが，次のように決めておくと良いかもしれない．

ポインタは常に左から右に動かす．戻らない．
性質が成り立つ境界が2つあるわけだが，どちらの境界でも，静止状態では，ポインタは右側を指すようにする．
ポインタが境界の左側を指していたときのなんらかの値が欲しいときには，それをどこかに記録しておく．

Rationale

戻すというのは常には可能ではないかもしれないし，戻すとなると右端を減らすという新たな処理が必要．．決して戻さないと決めておいた方が楽．
ポインタを進めてみないと性質が成り立つかどうかわからないということがある．
左側の時の値が欲しい場合は，おそらく，少ない．

注意

つまり，「…がなりたつ最大のr」を求めようとしているときには，「…が成り立たない最小のr」を求めることになるので，現在の r の値から 1 を引くことになる．

典型実装

$l$ の動く範囲が $[0, N)$ で，$r$ の動く範囲が $[0, N]$ だとする．(こういうことが多いであろう)

「cond() が成り立つ最小のr」 ( cond() がなりたつまで r を増やす )

    ll r = 0;
    for (ll l = 0; l < N; ) {
        auto cond = [&]() -> bool { /* 条件 */ };
        auto incr_r = [&]() -> void { r++; /* そのほか r を増やすときに行うこと */ };
        auto incr_l = [&]() -> void { l++; /* そのほか l を増やすときに行うこと */ };
        while (r <= N and not cond()) incr_r();
        if (r > N) break;
        do_something(l, r);
        incr_l();
    }

「cond() が成り立つ最大のr」 ( cond() が成り立っている間 r を増やしつづける )

    ll r = 0;
    for (ll l = 0; l < N; ) {
        auto cond = [&]() -> bool { /* 条件 */ };
        auto incr_r = [&]() -> void { r++; /* そのほか r を増やすときに行うこと */ };
        auto incr_l = [&]() -> void { l++; /* そのほか l を増やすときに行うこと */ };
        while (r <= N and cond()) incr_r();
        // ここには break は無い．
        do_something(l, r - 1);    // 条件を満たす最大の値は r ではなく r - 1
        incr_l();
    }

範囲右端に関する注意

「cond() が成り立つ最小の r 」の場合は， while ループを抜けたときは，r == N + 1 か cond(l, r) かであって，前者の場合には cond (l, N) がなりたたなかったことを意味する．もっと大きな l についても同じことになるので， r > N で while ループを抜けた場合には，外側の for ループを break してよい．

「cond() が成り立つ最大のr」の場合，not cond(l, r) で抜けた場合も，r - 1 が「…が成り立つ最大の値」だし，r > N で抜けた場合も r - 1，すなわち N + 1 - 1 = N が「cond() が成り立つ最大の値」になる．

その他

cond のチェックが l と r だけでできるとは限らない．たとえば，$[l, r)$ における $A$ の最大値と最小値の差がなになに，みたいな話で，最大値や最小値を参照する必要があるとすると，incr_r や incl_l の中で変更することになる．
上にも書いたが，do_something のところ，l と r - 1 だけでは処理できず，「rの値が1つ前だったときのこれこれの値」のようなものが必要になることがあるかもしれない．その場合には，incr_r の中で，prev_korekore のような変数にその値を格納しておくようにするとよいであろう．

keywords: two pointers two-pointer technique

概要#

注意#

典型実装#

範囲右端に関する注意#

その他#

概要

注意

典型実装

範囲右端に関する注意

その他