典型タグ

Convex Hull Trick・直線包絡

一次関数の候補を傾き・交点順に管理し、各query点で最小または最大となる直線を選ぶ。

この典型を扱う単元: Convex Hull Trick・直線包絡

検索別名: CHT、Convex Hull Trick、直線包絡

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

扱う対象
  • query点
  • 一次関数
  • 傾き
  • 切片
  • 直線
使う手掛かり
  • dp遷移
  • 最大値query
  • 最小値query
  • 直線を追加
保つ不変量
  • 上側包絡
  • 下側包絡
  • 交点順
  • 傾き順
求めるもの
  • dp高速化
  • 最適値
  • 線形関数の極値
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 幾何・凸最適化への変換

    関連する典型

    • 一次元凸・単峰最適化: どちらも凸性を語彙に持つが、一次元目的関数の単峰性から探索範囲を狭める方法と、複数直線の包絡を動的に管理する方法では発動条件・証明・実装が独立している。
    • DP遷移の集約・高速化: DP遷移を直線の評価へ変形し、包絡線queryとして高速化する構成で併用する。

    学習成果と学習単位

    代表問題

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

    関連問題

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