幾何・凸最適化
概要
座標・向き・円環順序から凸包と半平面へ進み、幾何的な実行可能領域を表す。直線包絡を幾何と関数の橋渡しとして学ぶ。凸性の節では一次元の最適化から限界値選択・slope trickへ進み、比率目的を単調判定へ変換するfractional programmingを学ぶ。その後、順序制約のPAV、個数制約を罰則へ移すAliens trick、遷移行列のMonge性を扱う。最後に二変数の凸区分線形整数最適化で、連続的な候補と整数格子の近傍保証を組み合わせる。DP・データ構造・数論の道具がどの条件で再利用できるかを確認する。
幾何・凸最適化への変換
配置・距離・目的関数を幾何predicateや凸構造へ変換する。
考え方
座標の問題では、まず距離や位置関係を式へ直し、その式を扱いやすくする座標を探す。例えば二点 と のマンハッタン距離(各座標の差の絶対値の和)は である。ここで新しい座標を と置くと、二点は と に移り、距離は と求まる。
これはこの二点だけの偶然ではない。二点の座標差を 、変換後の差を とすると、
が成り立つ。元の二つの差が同符号なら和の絶対値が、異符号なら差の絶対値が左辺と一致し、もう片方はそれを超えないからである。一点からの距離がある上限以下という条件は、変換後には それぞれの区間条件になる。斜めの境界を持つ領域を、軸に平行な長方形として扱える。
ただし、元が整数格子の問題なら、変換先の整数点をすべて使ってよいわけではない。逆変換は
なので、整数の が元の整数点に戻る条件は、両者の偶奇が同じことである。例えば は へ戻り、元の格子点ではない。距離の式と一緒に、実行可能な点の条件も移す。この判定や変換を詳しく学ぶ入口が幾何の基本判定と座標変換である。
式へ直した後は、何の構造を利用するかを分けて考える。点集合の内部候補を捨てられるなら凸境界・半平面制約へ、選ぶ値を動かしたときの費用の増減に規則があるなら凸性・傾き・限界費用へ進む。領域が凸であることと、そこで最小化する関数が凸であることは別の性質であり、使える候補削減も異なる。
成立条件と計算量
変換後の式が元の条件と同値かを確かめる。上の変換では、距離の条件に加えて整数座標の偶奇条件を保つ必要がある。一般の最適化でも、連続最適解を丸めれば整数最適解になるとは限らない。
固定長整数の演算を定数時間と数えれば、一点の座標変換は 、 点全体では 時間である。その後の整列・領域内の集計・最適化には別の費用がかかるため、変換だけの計算量で解法全体を評価しない。外積の積や座標の和・差が収まる整数幅、境界を含むか、浮動小数点の誤差も確認する。各子単元で、候補を捨てる根拠と必要な操作の費用を対応させる。
章の構成
項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。
- 幾何の基本判定と座標変換 — 水色
- 円環順序・chord交差 — 青色。概念上の親: 幾何の基本判定と座標変換
- 凸境界・半平面制約を扱う — 青色(導入)
- 凸包・支持方向・境界候補 — 青色。概念上の親: 凸境界・半平面制約を扱う
- 半平面制約・凸領域の共通部分 — 黄色。概念上の親: 凸境界・半平面制約を扱う
- Convex Hull Trick・直線包絡 — 黄色
- 凸性・傾き・限界費用・slope trick — 青色(導入)
- 一次元凸・単峰最適化 — 青色。概念上の親: 凸性・傾き・限界費用・slope trick
- 分離凸・凹の単調限界値選択 — 青色。概念上の親: 凸性・傾き・限界費用・slope trick
- slope trick — 黄色。概念上の親: 凸性・傾き・限界費用・slope trick
- fractional programming・比率parametric search — 青色
- isotonic regression・PAV — 橙色。概念上の親: 凸性・傾き・限界費用・slope trick
- Lagrangian relaxation・Aliens trick — 橙色
- Monge・monotone minima最適化 — 橙色
- 二変数の凸区分線形整数最適化 — 橙色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC221 G「Jumping sequence」 公式問題
技能・出典
主題: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: bitsetによるword並列集合演算 / 補助タグ: 構成解・witness復元、幾何の基本判定・配置・座標変換
- ABC225 E「7」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 貪欲法と交換論 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC229 G「Longest Y」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調境界探索 / 補助タグ: 一次元凸・単峰最適化
- ABC233 Ex「Manhattan Christmas Tree」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換、累積和・差分配列
- ABC240 F「Sum Sum Max」 公式問題主題: 整数境界と同値区間を正確に分ける
技能・出典
主題: 整数境界と同値区間を正確に分ける(圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 一次元凸・単峰最適化
- ABC240 G「Teleporting Takahashi」 公式問題主題: 組合せ係数と対称性で数える
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC243 Ex「Builder Takahashi (Enhanced version)」 公式問題主題: 最短路モデル
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 最短路モデル / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC250 F「One Fourth」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 尺取り法・sliding window / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC263 G「Erasing Prime Pairs」 公式問題主題: 最大流・最小カット
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最大流・最小カット / 補助タグ: 一次元凸・単峰最適化
- ABC266 Ex「Snuke Panic (2D)」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC274 F「Fishing」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC280 G「Do Use Hexagon Grid 2」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。追加で学ぶ技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 幾何の基本判定・配置・座標変換、集合上の包除原理 / 補助タグ: 寄与の数え上げと順序交換、event・値順のオフライン走査
- ABC283 F「Permutation Distance」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 幾何の基本判定・配置・座標変換、区間monoid要約
- ABC315 F「Shortcuts」 公式問題主題: 列・subsequence DP
技能・出典
主題: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 列・subsequence DP / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC323 F「Push and Carry」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 状態・配置の正規化 / 補助タグ: 有界全列挙・有限case分解、幾何の基本判定・配置・座標変換
- ABC330 F「Minimize Bounding Square」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調境界探索 / 補助タグ: 一次元凸・単峰最適化、累積和・差分配列
- ABC343 E「7x7x7」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: 幾何の基本判定・配置・座標変換、集合上の包除原理
- ABC405 F「Chord Crossing」 公式問題主題: laminar区間族の包含木構築
技能・出典
主題: laminar区間族の包含木構築(laminar区間の開閉端点をstackで処理し、直接包含関係と各点の最小包含区間を木として構築して、包含差分を木上pathへ変換できる。)。既習技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。) / 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。)。主タグ: laminar区間族の包含木構築 / 補助タグ: 円環順序・chord交差、ancestor query・LCA
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 値域集約による部分列DP / 補助タグ: event・値順のオフライン走査、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC418 E「Trapezium」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC422 E「Colinear」 公式問題
技能・出典
主題: 乱択の成功条件と誤り確率を設計する(乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 乱択・Monte Carloアルゴリズム / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC424 F「Adding Chords」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。)。主タグ: 区間monoid要約 / 補助タグ: 円環順序・chord交差
- ABC457 G「Catch All Apples」 公式問題
技能・出典
主題: 半順序・Dilworth・最大反鎖(対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。)。既習技能: LIS・末尾の支配関係(同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 半順序・Dilworth・最大反鎖 / 補助タグ: 幾何の基本判定・配置・座標変換、LIS・末尾の支配関係
- ABC462 E「Alternating Costs」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 状態・配置の正規化 / 補助タグ: 一次元凸・単峰最適化
前提・学習成果・出典
導入対象の目安: 水色(1200–1599)。座標と向きによる判定から、凸な境界・関数の最適化へ進む入口。
対象色の読み方は本書の読み方を参照してください。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-geometry-optimization
習得する技能
- 配置・距離・目的関数を幾何predicateや凸構造へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
orientationなどの幾何predicateから凸境界・傾き・dual penaltyへ進み、候補を構造的に削減する。
このUnitでは扱わないもの
- なし