貪欲法と交換論
局所選択の交換または候補の支配関係から、調べる順序・残す候補・定数個のcaseを確定する。
この典型を扱う単元: 交換論から選択順を導く
検索別名: greedy algorithm、交換法、貪欲法
未知問からこの典型を見つける手掛かり
- 扱う対象
- ソート
- 割り当て
- 選択
- 順序
- 使う手掛かり
- 交換
- 大きい順
- 小さい順
- 局所
- 保つ不変量
- 先に選
- 悪化しない
- 最適解
- 求めるもの
- 最大
- 最小
- 構成
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。
交換論から選択順を導くで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC214 E「Packing Under Range Regulations」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC225 E「7」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC225 F「String Cards」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC226 G「The baggage」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC227 E「Swap」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC228 H「Histogram」 公式問題主題: Convex Hull Trick・直線包絡 / 補助タグ
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP / 補助タグ
技能・出典
主題: 値域集約による部分列DP
主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC245 E「Wrapping Chocolate」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC252 F「Bread」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC254 Ex「Multiply or Divide by 2」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC257 E「Addition and Multiplication 2」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC259 F「Select Edges」 公式問題主題: 根付き木DP・部分木集約 / 補助タグ
- ABC262 F「Erase and Rotate」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する / 補助タグ
技能・出典
主題: 接尾辞の順序とLCPを索引化する
主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC268 F「Best Concatenation」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC271 Ex「General General」 公式問題主題: gcdと整数解の成立条件 / 補助タグ
- ABC274 G「Security Camera 3」 公式問題主題: 二部matching・Hall・Kőnig / 補助タグ
- ABC290 Ex「Bow Meow Optimization」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC290 G「Edge Elimination」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC298 F「Rook Score」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC299 G「Minimum Permutation」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC304 Ex「Constrained Topological Sort」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC305 Ex「Shojin」 公式問題主題: Lagrangian relaxation・Aliens trick / 補助タグ
技能・出典
主題: Lagrangian relaxation・Aliens trick
主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: prefix分割DP、貪欲法と交換論
- ABC308 F「Vouchers」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC312 F「Cans and Openers」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC314 G「Amulets」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
技能・出典
主題: ordered set・multisetの動的順序管理
主タグ: ordered set・multisetの動的順序管理 / 補助タグ: 貪欲法と交換論、尺取り法・sliding window
- ABC318 F「Octopus」 公式問題主題: 整数境界と同値区間を正確に分ける / 補助タグ
- ABC319 F「Fighter Takahashi」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC320 G「Slot Strategy 2 (Hard)」 公式問題主題: 二部matching・Hall・Kőnig / 補助タグ
技能・出典
主タグ: 二部matching・Hall・Kőnig / 補助タグ: 座標・値の順序保存圧縮、貪欲法と交換論、剰余周期・指数法則、単調境界探索
- ABC322 G「Two Kinds of Base」 公式問題主題: 素因数分解と約数構造 / 補助タグ
- ABC333 E「Takahashi Quest」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC359 F「Tree Degree Optimization」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC366 F「Maximum Composition」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC371 G「Lexicographically Smallest Permutation」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC374 E「Sensor Optimization Dilemma 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC376 E「Max × Sum」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC376 G「Treasure Hunting」 公式問題主題: 01 on Tree・親先行順序のcluster縮約 / 補助タグ
- ABC383 E「Sum of Max Matching」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
- ABC384 E「Takahashi is Slime 2」 公式問題主題: priority queue・best-first列挙 / 補助タグ
- ABC385 E「Snowflake Tree」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC388 E「Simultaneous Kagamimochi」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC390 E「Vitamin Balance」 公式問題主題: 資源・容量DP / 補助タグ
- ABC404 E「Bowls and Beans」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC407 E「Most Valuable Parentheses」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC408 E「Minimum OR Path」 公式問題主題: bitwise greedyによるmask最適化 / 補助タグ
- ABC412 F「Socks 4」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC415 G「Get Many Cola」 公式問題主題: 大容量unbounded knapsackのeventual linearity / 補助タグ
技能・出典
主題: 大容量unbounded knapsackのeventual linearity
主タグ: 大容量unbounded knapsackのeventual linearity / 補助タグ: 貪欲法と交換論
- ABC416 G「Concat (1st)」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC417 E「A Path in A Dictionary」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC432 F「Candy Redistribution」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC433 E「Max Matrix 2」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC434 F「Concat (2nd)」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC440 F「Egoism」 公式問題主題: 区間monoid要約 / 補助タグ
- ABC447 E「Divide Graph」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC453 F「Avoid Division」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC454 F「Make it Palindrome 2」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 補助タグ
- ABC457 E「Crossing Table Cloth」 公式問題主題: 交換論から選択順を導く / 主タグ
- ABC464 G「Celester 2」 公式問題主題: path matchingのheap縮約greedy / 補助タグ
- ABC466 E「Range Flip」 公式問題主題: prefix分割DP / 補助タグ