しゃくとり法 - komiyamの日記

私はしゃくとり法を書くのが苦手です。なので、しゃくとり法について自分なりに考えてみました。

しゃくとり法って結局何？

二分探索は「ある点を基準に真偽が入れ替わるとき、その基準となる点を見つけるアルゴリズム」と説明できるし、座標圧縮は「何かの境界となり得ない座標を潰す技法」等と説明できます。
じゃあ、しゃくとり法は何かという答も持っているべきです。今の私なら「ある条件を満たす極小な区間を全て列挙するアルゴリズム」と答えます。
もう少し詳しく言葉にしてみます。
ある関数fは区間X=[l,r](開とか閉とか半開とかは適当)を受け取って真偽値を返します。例えば数列のある区間和がS以上になるかどうか、みたいな。この関数はある種の単調性というべき性質を持っている必要があります。つまりf([l,r])が真ならf([l-1,r])もf([l,r+1])も真だということです。また、f(空)=偽も要求します。極小な区間というのは、f([l,r])が真かつf([l+1,r])もf([l,r-1])も偽となる、「もうこれ以上削れない区間」のことです。しゃくとり法はこの極小な区間を全て列挙します。

しゃくとり法の原理と実装

上で私の言いたいことはほとんど言い終わってしまいました。何をするための道具か、というのは道具の原理より大事なことです。
私の意識するしゃくとり法の基本はたったのふたつです。

条件を満たさなければ右端を進めて区間を広げる。
条件を満たしていれば左端を進めて区間を狭める。

二分探索は解が[low, high)の区間にある、といった不変条件を大事にします。同様に、しゃくとり法でも不変条件を意識して実装するように注意します。
以下、私の好みで区間は半開区間[l,r)で考えるようにします。
蟻本で紹介されているしゃくとり法の実装を抽象化すると次のようになります。以下のコメント部分で列挙される区間はかならずしも極小とは限りません。しかし重要な事実として、極小な区間の列挙漏れは起こり得ません。さすがに洗練された実装だと思います。

for (int l = 0, r = 0;; l++) {
    for (;r < n && !f( [l,r) ); r++) ;
    if( !f( [l,r) ) ) break;
    //[l,r)は条件を満たす。
}

ところでf(空)=偽がどこで効いているかというと、lがrを追い越さないことの保証になっています。
実用上はfの計算を差分計算などで効率よく求めることが要求されることが多く、そのせいで見た目が多少複雑になってしまうこともあります(結局そこでよく引っかかってしまうのですが)が基本はいつでも単純です。

追記：蟻本の実装は別の解釈の仕方もあって、「各lに対してf([l,r))が真になる最小のrを計算している」と見ることもできる。