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 しておけば問題ない。