分離凸・凹の単調限界値選択
各対象の限界費用が単調増加(または限界利益が単調減少)することを使い、複数の限界値列から必要な上位・下位K項をpriority queue mergeまたは値の閾値計数で選ぶ。
この典型を扱う単元: 分離凸・凹の単調限界値選択
検索別名: marginal-cost greedy、monotone marginal selection、separable convex allocation、限界利益選択、限界費用貪欲
未知問からこの典型を見つける手掛かり
- 扱う対象
- marginal sequence
- resources
- separable concave rewards
- separable convex costs
- 使う手掛かり
- 一単位ずつ配る
- 複数の単調列から上位K項
- 離散凸
- 離散凹
- 保つ不変量
- k-way mergeまたは閾値別個数
- 限界値の単調性
- 求めるもの
- 最大総利益
- 最小配分費用
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 幾何・凸最適化への変換
関連する典型
学習成果と学習単位
分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。
分離凸・凹の単調限界値選択で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC216 E「Amusement Park」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC359 F「Tree Degree Optimization」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC389 E「Square Price」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC383 G「Bar Cover」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC216 E「Amusement Park」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC359 F「Tree Degree Optimization」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC369 G「As far as possible」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC383 G「Bar Cover」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ
- ABC389 E「Square Price」 公式問題主題: 分離凸・凹の単調限界値選択 / 主タグ