priority queue・best-first列挙
現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。
この典型を扱う単元: priority queue・best-first列挙
検索別名: best-first enumeration、heap、優先度付きキュー
未知問からこの典型を見つける手掛かり
- 扱う対象
- heap
- 候補frontier
- 暗黙graph
- 使う手掛かり
- 上位K個
- 最小から順
- 閾値で解禁
- 保つ不変量
- 未確定候補の極値
- 重複排除
- 求めるもの
- best-first探索
- k番目
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
priority queue・best-first列挙で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC214 E「Packing Under Range Regulations」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC217 E「Sorting Queries」 公式問題主題: 単調進行による償却解析 / 補助タグ
- ABC218 H「Red and Blue Lamps」 公式問題主題: path matchingのheap縮約greedy / 補助タグ
技能・出典
主題: path matchingのheap縮約greedy
主タグ: path matchingのheap縮約greedy / 補助タグ: 索引付き連結リスト、priority queue・best-first列挙、状態・配置の正規化
- ABC249 F「Ignore Operations」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC250 G「Stonks」 公式問題主題: slope trick / 補助タグ
- ABC252 F「Bread」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC297 E「Kth Takoyaki Set」 公式問題主題: priority queue・best-first列挙 / 主タグ
- ABC305 E「Art Gallery on Graph」 公式問題主題: priority queue・best-first列挙 / 主タグ
- ABC307 F「Virus 2」 公式問題主題: 最短路モデル / 補助タグ
- ABC319 F「Fighter Takahashi」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC320 E「Somen Nagashi」 公式問題主題: event順にactive集合を更新する / 補助タグ
技能・出典
主タグ: event・値順のオフライン走査 / 補助タグ: ordered set・multisetの動的順序管理、priority queue・best-first列挙
- ABC331 E「Set Meal」 公式問題主題: priority queue・best-first列挙 / 主タグ
- ABC359 F「Tree Degree Optimization」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC376 G「Treasure Hunting」 公式問題主題: 01 on Tree・親先行順序のcluster縮約 / 補助タグ
- ABC384 E「Takahashi is Slime 2」 公式問題主題: priority queue・best-first列挙 / 主タグ
- ABC391 F「K-th Largest Triplet」 公式問題主題: priority queue・best-first列挙 / 主タグ
- ABC407 E「Most Valuable Parentheses」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC409 F「Connecting Points」 公式問題主題: priority queue・best-first列挙 / 主タグ
技能・出典
主題: priority queue・best-first列挙
主タグ: priority queue・best-first列挙 / 補助タグ: 有界全列挙・有限case分解、DSUによる連結成分管理・縮約
- ABC440 E「Cookies」 公式問題主題: priority queue・best-first列挙 / 主タグ