交換論から選択順を導く
概要
貪欲法と交換論
局所選択の交換または候補の支配関係から、調べる順序・残す候補・定数個のcaseを確定する。
二進操作を木へ写して深い一致を優先する例
ABC254 Exでは整数を二進表記の節点と見なし、末尾を一桁削る操作を親への移動に写す。二つの多重集合の要素を深い節点から照合し、一致できる対をその場で確定する。浅い祖先まで先に動かした対を深い位置で一致させ直しても移動回数は増えないため、余剰だけを親へ渡す順序が安全である。片側で許される移動の違いは別に判定する。この例の再利用点は「操作を祖先関係へ変換すること」と「深い一致を交換論で確定すること」の組合せであり、二進表記専用の独立技能としては扱わない。
考え方
今選ぶ候補を固定しても、任意の最適解をその選択を含む解へ悪化させず変形できることを示す。局所比較から大域最適へつなぐ橋が交換論であり、「良さそうな順」だけでは根拠にならない。
交換後の両者の制約と、縮約後の問題を確認する
区間割当てで最早締切aを現在位置xへ置くなら、元の解でaを置いたyとxの相手bを交換する。aがxへ入るだけでなく、L_b≤x≤y≤R_a≤R_bからbもyへ入ることを示す。二属性の箱割当てでは、後続チョコの第一辺は現在以下、交換で渡す箱の第二辺は元の箱以上という二つの条件を別々に使う。交換する片方だけを検査してはならない。
最適併合では費用をΣ葉重み×深さへ数え直す。最小二重みa,bを最深の兄弟葉へ交換しても費用は増えず、二葉を和a+bへ縮約すると費用がa+bだけ減り、残りも同じ最適併合問題になる。従ってOPT(S)=a+b+OPT((S−{a,b})∪{a+b})を葉数について反復できる。これがABC252 FのHuffman法の根拠である。葉の順序や隣接併合が固定される場合は自由な交換ができず、この証明をそのまま使えない。
緩和した最適値と実現可能性を分ける
操作の削除量だけを硬貨へ写すと、硬貨最小枚数は元の切断数の下界になる。しかし硬貨の表現を、重ならない部分木として配置できるとは限らない。まず枚数を増やさない具体的な交換を示し、次に配置を深さについて帰納する。ABC290 GではK V_j+V_l=V_{j+1}+K V_{l−1}という交換と、V_H−1=KV_{H−1}という子への容量の式が、二つの証明をそれぞれ担う。
交換を直接追う代わりに、全解に共通の下界を達成する方法もある。木上の対応付けでは、各子部分木の供給数と需要数の差δは親辺の正味流量となり、少なくとも|δ|の通過が必要である。内部で一致できる供給と需要を全て相殺し、残りだけを親へ送ればこの下界を達成する。ただし辺ごとの通行方向を確認する。ABC254 Exでは0辺は両向き、1辺は上向きだけなので、1辺の子に需要余剰が残る場合は不可能である。「深い方が得」という直感を、各辺の下界と達成へ接続する。
一操作の下界を、達成する操作列へつなぐ
完成形で0になる整数Fが一操作で高々1しか減らないなら、初期Fは必要操作回数の下界である。しかし「閉路へ分解できる」「局所的に直せる」だけでは、その下界を毎回1ずつ減らして完成することは示せない。達成する操作の順序、使用できる要素、残る問題の条件まで与える。
隣接逆転の例では、異色の逆転数Fは異色の隣接交換でだけ変わる。同色の隣接逆転は無料で直し、異色の隣接逆転は費用1で直す。どちらも全体の逆転数を1減らすので停止し、費用を払ったときだけFを1減らして完成形の0にする。これで必要費用Fを達成する。停止量と費用下界が別の量でもよい。
任意交換のABC302 Gでは、現在値→目標値の4×4誤配置Cを作り、値順序pの前向き重みF(p)を下界にする。逆向きpairの相殺は全pのFを一律1減らす。その後の4頂点の均衡graphは、重み0の辺の補完を含め、二種類の3-cycleと一種類の4-cycleへ表せる。各ℓ-cycleをℓ−1交換で直す具体列が、あるpのFと同じ費用となる。ここでは値種類4によるgraph分類が達成性の鍵であり、任意の種類数に閉路分解の存在だけを根拠に同じpotential式を使えない。
成立条件と計算量
交換後も制約が保たれることを確認し、未確定部分に同じ議論を反復する。sortやheapの費用に加えて交換の対象を探す費用を数える。独立集合の交換公理が使える場合はmatroidの節へ進む。
問題一覧
- ABC447 E「Divide Graph」 公式問題組合せ: DSUによる連結成分管理・縮約
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 貪欲法と交換論 / 補助タグ: DSUによる連結成分管理・縮約
- ABC376 E「Max × Sum」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: ordered set・multisetの動的順序管理
- ABC388 E「Simultaneous Kagamimochi」 公式問題組合せ: 単調境界を証明して探索する
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。 - ABC257 E「Addition and Multiplication 2」 公式問題
- ABC417 E「A Path in A Dictionary」 公式問題組合せ: 状態グラフのモデリングと探索
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。主タグ: 貪欲法と交換論 / 補助タグ: 状態グラフのモデリングと探索
- ABC404 E「Bowls and Beans」 公式問題
- ABC308 F「Vouchers」 公式問題組合せ: event順にactive集合を更新する
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 貪欲法と交換論 / 補助タグ: event・値順のオフライン走査
- ABC385 E「Snowflake Tree」 公式問題
- ABC457 E「Crossing Table Cloth」 公式問題
- ABC407 E「Most Valuable Parentheses」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: priority queue・best-first列挙
- ABC298 F「Rook Score」 公式問題
- ABC312 F「Cans and Openers」 公式問題
- ABC245 E「Wrapping Chocolate」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理
- ABC252 F「Bread」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: priority queue・best-first列挙
- ABC433 E「Max Matrix 2」 公式問題組合せ: event順にactive集合を更新する
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 貪欲法と交換論 / 補助タグ: event・値順のオフライン走査
- ABC225 E「7」 公式問題組合せ: 幾何の基本判定と座標変換
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 貪欲法と交換論 / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC214 E「Packing Under Range Regulations」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 貪欲法と交換論 / 補助タグ: event・値順のオフライン走査、priority queue・best-first列挙
- ABC268 F「Best Concatenation」 公式問題
- ABC366 F「Maximum Composition」 公式問題組合せ: 資源・容量DP
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 貪欲法と交換論 / 補助タグ: 資源軸knapsack DP
- ABC299 G「Minimum Permutation」 公式問題組合せ: 区間monoid要約
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 貪欲法と交換論 / 補助タグ: 区間monoid要約
- ABC262 F「Erase and Rotate」 公式問題組合せ: 区間monoid要約
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 貪欲法と交換論 / 補助タグ: 区間monoid要約
- ABC371 G「Lexicographically Smallest Permutation」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。追加で学ぶ技能: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 貪欲法と交換論、一次合同・CRT / 補助タグ: 関数グラフのcycle・tree分解
- ABC226 G「The baggage」 公式問題
- ABC290 G「Edge Elimination」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 貪欲法と交換論 / 補助タグ: 有界全列挙・有限case分解
- ABC225 F「String Cards」 公式問題組合せ: 列・subsequence DP
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。主タグ: 貪欲法と交換論 / 補助タグ: 列・subsequence DP
- ABC254 Ex「Multiply or Divide by 2」 公式問題組合せ: bit列をTrieで索引化する
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: bit列をTrieで索引化する(整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。)。主タグ: 貪欲法と交換論 / 補助タグ: binary Trieによるbit列索引
- ABC434 F「Concat (2nd)」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: Z algorithmによるprefix matching(既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。)。主タグ: 貪欲法と交換論 / 補助タグ: Z algorithmによるprefix matching
- ABC304 Ex「Constrained Topological Sort」 公式問題
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: DAGのtopological processing
- ABC290 Ex「Bow Meow Optimization」 公式問題組合せ: 資源・容量DP
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 貪欲法と交換論 / 補助タグ: 資源軸knapsack DP
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC227 E「Swap」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 - ABC228 H「Histogram」 公式問題
技能・出典
主題: Convex Hull Trick・直線包絡(一次関数候補の傾き・交点順を保ち、query点で包絡線上の最適な直線を選べる。)。既習技能: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Convex Hull Trick・直線包絡 / 補助タグ: prefix分割DP、貪欲法と交換論
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC259 F「Select Edges」 公式問題主題: 根付き木DP・部分木集約
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 貪欲法と交換論
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC271 Ex「General General」 公式問題主題: gcdと整数解の成立条件
技能・出典
主題: gcdと整数解の成立条件(整除条件や一次不定方程式の可解性をgcdで特徴付け、必要なら拡張EuclidでBézout整数解を構成できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Bézout等式・一次不定方程式 / 補助タグ: 有界全列挙・有限case分解、貪欲法と交換論
- ABC274 G「Security Camera 3」 公式問題
技能・出典
主題: 二部matching・Hall・Kőnig(左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 二部matching・Hall・Kőnig / 補助タグ: 貪欲法と交換論
- ABC305 Ex「Shojin」 公式問題
技能・出典
主題: Lagrangian relaxation・Aliens trick(個数制約へpenalty λを加えたoracleで双対下界を求める。厳密復元には個数別最適値の離散凸性などから対象個数で双対ギャップがないことを証明し、その上で個数単調性とtie-breakにより支持直線を探索する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: prefix分割DP、貪欲法と交換論
- ABC314 G「Amulets」 公式問題
技能・出典
主題: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: ordered set・multisetの動的順序管理 / 補助タグ: 貪欲法と交換論、尺取り法・sliding window
- ABC318 F「Octopus」 公式問題主題: 整数境界と同値区間を正確に分ける
技能・出典
主題: 整数境界と同値区間を正確に分ける(成立判定が変わり得る整数境界を全て列挙し、隣り合う境界の間で判定が一定であることを示して、代表点判定と区間長で整数解の個数を求められる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 二部matching・Hall・Kőnig、貪欲法と交換論
- ABC319 F「Fighter Takahashi」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 貪欲法と交換論、priority queue・best-first列挙
- ABC320 G「Slot Strategy 2 (Hard)」 公式問題
技能・出典
主題: 二部matching・Hall・Kőnig(左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 剰余周期と指数法則を利用する(剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 周期性による候補時刻の圧縮と単調判定の二分探索を前提に、時間上限Tで各リールが同じ数字を停止できる時刻へ辺を張る。リールと時刻の一対一対応を二部matchingで判定することが主題。主タグ: 二部matching・Hall・Kőnig / 補助タグ: 座標・値の順序保存圧縮、貪欲法と交換論、剰余周期・指数法則、単調境界探索
- ABC322 G「Two Kinds of Base」 公式問題主題: 素因数分解と約数構造
技能・出典
主題: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 - ABC333 E「Takahashi Quest」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 構成解・witness復元 / 補助タグ: 貪欲法と交換論、累積和・差分配列
- ABC359 F「Tree Degree Optimization」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 貪欲法と交換論、priority queue・best-first列挙
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。) / priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 貪欲法と交換論、資源軸knapsack DP、priority queue・best-first列挙
- ABC374 E「Sensor Optimization Dilemma 2」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 - ABC376 G「Treasure Hunting」 公式問題
技能・出典
主題: 01 on Tree・親先行順序のcluster縮約(親先行制約下の交換比較をcluster統計へまとめ、01 on Treeの縮約貪欲で最適順序を構成できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 01 on Tree・親先行順序のcluster縮約 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論、priority queue・best-first列挙
- ABC383 E「Sum of Max Matching」 公式問題
技能・出典
主題: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Kruskal順の閾値DSU sweep / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論
- ABC384 E「Takahashi is Slime 2」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 貪欲法と交換論
- ABC390 E「Vitamin Balance」 公式問題主題: 資源・容量DP
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 貪欲法と交換論
- ABC408 E「Minimum OR Path」 公式問題
技能・出典
主題: bitwise greedyによるmask最適化(上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: bitwise greedyによるmask最適化 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論
- ABC412 F「Socks 4」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 総数順の最適方策を証明し、自己loopを移項する。dp_i=(1+Σ_{j>i}A_j dp_j/S)/(1−Σ_{j<i}A_j/S)。prefix Aと降順の重み付きsuffix和で、一状態の全色走査を定数時間へ落とす。主タグ: 確率・期待値DP / 補助タグ: DP遷移の集約・高速化、貪欲法と交換論、法上の四則演算・高速累乗・逆元
- ABC415 G「Get Many Cola」 公式問題
技能・出典
主題: 大容量unbounded knapsackのeventual linearity(剰余の鳩の巣原理と密度交換で非基準itemの使用量を界し、有限prefix DPと最大密度itemの反復から巨大capacityの最適値を求められる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 大容量unbounded knapsackのeventual linearity / 補助タグ: 貪欲法と交換論
- ABC416 G「Concat (1st)」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 - ABC432 F「Candy Redistribution」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 構成解・witness復元、貪欲法と交換論
- ABC440 F「Egoism」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 区間monoid要約 / 補助タグ: 貪欲法と交換論
- ABC453 F「Avoid Division」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 木の均衡分離点から重心分解へ進む(非負頂点重みの総和に対し、除去後の各成分を半分以下にする一点を線形時間で選び、通常の頂点数重心と葉数重心を区別できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 N=2を別扱いし、元の木の葉に重み1、他に0を置いて一点だけ均衡分離点を選ぶ。各成分の葉数が全葉数の半分以下になることを使い、残数最大の異なるgroupへ色を配る。削除後に生じた葉を数え直したり、各成分を再帰的に重心分解したりしない。主タグ: 構成解・witness復元 / 補助タグ: 貪欲法と交換論、木の均衡分離点と重心分解
- ABC454 F「Make it Palindrome 2」 公式問題
技能・出典
主題: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。 - ABC464 G「Celester 2」 公式問題
技能・出典
主題: path matchingのheap縮約greedy(重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: path matchingのheap縮約greedy / 補助タグ: 貪欲法と交換論
- ABC466 E「Range Flip」 公式問題主題: prefix分割DP
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: prefix分割DP / 補助タグ: 貪欲法と交換論
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。選択の直感を交換論法や支配関係で裏付け、反例のある貪欲法を見分ける。
対象色の読み方は本書の読み方を参照してください。
概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-greedy-exchange
習得する技能
- 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: matroid greedy、path matchingのheap縮約greedy、cut・cycle性質から最適全域木を構成する、01 on Tree・親先行順序のcluster縮約。
局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。
このUnitでは扱わないもの
- 対称操作による状態の正規化。