しゃくとり法(尺取法)の適用範囲, 実装
しゃくとり法は主に競技プログラミングにおいてある条件を満たすような連続部分列 の個数を数えたり, 最大の長さを求めたり, 最小の長さを求めたりするのを で行うアルゴリズムです. しゃくとり法の適用できる範囲と実装方法について考えてみました.
しゃくとり法とは
いま自然数と連続部分列に関するある条件 が与えられているとします. インデックスは0-indexedで半開区間を考えているとします. しゃくとり法が適用可能な条件は次の二つのいずれかの場合です.
条件1: が真のとき, ならばも真である.
条件2: が真のとき, ならばも真である.
すなわち条件1はある部分列が条件を満たすとき, その中の任意の部分列が条件を満たすということを意味しており, 条件2はある部分列が条件を満たすとき, それを含む任意の部分列が条件を満たすということを意味しています.
条件1と条件2は条件の真偽を入れ替えることで互いに移り変わるため, これを区別することに意味はないように見えますが, 条件1の場合ではを満たす部分列の最大の長さをしゃくとり法で求めることが可能で, 条件2の場合ではを満たす部分列の最小の長さをしゃくとり法で求めることが可能であるため, この区別には意味があります.
しかし, 条件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
ループではを固定して条件を満たす限り r++
としています. while
ループが終了したとき,
r = n
(すなわち は真)r < n
かつ は真かつは偽である
のいずれかということがわかります. r = n
なら (l
を固定した時の)数え上げ, 最大の長さともに正しいことがわかります.
r < n
のときもは偽であることから条件1よりならばは常に偽であることがわかるのでこの場合も(l
を固定した時の)数え上げ, 最大の長さともに正しいです.
さらにl+1
としたとき,
r = n
r < n
かつ は真かつは偽である- は偽かつ
r = l+1
という状態です. r = n
ならばよりは真であるのでよいです.
r < n
かつ は真かつは偽ならばは必ず真であるので
このr
から始めても良いです. または偽かつr = l+1
の場合も当然問題ないです.
よって以上より正当性がわかりました.
またアルゴリズムで r
は0からnまでインクリメントしかされないためwhile
は合計で回しか回らないため, 計算量はです.
これでOK?
これで一件落着な気がしますが, うえの計算量の仮定は がで計算できるという仮定に基づいていました. これは多くの場合嘘です.
そのため連続部分列に関する情報を何らかの形で保持しておきl,r
をインクリメントしたときにいい感じに
情報を捨てたり, 取り込んだりできるようにしたいです.
これは実は連続部分列に関する情報が群で表されるときに可能です(多分?).
すなわち今までと書いていたものが次のように書けるとします.
- Aを長さnのある群の要素からなる配列とする. するとなる関数を考えることができる. 群の要素に対する条件があり,
するとつぎのようなアルゴリズムでしゃくとり法を実装できます. ただし群の単位元を, 演算を, 逆元をのように書きます.
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++; } }
これが多くの場合にしゃくとり法が適用可能な場合だと思います(多分). たとえば以下の問題は次のような群と条件を考えるとできます.
※ネタバレ注意
- AOJ The Number of Windows
- Atcoder ABC032 C 列
であるものがある場合答えが明らかにになるのですべてとしてよく.
いちおうライブラリみたいなのもつくりました. なんですが, しゃくとり法は貼るだけで解くみたいなことは厳しいと思っているので(これとか), 貼るというよりどのような場合に適用可能なのかとどうやって実装するかを理解しておくのが良いのではないかと思いました.
おわりに
しゃくとり法に苦手意識があったため, 適用できる条件と実装の仕方について考えてみました.