しゃくとり法のDequeを使ったバグりにくい実装 - Qiita

この記事の目的 しゃくとり法のバグりにくい実装の紹介です！ しゃくとり法(尺取り法)って？ しゃくとり法の説明自体は、とってもいいまとめがあるのでこちらをご覧ください。 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ でも、しゃくとり法ってバグりません？ しゃくとり法っていざ書いてみるとかなりの確率でバグります。 区間の端を表す添え字 $l$ と $r$ の動かし方が結構混乱します。 この記事ではdeque(両端キュー)を使った実装を紹介します。 なんとこの実装では添え字を使う必要がありません！ deque(両端キュー)によるしゃくとり法の実装 次の問題を例にとって説明します。 ABC 032 C - 列 長さ $n$ の整数列 $A = \{a_1, a_2,..., a_n\}$の連続部分列で、その要素の積が $K$ 以下となるものの長さの最大値を求める問題です。 次の

[sh19910711]

"連続部分列をdequeの両端への追加と削除で管理 / 標準的な実装でありがちな、l が r を追い越してしまった！という事はdequeの要素の数が負になる事に相当するので起こりえません"