典型タグ

単調境界探索

可否または値の単調性を証明し、最初・最後の成立点を探す。

この典型を扱う単元: 単調境界を証明して探索する

検索別名: binary search on the answer、二分探索、答えの二分探索

未知問からこの典型を見つける手掛かり

扱う対象
  • 上限
  • 下限
  • 境界
  • 答え
使う手掛かり
  • 二分探索
  • 単調
  • 可否判定
保つ不変量
  • 以上なら
  • 以下なら
  • 成立する最
求めるもの
  • 境界
  • 最大化
  • 最小化
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: モデル変換

    関連する典型

    • DSUによる連結成分管理・縮約: 閾値以下の辺だけを有効化する単調判定器をDSUで共有するときに併用する。
    • 尺取り法・sliding window: どちらも単調性を使うが、値域の真偽境界を探す方法と連続区間の端を一方向へ進める方法を区別する。
    • XOR閾値matchingのbit分割再帰: 固定XOR閾値での最大matching数をbit再帰で判定し、その成立数が閾値に対して単調な場合に外側の二分探索と組み合わせる。

    学習成果と学習単位

    代表問題

    この典型の考え方を具体的な問題で確かめるための入口です。

    関連問題

    この典型が主タグまたは補助タグとして付いている問題です。