しゃくとり法

いや検索候補の上位に出てきてて泣いてしまった、中身何もない…

とりあえず読むといいです

「〇〇を満たす区間の中で最小or最大の長さを求めよ」

「〇〇を満たす区間の数を求めよ」

みたいな問題で使える。「連続する部分列」〜、とかいうのでもしゃくとり法が使えたりします。区間と仲が良い…？

連続する何かで、連続するそれの内側のやつが全て条件を満たしたり、連続するそれを含んでるやつが全て条件を満たしたり、みたいな時に

つまり、「左端を決めたら右側に何かしらの単調性が出てくる時」にしゃくとり法は便利

たぶん左端を全探索、右端を二分探索すれば良い…？知らんけど

実装

おきもち

左手は一定の速さで右に移動する

右手は不規則に進んだり止まったりする

ゲームで言うと

キャサリン

NewスーパーマリオブラザーズWii 8-1

星のカービィスーバーデラックス メタナイトの逆襲 STAGE6のボス戦前

その他、後ろから一定速度で追いかけてくる系で主人公が進んだり止まったりする任意のゲーム

実装としては、大体

code:hoge.cpp

int right = 0;

for(int left = 0; left < n; left++){

while(right < n && 条件){

rightを右に動かす処理

}

何かしらの処理

if(left == right){ // leftがrightに追いついたら

どうにかする

}

}

こんな感じです。初めにrightが条件を満たす限り右に進めるだけ進んで、rightが止まってwhileループから抜け出したら、一定速度のleftがだんだん追いついてきます。

right++;

right++;

right++;

right++;

何かしらの処理

left++;

何かしらの処理

left++;

何かしらの処理

left++;

何かしらの処理

left++;

どうにかする

right++;

right++;

.........

こんな感じの挙動になります。このleftがrightに追いついた時の「どうにかする」は、rightを右に押しだす…とかそういうやつです。