Yet Another Blog

しゃくとり法は主に競技プログラミングにおいてある条件を満たすような連続部分列 $[l,r)\ (0 \leq l < r \leq n)$ の個数を数えたり, 最大の長さを求めたり, 最小の長さを求めたりするのを $O(n)$ で行うアルゴリズムです. しゃくとり法の適用できる範囲と実装方法について考えてみました.

いま自然数$n$と連続部分列$[l,r)$に関するある条件 $P(l,r)$ が与えられているとします.
インデックスは0-indexedで半開区間を考えているとします. しゃくとり法が適用可能な条件は次の二つのいずれかの場合です.

条件1: $P(l_1,r_1)$ が真のとき, $l_1 \leq l_2 < r_2 \leq r_1$ ならば $P(l_2,r_2)$も真である.
条件2: $P(l_1,r_1)$ が真のとき, $0 \leq l+2 \leq l_2, r_1 \leq r_2 \leq n$ならば$P(l_2,r_2)$も真である.

すなわち条件1はある部分列が条件を満たすとき, その中の任意の部分列が条件を満たすということを意味しており,条件2はある部分列が条件を満たすとき, それを含む任意の部分列が条件を満たすということを意味しています.

条件1と条件2は条件 $P(l,r)$ の真偽を入れ替えることで互いに移り変わるため, これを区別することに意味はないように見えますが,

• 条件1の場合では$P(l,r)$を満たす部分列の最大の長さをしゃくとり法で求めることが可能で　
• 条件2の場合では$P(l,r)$を満たす部分列の最小の長さをしゃくとり法で求めることが可能であるため,

この区別には意味があります.

しかし, 条件1と条件2の両方の場合でしゃくとり法の実装も考え方もほとんど同じなので以下では条件1について説明してみます.

以下のようなアルゴリズムで条件1を満たす連続部分列の数え上げ or 最大の長さをもとめることができます.
これをしゃくとり法といいます.

int n;

int count = 0; // 数
int max_length = 0; // 最大の長さ
int r = 0;
for (int l = 0; l < n; l++) {
    while (r < n && P(l,r+1)) {
        r++;
    }
    count += r - l;
    max_length = max(max_length, r - l);
    if (r == l)
        r++;
}

正当性を考えてみます. while ループでは$l$を固定して条件を満たす限り r++ としています. while ループが終了したとき,

• r = n (すなわち $P(l,n)$は真)
• r < n かつ $P(l,r)$は真かつ$P(l,r+1)$は偽である

のいずれかということがわかります. r = n なら (lを固定した時の)数え上げ, 最大の長さともに正しいことがわかります. r < n のときも$P(l,r+1)$は偽であることから条件1より$r<x\leq n$ならば$P(l,x)$は常に偽であることがわかるのでこの場合も(lを固定した時の)数え上げ, 最大の長さともに正しいです.

さらにl+1としたとき,

• r = n
• r < n かつ $P(l,r)$は真かつ$P(l,r+1)$は偽である
• $P(l,l+1)$は偽かつr = l+1

という状態です. r = n ならば$l < l + 1$より$P(l+1,r)$は真であるのでよいです.
r < n かつ$P(l,r)$は真かつ$P(l,r+1)$は偽ならば$P(l+1,r-1)$は必ず真であるので
このrから始めても良いです. また$P(l,l+1)$は偽かつr = l+1の場合も当然問題ないです.
よって以上より正当性がわかりました.

またアルゴリズムで r は0からnまでインクリメントしかされないためwhileは合計で$O(n)$回しか回らないため, 計算量は$O(n)$です.

これで一件落着な気がしますが, うえの計算量の仮定は $P(l,r)$が$O(1)$で計算できるという仮定に基づいていました. これは多くの場合成立しません.

そのため連続部分列$[l,r)$に関する情報を何らかの形で保持しておきl,rをインクリメントしたときにいい感じに情報を捨てたり, 取り込んだりできるようにしたいです.　これは実は連続部分列$[l,r)$に関する情報が群で表されるときに可能です(多分?).

すなわち今まで$P(l,r)$と書いていたものが次のように書けるとします.

• Aを長さnのある群$G$の要素からなる配列とする. すると$f(l,r) = A[l] \cdot A[l+1] \cdot \dots \cdot A[r-1]$なる関数を考えることができる. 群$G$の要素$g \in G$に対する条件$P(g)$があり, $P(l,r)=P(f(l,r))$

するとつぎのようなアルゴリズムでしゃくとり法を実装できます. ただし群の単位元を$1$, 演算を$op(a,b)$, 逆元を$1/a$のように書きます.

int n;
vector<Grp> A(n); // なんか入力

Grp g = 1; // 単位元
int count = 0; // 数
int max_length = 0; // 最大の長さ
int r = 0;
for (int l = 0; l < n; g = op(1/A[l],g),l++) {
    while (r < n && P(op(g,A[r]))) {
        g = op(g,A[r]);
        r++;
    }
    count += r - l;
    max_length = max(max_length, r - l);
    if (r == l) {
        g = op(g,A[r]);
        r++;
    }
}

これが多くの場合にしゃくとり法が適用可能な場合だと思います(多分). たとえば以下の問題は次のような群と条件$P$を考えるとできます.
※ネタバレ注意

• AOJ The Number of Windows
  $G = (\mathbb{Z},+,0),P(g) = (g \leq x)$
• Atcoder ABC032 C 列
  $S[i] = 0$であるものがある場合答えが明らかに$n$になるのですべて$S[i] > 0$としてよく.
  $G = (\mathbb{R}_{> 0},\times,1),P(g) = (x \leq K)$

いちおうライブラリもつくりましたが, しゃくとり法は貼るだけで解くことは厳しいと思っているので(これとか), 貼るというよりどのような場合に適用可能なのかとどうやって実装するかを理解しておくのが良いのではないかと思いました.

しゃくとり法に苦手意識があったため, 適用できる条件と実装の仕方について考えてみました.