while1重尺取り法のすゝめ

半分ネタとして書いた記事です。強い思想などお許しください

はじめに

突然ですが、以下のようなプログラムを見た時、計算量は正しく判断できますか？

int r = 0;
for(int l = 0; l < n; ++l) {
    while(r < n and 条件) {
        // 処理
	++r;
    }
    // 処理
}

このプログラムは「尺取り法」と呼ばれるアルゴリズムの実装方法でメジャーな実装方法です(whileとforが入れ替わるものもありますが)。
おそらく大半の人が初見で$O(N^2)$と判断するでしょう。ですが、実際にはこのプログラムは$O(N)$で動作します。
どうしてこのような勘違いが起こるのか、これは2重ループだからです。
というわけで、僕は1重ループの尺取り法を勧めたいと思います

while1重ってどんなの？

では、while1重尺取り法はどのようなものか紹介します。こんなのです

int l = 0, r = 0;
while(l < n){
    if(r == n or 条件を満たさない){
	// 処理a
        ++l;
    }
    else{
	// 処理a'
        ++r;
    }
    // 処理b
}

これだと、尺取り法が$O(N)$と聞いても腑に落ちるでしょう。

while1重の利点

では、この実装方法による利点を紹介しましょう

1. 計算量の見積もりがしやすくなる

これは実装を見れば自明にわかると思います。これはおまけ程度に。大事なのは次です

2. 楽に実装ができる

これが一番重要なところです。while1重のコードで、処理aと処理a'と書いているように、この二つはかなり類似した処理になるところ、そしてそれらを処理bと視覚的に分離できることです。これのおかげでバグが発生しにくくなります。他にも実装面で色々分かりやすくなります

3. 拡張がしやすい

これは綺麗な端点移動と他の処理の分離が容易かつ直感的にできるからこその利点です。
時によってはコードが汚くなってしまいますが、まぁしょうがないでしょう。

2重ループ型との比較

では、実際に2重ループ型と実装について比較してみましょう。例としてABC032 C - 列を二つの実装方法で解いてみます。

問題概要

数列$S_0, S_1, ... , S_N$の区間であって、その総積が$K$以下となるものの長さの最大値を求めよ

1. 二重ループ(for-while)型による実装

# include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}

int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll>s(n);
    for(auto& i : s) cin >> i;

    if(k == 0) { // コーナーケース
        if (count(s.begin(), s.end(), 0) == 0) cout << 0 << endl;
        else cout << n << endl;
        return 0;
    }

    // for-while型尺取り法
    ll now = 1, r = 0, ans = 0;
    for(ll l = 0; l < n; ++l) {
        while(r < n and now*s[r] <= k) {
            now *= s[r];
            ++r;
        }
        chmax(ans, r-l);
        if(now == 0) {
            cout << n << endl;
            return 0;
        }

        if(l == r) ++r;
	else now/=s[l];
    }
    cout << ans << endl;
}

こんな感じになります。さて、このコード、キモくないですか？++lと++r流石に離れすぎじゃない？lが毎forループ加算されるの無慈悲すぎない？rと協力しようよ
まぁ、１つ目の問題はfor-whileからwhile-whileに変えれば++lは出てきますが、それでも二番目の問題は解決されません。
こんな無慈悲で協調性のないアルゴリズムがあってたまるか！

2. while1重型

というわけで我らがwhile1重型尺取り法のお出ましです。先ほど紹介した型に当てはめて書いてみます。

# include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}

int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll>s(n);
    for(auto& i : s) cin >> i;

    if(k == 0) { // コーナーケース
        if (count(s.begin(), s.end(), 0) == 0) cout << 0 << endl;
        else cout << n << endl;
        return 0;
    }

    // while1重型尺取り法
    ll l = 0, r = 0, now = 1, ans = 0;
    while (l < n-1) {
        if(r == n or now > k) {
            now /= s[l];
            ++l;
        }
        else {
            now *= s[r];
            ++r;
        }

        if(now <= k) chmax(ans, r-l);
        if(now == 0) {
            cout << n << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

こんな感じです。なんと綺麗なコードでしょう。どのループでもlとrどちらかしか動きません。変数の協調性のある素晴らしいコードです。
さらに、++lと++rの部分はよく似ていますし、端点を動かす処理と答えを出す処理が綺麗に分離できています。美しすぎる。

おわりに

というわけでここまでwhile1重型尺取り法を紹介してきました。
この記事を見ての通り、僕は圧倒的に一重ループ推しです。というわけでこの記事を読んだ人も尺取りはwhile1重ループで書こう！

ありがとうございました

追記

ループ内のif文について (2022-05-11)

++lと++rの部分のif文はしばしば以下のように書いたりすることもあります

if (r < n and 条件を満たす) {
    // 処理a
    ++r;
}
else {
    // 処理a'
    ++l;
}

どちらもやっていることはほぼ同じです