Convex Hull Trick

2025年10月20日

Convex Hull Trick

英語表記: Convex Hull Trick (CHT)

概要

Convex Hull Trick（CHT、凸包トリック）は、動的計画法（DP）における特定の遷移計算を劇的に高速化するための高度な最適化手法です。特に、DPの遷移式が、過去の複数の状態から導かれる一次関数の最小値または最大値を求める形になっている場合に適用されます。この手法は、候補となる直線の集合の「凸包（Convex Hull）」の幾何学的な性質を利用することで、通常 $O(N^2)$ や $O(N)$ かかる遷移計算を、全体として $O(N \log N)$ や $O(N)$ にまで削減します。DPの計算量を削減する技術の中でも、特に強力で洗練されたテクニックの一つだと認識しています。

詳細解説

CHTの適用範囲と目的

CHTが適用できるのは、DPの遷移が以下のような形に書ける場合です。

$$
DP[i] = \min_{j < i} { a_j x_i + b_j }
$$

ここで、$a_j$ と $b_j$ は前の状態 $j$ に依存する定数（傾きと切片）であり、$x_i$ は現在の状態 $i$ に依存する変数（クエリ点）です。

通常のDPでは、状態 $i$ を計算するために、過去のすべての状態 $j$ を確認する必要があり、計算量は $O(N^2)$ になってしまいます。しかし、この遷移式をよく見ると、これは「複数の直線 $L_j: y = a_j x + b_j$ のうち、点 $x_i$ において最も小さい値（最小値）を取るものを探す」という幾何学的な問題に置き換えられることがわかります。

幾何学的解釈と凸包の利用

なぜ「凸包」が関係してくるのでしょうか。

私たちが知りたいのは、多数の直線が描かれたグラフ上で、常に一番下（最小値）を通る「下包絡線（Lower Envelope）」の形です。この下包絡線こそが、幾何学的には凸包の境界の一部を形成しているのです。

直線の冗長性: 複数の直線が存在するとき、ある直線が他のどの直線よりも下に位置することがない場合、その直線は決して最適解（最小値）にはなり得ません。このような直線は「冗長」であるとして、計算の候補から除外できます。
凸性の維持: 最小値を取る直線群だけを残した場合、その集合の境界は必ず下に凸な形状（下凸包）を形成します。これは、関数が線形であるという性質から保証される非常に重要な点です。
効率的な探索: 凸包の境界を構成する直線だけを保持していれば、新しい直線を追加する際や、クエリ点 $x_i$ での最小値を探索する際に、直線が持つ傾きの単調性を利用できます。

実装と計算量の削減

CHTの具体的な実装では、通常、両端キュー（Deque）や平衡二分探索木（BST、例えばLi Chao Tree）といったデータ構造が用いられます。

最も古典的な（そして試験で問われやすい）ケースでは、傾き $a_j$ もクエリ点 $x_i$ も両方とも単調増加（または単調減少）であると仮定します。この単調性が揃っている場合、非常に効率的な $O(N)$ のアルゴリズムが実現可能です。

直線の追加: 傾きの単調性を利用し、新しい直線が追加されるたびに、凸包性を崩すような古い冗長な直線を Deque の端から $O(1)$ で削除します。
クエリの処理: クエリ点 $x_i$ も単調に増加するため、最適な直線も Deque の中で単調に移動していきます。一度最適解ではなくなった直線は、今後も最適解になることはないため、これも Deque の端から $O(1)$ で削除できます。

このように、高度な DP 最適化である CHT は、幾何学的洞察（凸包）を駆使して、代数的な最小化問題（線形関数の最小化）を、計算量 $O(N)$ で解くことを可能にする、非常に洗練された技術と言えるでしょう。

具体例・活用シーン

1. 最安値の屋根を見つけるメタファー

CHTを理解するための最も分かりやすいメタファーは、「最安値の屋根」を見つけるストーリーです。

あなたは工場を建設しようとしており、複数の建設業者（$j$）から見積もりを取っています。各業者は、資材費や人件費（切片 $b_j$）と、工場の大きさ（クエリ点 $x_i$）に応じた追加費用（傾き $a_j$）に基づいて、総費用を提示します。

業者＝直線: 各業者の見積もりは $y = a_j x + b_j$ という一本の直線です。
あなたの目標: 工場の大きさ $x_i$ が決まったとき、最も安い費用 $y$ を提示する業者を見つけたい。つまり、すべての直線のうちの最小値（最安値）を探します。

このとき、ある業者Aの見積もり線が、常に他の二つの業者BとCの見積もり線よりも上にあるとします。業者Aはどんな工場の大きさ $x_i$ に対しても最安値になることはありません。この業者Aは「冗長な直線」として、リストから即座に除外できます。

実際に最安値を形成するのは、複数の業者の見積もり線が交差し合いながら、常に一番下を走っている部分です。この「一番下の線」の集合が、まさに下凸包を形成しているのです。

CHTは、この「最安値の屋根」を構成する業者だけを効率的に選び出し、不要な業者を即座に破棄する仕組みを提供することで、大規模な工場建設（大規模なDP計算）でも迅速に最安値を特定できるようにする技術なのです。

2. 実際の活用例

最適化された連鎖行列積: 特定の種類の連鎖行列積問題や、区間分割問題など、コスト関数が二乗項を含みつつも線形化できる場合に適用されます。
リソース配分問題: 過去の投資額や生産量に依存して、現在の最適な配分を決定するようなDP問題で、計算量を削減するために用いられます。

資格試験向けチェックポイント

Convex Hull Trickは、日本のIT資格試験の分類において、「アルゴリズムと計算量」の中でも、特に「動的計画法」の「高度な DP」に位置づけられます。そのため、出題されるとすれば、応用情報技術者試験（AP）や、さらに高度な専門知識を問う試験の範囲となる可能性が高いです。

チェックポイント

適用条件の理解: CHTは、DPの遷移が「一次関数の最小化（または最大化）」の形をしている場合に適用できることを覚えておきましょう。これができない DP には CHT は使えません。
幾何学的な原理: CHTの核心は、最適解が常に「凸包」の境界（包絡線）上に存在するという幾何学的な性質を利用している点です。このキーワード（凸包、包絡線）と最小化の関係を理解しておくと、知識問題に対応しやすくなります。
計算量削減の目的: CHTの主な目的は、 $O(N^2)$ や $O(N \log N)$ の DP を $O(N)$ に近づけ、大規模なデータを処理できるようにすることです。なぜ高速化が必要なのかという背景を理解することが、高度な DP を学ぶ上で非常に重要だと感じます。