Convex Hull Trick・直線包絡
一次関数の候補を傾き・交点順に管理し、各query点で最小または最大となる直線を選ぶ。
この典型を扱う単元: Convex Hull Trick・直線包絡
検索別名: CHT、Convex Hull Trick、直線包絡
未知問からこの典型を見つける手掛かり
- 扱う対象
- query点
- 一次関数
- 傾き
- 切片
- 直線
- 使う手掛かり
- dp遷移
- 最大値query
- 最小値query
- 直線を追加
- 保つ不変量
- 上側包絡
- 下側包絡
- 交点順
- 傾き順
- 求めるもの
- dp高速化
- 最適値
- 線形関数の極値
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 幾何・凸最適化への変換
関連する典型
- 一次元凸・単峰最適化: どちらも凸性を語彙に持つが、一次元目的関数の単峰性から探索範囲を狭める方法と、複数直線の包絡を動的に管理する方法では発動条件・証明・実装が独立している。
- DP遷移の集約・高速化: DP遷移を直線の評価へ変形し、包絡線queryとして高速化する構成で併用する。
学習成果と学習単位
一次関数候補の傾き・交点順を保ち、query点で包絡線上の最適な直線を選べる。
Convex Hull Trick・直線包絡で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。