drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ NoviSteps2D AtCoder AtCoder550点 青色diff ABC-F Greedy Greedy:凸性の活用 凸性に着目する グラフ 最適化問題 制約条件:総和=K 操作をちょうどK回行う priority_queue 木 数学的帰納法に基づく考察 葉から考える 資源配分問題 凸関数 資源配分問題などとも呼ばれる、貪欲法が使える問題！ 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 の次数)。 制約 考えたこと まず、次のことが自明に成り立つ。 ここでよく知られたこととして、逆にこれを満たす に対して、次数がこの値になるような木が存在する。このことは、プルーファーコードを用いたり、葉が必ず存在することから帰納法を活用したりすることで、証明できる。 よって問題は次の最適化問題を解くことに帰着された。 M… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2024%2F06%2F23%2F032101" title="AtCoder ABC 359 F - Tree Degree Optimization (2D, 青色, 550 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2024-06-23 03:21:01 rich https://drken1215.hatenablog.com/entry/2024/06/23/032101 1.0 100%