AtCoder Beginner Contest 032 [ C - 列 ]をPythonで解く。しゃくとり法をやってみる（💧水色diff）

問題

atcoder.jp

解法

しゃくとり法という単語をAtCoderの解法でよく聞くが、やったことなかったので、やってみる。
ある条件を満たす数列の範囲を、しゃくとり虫のように長さを変えながら探索するアルゴリズムで

• 条件〇〇を満たす区間 (連続する部分列) のうち、最小or最大の長さを求めよ
• 条件〇〇を満たす区間 (連続する部分列) を数え上げよ

このような問題に使える。
左端と右端を条件に合わせて移動させて探索するアルゴリズムとのこと。

計算量はO(N²)のところがO(N)になる。

実装

左端lを固定して、右端rを条件を満たすところまで伸ばしていく。
右端が条件外に達したら、lを+1。
また右端を伸ばせるところまで伸ばす。

ほとんど、参考先のコードと一緒だが。

参考

nashidos.hatenablog.com