尺取り法の最強ライブラリを作った。

僕は水色コーダーでありながら尺取り法がとても苦手である。
ミスりやすい。
そこでこの度、尺取り法の最強ライブラリを作った。

尺取り法の難しさ

実装上の注意として２つの点が挙げられる。

どの尺にも入れない要素がいる
LeftがRightを追い越す時の処理。

１．どの尺にも入れない要素がいる

例えば和が100以下の尺を数え上げる問題で、200の要素が混じっていたりすると、その前後の処理が複雑になる

２．LeftがRightを追い越す時の処理

LeftとRightを追い越す時に、Rightを追従させなければいけない。この時の処理を忘れがちである。

時には１と２が同時に起きることもある。非常に辛い

解決

尺が存在する区間を列挙

まず、単体で条件を満たす要素を列挙する。
そして、尺が存在する区間を列挙する。
たとえばこの数列から和が8以下の尺を列挙するとする

{ 1, 2, 8, 10, 3, 4, 6}

単体で存在可能な要素は{1, 2, 8, 3, 4, 6}なので、
尺が存在する区間は{1, 2, 8}と{3, 4, 6}である。
この２つの区間をそれぞれ処理すればいい。
この時点で、１のどの尺にも入れない要素がある問題はクリアできた。

尺が存在する区間の始まりをハンドリングする

次に、２の問題はライブラリが区間の開始イベントを送ってくれると解決する。
区間が始まるタイミングは３つだ

配列の最初の要素
自分の左がどの尺にも入れない要素
左が右を追い越した時

プログラマは、区間の開始を知らされた時に尺を初期化すればいい。

実装

プログラマは以下の６個のイベントハンドラを処理すればいい。

この要素は単体で条件を満たしているか？
左を固定して尺を初期化しろ
右に１個伸ばせるか？
右に１個伸びろ
左を１個捨てろ
区間が確定した

ライブラリ

void tow_pointer(int n,
                 function<bool(int left)> check_begin,
                 function<void(int left)> begin,
                 function<bool(int right)> check_right,
                 function<void(int right)> push_right,
                 function<void(int left)> pop_left,
                 function<void(int left, int right)> dead_end
) {

    auto go = [&](P range) {
        int right = -1;
        for (int left = range.first; left <= range.second; left++) {
            if (right < left) {
                right = left;
                begin(left);
            }
            while (right + 1 <= range.second && check_right(right + 1)) {
                right++;
                push_right(right);
            }
            dead_end(left, right);
            pop_left(left);
        }
    };


    auto get_ranges = [&] {
        vector<bool> enable_items(n);
        rep(i, n) enable_items[i] = check_begin(i);

        auto start = [&](int i) {
            if (i == 0) {
                return enable_items[i] == true;
            }
            if (!enable_items[i - 1] && enable_items[i]) {
                return true;
            }
            return false;
        };

        auto end = [&](int i) {

            if (i == n - 1) {
                return enable_items[i] == true;
            }

            if (enable_items[i] && !enable_items[i + 1]) {
                return true;
            }

            return false;
        };

        vector<P> ans;
        P p;
        rep(i, n) {
            if (start(i)) {
                p = P(i, -1);
            }
            if (end(i)) {
                p.second = i;
                ans.push_back(p);
            }
        }
        return ans;
    };


    vector<P> ranges = get_ranges();
    for (P range: ranges) go(range);
}

使い方

例えばこんな感じで使える

https://atcoder.jp/contests/abc032/tasks/abc032_c

int main() {
    int n;
    ll k;
    cin >> n >> k;

    vector<ll> numbers(n);
    rep(i, n) cin >> numbers[i];

    if (find(numbers.begin(), numbers.end(), 0ll) != numbers.end()) {
        cout << n << endl;
        ret();
    }
    ll sum = 0;

    // この要素は単体で条件を満たすか？
    auto check_begin = [&](int left) {
        return numbers[left] <= k;
    };

    // leftを左として尺を初期化しろ
    auto begin = [&](int left) {
        sum = numbers[left];
    };

    // 右に1個伸びれるか確認しろ
    // 次の「1個右の要素は」rightだ
    auto check_right = [&](int right) {
        return sum * numbers[right] <= k;
    };

    // 右に1このびろ
    // 次の「1個右の要素は」rightだ
    auto push_right = [&](int right) {
        sum *= numbers[right];
    };

    // 左を1個捨てろ
    // 捨てる左の要素はleftだ
    auto pop_left = [&](int left) {
        assert(sum % numbers[left] == 0);
        sum /= numbers[left];
    };

    ll ans = 0;

    // 尺が伸びれるところまで伸びた
    auto dead_end = [&](int left, int right) {
        ll now = right - left + 1;
        cmax(ans, now);
    };


    tow_pointer(
            n,
            check_begin,
            begin,
            check_right,
            push_right,
            pop_left,
            dead_end
    );
    cout << ans << endl;

}