尺取り法・sliding window
一列の連続窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進める。
この典型を扱う単元: 尺取り法・sliding windowで連続区間を走査する
検索別名: sliding window、two pointers、尺取り法
未知問からこの典型を見つける手掛かり
- 扱う対象
- 両端
- 列
- 区間
- 連続
- 使う手掛かり
- 単調に進
- 右端
- 尺取り
- 左端
- 保つ不変量
- 一度ずつ
- 突き合わせ
- 窓
- 求めるもの
- 区間ごと
- 区間の長さ
- 区間数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- 単調境界探索: どちらも単調性を使うが、値域の真偽境界を探す方法と連続区間の端を一方向へ進める方法を区別する。
学習成果と学習単位
一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。
尺取り法・sliding windowで連続区間を走査するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC215 F「Dist Max 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC250 F「One Fourth」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC258 E「Packing Potatoes」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC260 E「At Least One」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC281 E「Least Elements」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
- ABC290 E「Make it Palindrome」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC294 E「2xN Grid」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC300 G「P-smooth number」 公式問題主題: meet-in-the-middle・半分全列挙 / 補助タグ
- ABC314 G「Amulets」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
技能・出典
主題: ordered set・multisetの動的順序管理
主タグ: ordered set・multisetの動的順序管理 / 補助タグ: 貪欲法と交換論、尺取り法・sliding window
- ABC337 F「Usual Color Ball Problems」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC365 G「AtCoder Office」 公式問題主題: 平方根・閾値による軽重分類 / 補助タグ
- ABC366 E「Manhattan Multifocal Ellipse」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC370 F「Cake Division」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する
主タグ: 尺取り法・sliding window / 補助タグ: doubling・binary lifting、単調境界探索
- ABC380 G「Another Shuffle Window」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元、尺取り法・sliding window
- ABC388 G「Simultaneous Kagamimochi 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC431 F「Almost Sorted 2」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC444 E「Sparse Range」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC452 F「Interval Inversion Count」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 主タグ
- ABC455 G「Balanced Subarrays」 公式問題主題: 乱択代数fingerprint / 補助タグ