bouzuya https://blog.hatena.ne.jp/bouzuya/ bouzuya.hatenablog.com https://bouzuya.hatenablog.com/ PAST201912 L グラデーション Gradation を解いた。自力では解けなかった。 使用する小さい塔の組み合わせを bit 全探索で列挙する。大きい塔と使う小さい塔に対して MST: Minimum Spanning Tree 最小全域木 (の辺のコストの合計) を求めた。 MST はクラスカル法で求めた。 クラスカル法は辺をコスト順に並べて UnionFind で連結していく。その辺が新たに連結される頂点へのものなら最小全域木 (コストの合計) に加える。問題とは違うがイメージは ↓。 // (cost, u, v) let mut e: Vec<(i64, usize, usi… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbouzuya.hatenablog.com%2Fentry%2F2020%2F05%2F26%2F221615" title="past201912_l を解いた - bouzuya.hatenablog.com" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-05-26 22:16:15 rich https://bouzuya.hatenablog.com/entry/2020/05/26/221615 1.0 100%