尺取り法｜Python｜女子大生エンジニアの備忘録 #4
こんにちは、鈴です。
今回は尺取り法についての備忘録になります。
前回の備忘録はこちらから↓
前置きは省略して、早速本題に移りましょう。
尺取り法とは
尺取り法とは、区間の左端と右端を動かしながら条件を満たす区間を高速に見つけるというアルゴリズムです。
この区間の端と端の動きを尺取り虫に例えてこのような名前で呼ばれているようです。
Pythonでの実装例
例題として、以下の場合を考えます。
- 入力１：整数のリストS
- 入力２：整数K
- 出力：S内で和がK以下となる最大の要素数
- sum(l,r)：S[l]からS[r]までの和を返す関数
尺取り法をざっくり解説すると、
- 左端を０に固定して条件を満たすできるだけ遠くに右端を固定
- 左端を１つ右に動かしてさらにできるだけ遠くに右端を固定
- 以上の操作を繰り返し、一番長かった区間の長さを出力
という流れです。
区間が伸び縮みして尺取り虫のように進んでいるのがなんとなくイメージできますかね。
余談
皆さんはAtCoderという競技プログラミングのコンテストをご存知ですか？（このページを見て頂いている時点で失礼な質問かもしれませんが・・・）
私はなるべく毎週AtCoderのABC(AtCoder Begginer Contest)に参加するようにしているのですが、先週のABCでこの尺取り法が登場して解けませんでした。
まだまだ自分は勉強不足だということを痛感しております。
就職を控えた大学4年生にして今だに茶色コーダーなので、卒業までに頑張って緑に到達したいものですね・・・。
問題にチャレンジしてみたいという方は、ABC229のD問題をチェックして見てください。
次の記事はこちらから↓
では。
鈴
