もうバグらせない。尺取法×Queueの結論
はじめに
今日１日ずっと尺取法と向き合ってきて、尺取法がいかにバグりやすいものなのかをさんざん知ってきた。Twitterを見ていても、尺取法に悩み枕を濡らす人々がたくさん。ご多分に漏れず、私もそのうちの１人である。
そして尺取法に囚われた人の多くが、for-while二重ループの実装で嘆いている。
この尺取法の問題点は、leftがrightを超えてしまう危険性を常にはらんでいるということ。あと、インデックスの管理というよりは、境界の管理、という感覚があるのが分かりづらい(結構感覚的に喋ってしまっている)。
それ故にインデックスのずれや、いつの間にかwhileが変に回ってしまい、オワオワリって感じのコードが多発する。
そんなことで悩んでらんないのだ…私はもっと早く上に登りたい。尺取法なんぞにバグリスクをはらませてはならない。ということで今回は、尺取法×Queueを紹介したい。
尺取法はどこで利用できるのか？
まずはいつ使えるのかを考えるところから、解法を学ぶことは始まる。尺取法は、主に以下の3点において有効である。
- 「条件」を満たす区間 (連続する部分列) のうち、最小の長さを求めよ
- 「条件」を満たす区間 (連続する部分列) のうち、最大の長さを求めよ
- 「条件」を満たす区間 (連続する部分列) を数え上げよ
数学的には、区間における単調性が担保されているといいとか話があるのだが、詳しくは以下のサイトを見てほしい。
要は、どちらかの区間を固定したときに、条件を満たすところと満たさないところが綺麗に分かれていることが絶対条件なのだ。
でもそんなこと尺取法で枕濡らしているような人間が気にしても仕方がない。我々はいつ使うかを気にしておけばよろしい。
尺取法の派閥
次にどんな実装方法があるのかをみながら比較していきたい。
for-while二重ループ
まずは王道の方法。いわゆるfor-whileでの二重ループによって実装する方法。この実装方法は、左端を固定して、[l,r)の半開区間で尺取している。
半開区間を実装しているとかなり感じられることがこのコードの強み。
このコードを書いているときの気持ちを記述してみる。
気持ち
まず、1.while文の条件の中で、「次の要素に移動してもいいのかな〜？」って聞いている。もし行けるなら、移動する。移動できるだけ移動する。
移動しきったら、2.区間の長さとか、区間の数とかを数える。基本的にwhileの中では長さとか数とかは保持せず、whileで移動しきった後に計算する。
で、3.最後にバグらないでね〜のおまじない。
コード
#define rep(i, n) for (auto i = 0; i < (n); i++)
/*for-while-loop*/
// 尺取法(半開区間)
ll res = 0;
ll criterion = 0;
ll right = 0;
rep(left, n) {
// 1.次の要素に動かしていいのなら？P(l,r)の部分を変更する
while (right < n && P(l, r)) {
// rightを伸ばす
right++;
}
// 2.区間の現在の長さ
res += (right - left);
// 3.leftをインクリメントする準備
if (right == left) {
right++;
} else {
// 減らす処理
}
}
}
1重while-loop
次が、2重のloopを見たくないという人間に1重while-loop実装。
ポインタの部分が並列構造になっているため分かりづらいんだけど、左端固定をしつつ半開区間で移動している。そして何と言っても、ポインタの移動の際に条件の判定をしている。
たしかにポインタの移動に類似実装が可能なので、見た目としては綺麗だし、実装も一見楽そうに見える。でもwhileにしようという気持ちが入りすぎて、条件を満たしているかのcheckが２回も出てしまう(だから関数化しないと使いづらい)。あと、結局は左端固定で半開区間移動なのに、その思想が見えづらいコードなところが扱いづらかった。
気持ち
まず、1.if文の条件の中で、何もしていない今の状態に対して「条件を満たしてる？？満たしてなかったら左端ずらす？満たしてたら右端ずらす？」って聞いている。もし行けるなら、移動する。
移動した後に、2.条件を満たしてる〜？ってもう一回聞く(ここがめんどい。前文で、現在の状態を元に条件判定しているためこうなってしまっている)。
端点を一つずらしたら、都度区間の長さとか、区間の数とかを数える。ここが他の方法と大きく違う。
で、3.最後にバグらないでね〜のおまじない。
コード
/*1-while-loop*/
// 現在の条件を考える
bool check = [&](){
}
do {
1.if (r < n and check()) {
// 右端を増やす
now *= s[r];
++r;
} else {
// 満たされている？→右端を増やす
now /= s[l];
++l;
}
// 2.満たしているときに計算
if(check()){
}
// 3.バグらないためのインクリメント
} while (l < n) // lがnが端っこに来たら終わり
Queue
最後が本題。Queueでの実装。かなり他のものと毛色が異なっているように見えるのがこのコードなのだが、それもそのはず。こちらは右端固定で、かつ閉区間による実装になっている。
最初は半開区間の方が扱いやすいんじゃないの？とおもってやってなかったんだけど、色々と試行錯誤しているとこれが一番バグりにくい。
そして、閉区間であるがゆえに他の実装と気持ちの面でもかなり違う。
気持ち
下のコードで言うと、Queueを定義しているところから話が始まる。まずfor文内で、1.Queueに要素を一ついれる(右端を伸ばす)。その後、2.条件を判定する。条件が満たされていなければ、満たされるまでpopし続ける(左端を縮める)。その変化が終了した後に、3.区間数や数を計算する。queueのため、左端が右端を越すことはまずない。
コード
using ll = long long;
using vl = vector<ll>;
#define rep(i, n) for (auto i = 0; i < (n); i++)
vl s(n);
rep(i, n) {
cin >> s[i];
if (s[i] == 0) {
cout << n << endl;
return 0;
}
}
queue<ll> Q;
ll maxlen = 0;
ll cri = 1;
rep(i, n) {
//1
Q.push(s[i]);
cri *= s[i];
//2
while (!Q.empty() && cri > k) {
cri /= Q.front();
Q.pop();
}
//3
maxlen = max(maxlen, ll(Q.size()));
}
cout << maxlen << endl;
感想
他のコードと比べて、Queueの思想は他と比べてかなり異なっている。そもそも実装上の制約から、閉区間にもなるし、右端固定にもなっている。みんなの意見聞いてないからわかんないけど、この思想の違いがせっかくのQueue×尺取法に、謎の使いにくさをもたらしているんじゃないかな。閉区間であることを受け入れて、右端固定なのでそれに見合った区間の計算方法をマスターすれば、尺取法なんかで悩むこともなくなるんじゃないかな？と思っている。まだまだペーペーの競プロerですが。
具体的に取り組む
前提テンプレート
自分の今のincludeとかテンプレートの構成はこれ。競プロerならだいたいこんな感じなんじゃないの？もっとあるんじゃないかな。
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
// usingの設定
// stdは一番上に設定しておく
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using graph = vector<vector<ll>>;
// rep文の作成
#define rep(i, n) for (auto i = 0; i < (n); i++)
条件にあう区間長の最大値を求める問題
int main() {
ll n, k;
cin >> n >> k;
vl s(n);
rep(i, n) {
cin >> s[i];
if (s[i] == 0) {
cout << n << endl;
return 0;
}
}
queue<ll> Q;
ll maxlen = 0;
ll cri = 1;
rep(i, n) {
Q.push(s[i]);
cri *= s[i];
while (!Q.empty() && cri > k) {
cri /= Q.front();
Q.pop();
}
maxlen = max(maxlen, ll(Q.size()));
}
cout << maxlen << endl;
return 0;
}
単調増加を判定する問題
区間の数を数える問題で、ちょっと特徴的なのは条件を判定するときには常に数列が2つ以上入っているようにしていること。ちょうど前に最後尾に入っていたものと比べる場合には、この方法が有効。
int main() {
ll n;
cin >> n;
vl a(n);
rep(i, n) cin >> a[i];
// 尺取法
ll res = 0;
queue<ll> Q;
for (int i = 0; i < n; i++) {
Q.push(a[i]);
while (Q.size() > 1 && a[i] <= a[i - 1]) {
Q.pop();
}
res += Q.size();
}
cout << res << endl;
return 0;
}
重複しないような区間長の最大値問題
つい最近のABC381でもでたような、区間内の数が重複しないような区間長の最大値問題。
setと組み合わせで使っているけど、なおこの書きやすさ。おかしい。
ポイントは、変化しきった後にkind,insertをしているということ。重複しない問題にはよくある書き方かな。
int main() {
// 入力
ll n;
cin >> n;
vl a(n);
rep(i, n) cin >> a[i];
set<ll> kind;
// 尺取法
queue<ll> Q;
ll maxlen = 0;
rep(i, n) {
Q.push(a[i]);
// 条件が満たされていないところまで
while (!Q.empty() && kind.find(a[i]) != kind.end()) {
kind.erase(Q.front());
Q.pop();
}
kind.insert(a[i]);
maxlen = max(maxlen, ll(Q.size()));
}
cout << maxlen << endl;
return 0;
}
インデックスをqueueにいれるだけの問題
考察のレベルがかなり高い問題だが、できれば一瞬。
int main() {
ll n, m;
cin >> n >> m;
map<ll, ll> seg;
ll l, r;
rep(i, n) {
cin >> l >> r;
if (seg.find(r) == seg.end() || seg[r] < l) {
seg[r] = l;
}
}
// 尺取法
queue<ll> Q;
ll res = 0;
for (int i = 1; i <= m; i++) {
Q.push(i);
while (!Q.empty() && (seg.find(i) != seg.end()) && seg[i] >= Q.front()) {
Q.pop();
}
res += Q.size();
}
cout << res << endl;
return 0;
}
参考記事
Discussion