PAST201912 L グラデーション Gradation を解いた。自力では解けなかった。
使用する小さい塔の組み合わせを bit 全探索で列挙する。大きい塔と使う小さい塔に対して MST: Minimum Spanning Tree 最小全域木 (の辺のコストの合計) を求めた。 MST はクラスカル法で求めた。
クラスカル法は辺をコスト順に並べて UnionFind で連結していく。その辺が新たに連結される頂点へのものなら最小全域木 (コストの合計) に加える。問題とは違うがイメージは ↓。
// (cost, u, v) let mut e: Vec<(i64, usize, usize)> = /* ... */; e.sort(); let mut sum = 0; let mut uf = UnionFind::new(n); for &(cost, u, v) in e.iter() { if uf.same(u, v) { continue; } uf.unite(u, v); sum += cost; } sum
問題では cost
が f64
だったので fs.sort_by(|a, b| a.partial_cmp(b).unwrap());
のように工夫しないといけなかった。 Rust の f64
はおそらく NaN を理由に std::cmp::Ord
を実装できないため std::cmp::PartialOrd
が実装されている。 partial_cmp
の戻り値は Option<Ordering>
になる。問題の条件なら unwrap
しておけば問題ない。