区間の数え上げ / 2 : 尺取り法
区間の数え上げに関する技術のひとつであり、時々現れては競プロerを撲殺するひどいやつ。
使える条件
尺取り法は結構な場合において、実は使えない。
というのも、左端を固定した時に右端としてあり得る箇所が$ 1箇所であるか、右端に単調性がないといけない。右端としてあり得る箇所が複数箇所あるならば区間の数え上げ / 1 : 累積〇〇シフトだったり、他の方法を使うことになる。 単調性というワードを使ったが、これは
左端を$ lと定める。このとき、$ rが存在して、
$ lから始まり$ l+1, l+2, \ldots, rのそれぞれで終わる区間は全て題意を満たす
$ lから始まり$ r+1, r+2, \ldots, Nのそれぞれで終わる区間は全て題意を満たさない
という意味。
例えば、数列の要素が正の整数だけで、総和が$ M以下などの条件があるとすると、総和は必ず単調増加になる。
左端をひとつ定めて右端を末尾の方向に広げることを考えるが、この時一度区間の総和が$ Mを超えるとそれ以上右端を末尾の方向に広げても$ Mを超えたままになる。
これをいいことに$ l, rを全探索する$ Ο(N^2)と比べて非常に高速な、時間計算量$ Ο(N)で区間の数え上げが出来てしまう。この技術を尺取り法と呼ぶ。
一般的な実装
leftおよびrightという「今見ている区間」の両端の座標を持っている変数を用意して、以下の様に処理する。
$ [\mathrm{left}, \mathrm{right})が条件を見たしている間、rightに$ 1加算する。
$ [\mathrm{left}, \mathrm{right})が条件を満たさなくなったら、再び$ [\mathrm{left}, \mathrm{right})が条件を満たすようになるまで、leftに$ 1加算する。
要は、出来るだけ右に区間を広げて、ダメになったら左を右方向に狭めるという処理をする。これが尺取り虫のような挙動なので、尺取り法と呼ばれている。虫のことが嫌いな人、ごめんなさい。僕も苦手です。
割と非直感的かもしれないが、leftもrightも$ 1回ずつ$ 1, 2, \ldots, Nと変化していくので、時間計算量は$ Ο(N)である。
ABC032 / C - 列 を解く
rightを大きくするたびに、ある例外を除いて必ず区間の積が大きくなることが重要である。
つまり、そのある例外を除いては区間の総和が一度$ Mを超えると、それ以上区間を広げた時にどう頑張っても二度と$ Mを下回ることは無い。
ちなみに、ある例外とは数列内に$ 0が含まれている場合であり、この場合は答えが$ Nになる(全要素の積が$ 0になるので)。
ということで、以下は$ Sに$ 0が含まれない場合だけを考える。
uncompleted……