単調境界探索
可否または値の単調性を証明し、最初・最後の成立点を探す。
この典型を扱う単元: 単調境界を証明して探索する
検索別名: binary search on the answer、二分探索、答えの二分探索
未知問からこの典型を見つける手掛かり
- 扱う対象
- 上限
- 下限
- 境界
- 答え
- 使う手掛かり
- 二分探索
- 単調
- 可否判定
- 保つ不変量
- 以上なら
- 以下なら
- 成立する最
- 求めるもの
- 境界
- 最大化
- 最小化
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- DSUによる連結成分管理・縮約: 閾値以下の辺だけを有効化する単調判定器をDSUで共有するときに併用する。
- 尺取り法・sliding window: どちらも単調性を使うが、値域の真偽境界を探す方法と連続区間の端を一方向へ進める方法を区別する。
- XOR閾値matchingのbit分割再帰: 固定XOR閾値での最大matching数をbit再帰で判定し、その成立数が閾値に対して単調な場合に外側の二分探索と組み合わせる。
学習成果と学習単位
判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。
単調境界を証明して探索するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC215 F「Dist Max 2」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC216 E「Amusement Park」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC229 G「Longest Y」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC246 G「Game on Tree 3」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する / 主タグ
技能・出典
主題: 単調境界を証明して探索する
主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC267 E「Erasing Vertices 2」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC269 E「Last Rook」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC270 E「Apple Baskets on Circle」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC292 F「Regular Triangle Inside a Rectangle」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC293 Ex「Optimal Path Decomposition」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC300 F「More Holidays」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC303 F「Damage over Time」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC304 G「Max of Medians」 公式問題主題: XOR閾値matchingのbit分割再帰 / 補助タグ
- ABC320 G「Slot Strategy 2 (Hard)」 公式問題主題: 二部matching・Hall・Kőnig / 補助タグ
技能・出典
主タグ: 二部matching・Hall・Kőnig / 補助タグ: 座標・値の順序保存圧縮、貪欲法と交換論、剰余周期・指数法則、単調境界探索
- ABC324 F「Beautiful Path」 公式問題主題: fractional programming・比率parametric search / 補助タグ
- ABC330 F「Minimize Bounding Square」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC346 F「SSttrriinngg in StringString」 公式問題主題: 圧縮・反復・再帰文字列へ問い合わせる / 補助タグ
- ABC370 F「Cake Division」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 補助タグ
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する
主タグ: 尺取り法・sliding window / 補助タグ: doubling・binary lifting、単調境界探索
- ABC373 E「How to Win the Election」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC374 E「Sensor Optimization Dilemma 2」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC381 E「11/22 Subsequence」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC388 E「Simultaneous Kagamimochi」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC388 G「Simultaneous Kagamimochi 2」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC389 E「Square Price」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC394 G「Dense Buildings」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC395 F「Smooth Occlusion」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC397 G「Maximize Distance」 公式問題主題: 最大流・最小カット / 補助タグ
- ABC401 G「Push Simultaneously」 公式問題主題: 二部matching・Hall・Kőnig / 補助タグ
- ABC424 E「Cut in Half」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC427 G「Takahashi's Expectation 2」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC444 F「Half and Median」 公式問題主題: 単調境界を証明して探索する / 主タグ
- ABC458 G「Children Yearn for the Evil Kindergarten」 公式問題主題: slope trick / 補助タグ