Greedy:凸性の活用
NoviSteps2D
AtCoder
AtCoder550点
青色diff
ABC-F
Greedy
Greedy:凸性の活用
凸性に着目する
グラフ
最適化問題
制約条件:総和=K
操作をちょうどK回行う
priority_queue
木
数学的帰納法に基づく考察
葉から考える
資源配分問題
凸関数
資源配分問題などとも呼ばれる、貪欲法が使える問題! 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …
AtCoder
けんちょん自作問題
コーナーケース
誤差
有理数
Greedy
区分線形関数
凸関数
制約条件:総和=K
操作
操作をK回まで行える
復元
絶対値やminを扱う問題
全部混ぜて解く
priority_queue
数列
操作をちょうどK回行う
制約条件:ちょうどK個
均等に分ける
Greedy:凸性の活用
凸性に着目する
資源配分問題
NoviSteps4D
最適化問題
辞書順
資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…