けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Greedy:凸性の活用

AtCoder ABC 359 F - Tree Degree Optimization (2D, 青色, 550 点)

資源配分問題などとも呼ばれる、貪欲法が使える問題! 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …

CPSCO2019 Session3 G - Grand Election (4D, 800 点設定)

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…