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

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

n個からk個選んだものの最適化

AOJ 3048 Averaging (AUPC 2018 day2-J)

二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…

AtCoder ABC 116 D - Various Sushi (400 点)

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった! 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…

CS Academy 082 DIV1 E - Water Supply

ラグランジュ緩和か、、、なのん しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白いのんな。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最…