Advent of Code 2025 Day 8: Playground をRustで解いた

Advent of Code

毎日2題出題されます。競技プログラミングチックに楽しめます。

この問題概要と実装解答を以下にご紹介します。
問題概要は生成AIに書いてもらったものを貼り付けています。
実装は人間が行なっています。

Day 8: Playground

part1 問題概要

3次元空間の点がa,b,cのようなカンマ区切りでXYZ座標が与えられます。
この座標を以下のルールで接続していきます。

• すべてのペアのボックス間の直線距離を考える。
• 「まだ直接つないでないペア」の中から、距離が最も短いものを 1 組選んで接続する。

接続すると：

• その2つのボックスは 同じ回路 の一部になる。
• どちらかがすでに別のボックスと繋がっていても、
  「それら全部を含む一つの回路」としてまとまる。
• もし「すでに同じ回路に属している2つ」を選んでしまった場合は、新たな統合は起きない（状態は変わらない）。

これを 距離の短い順にペアを選んで接続していく。

「最も近いボックス同士のペア」を 1000 組 接続したあと、できている回路（連結グループ）のサイズを全部調べる。
最も大きい3つの回路サイズを掛けた値を答えよ。

解答

明らかにunionfindです。
距離の近い順という話に関しては、座標数Nは1000しかないので、全ての頂点に対する距離の計算が可能です。
これを小さい順に1000個みてあげればいいので、配列に入れてソートするか、以下の実装のようにBinaryHeapに突っ込んで1000回popすれば距離が小さい1000個を得ることができるのでその頂点indexをunionfindで接続してあげればいいです。
あと、本来距離は各軸のdiffの2乗の総和をルート取る必要がありますが、浮動小数の計算により誤差が生じる可能性があるため、2乗のまま計算しています。大小関係は変わりません。

unionfindはac-library-rsのものを使わせていただいております。

use std::{cmp::Reverse, collections::BinaryHeap};

use ac_library::Dsu;
use itertools::Itertools;
use proconio::input;

fn parse_input(s: &str) -> (usize, usize, usize) {
    let s = s.split(',').collect_vec();
    let a = s[0].parse::<usize>().unwrap();
    let b = s[1].parse::<usize>().unwrap();
    let c = s[2].parse::<usize>().unwrap();
    (a, b, c)
}

fn main() {
    let count = 1000;
    let n = 1000;
    input! {
        s: [String; n]
    }
    let abc = s.iter().map(|e| parse_input(e)).collect_vec();
    let dist2 = |a: (usize, usize, usize), b: (usize, usize, usize)| {
        let (x1, y1, z1) = a;
        let (x2, y2, z2) = b;
        x1.abs_diff(x2).pow(2) + y1.abs_diff(y2).pow(2) + z1.abs_diff(z2).pow(2)
    };
    let mut heap = BinaryHeap::new();
    for i in 0..n {
        for j in i + 1..n {
            let d = dist2(abc[i], abc[j]);
            heap.push((Reverse(d), i, j));
        }
    }
    let mut uf = Dsu::new(n);
    for _ in 0..count {
        let (_, i, j) = heap.pop().unwrap();
        uf.merge(i, j);
    }
    let mut g = uf.groups().iter().map(|e| e.len()).collect_vec();
    g.sort_by_key(|&e| Reverse(e));
    assert!(g.len() >= 3);
    let ans = g[0] * g[1] * g[2];
    println!("{}", ans);
}

part2 問題概要

↑の操作を続けていくと、どこかのタイミングですべての座標が同じグループに入る瞬間がきます。
そのタイミングのマージ操作のx座標どうしの掛け算の結果を教えてください。

解答

距離が小さい順に見ていって、unionfindの結果が!sameの時に都度ansにその時の答えに更新していけば良いだけです。
すべての頂点をマージするのは $\binom{n}{2} = n * (n - 1) / 2$ かかるので、この回数だけマージしようとした際の動作をチェックしてあげればいいです。

fn main() {
    let n = 1000;
    let count = n * (n - 1) / 2;
    input! {
        s: [String; n]
    }
    let abc = s.iter().map(|e| parse_input(e)).collect_vec();
    let dist2 = |a: (usize, usize, usize), b: (usize, usize, usize)| {
        let (x1, y1, z1) = a;
        let (x2, y2, z2) = b;
        x1.abs_diff(x2).pow(2) + y1.abs_diff(y2).pow(2) + z1.abs_diff(z2).pow(2)
    };
    let mut heap = BinaryHeap::new();
    for i in 0..n {
        for j in i + 1..n {
            let d = dist2(abc[i], abc[j]);
            heap.push((Reverse(d), i, j));
        }
    }
    let mut uf = Dsu::new(n);
    let mut ans = (usize::MAX, usize::MAX);
    for _ in 0..count {
        let (_, i, j) = heap.pop().unwrap();
        if uf.same(i, j) {
            continue;
        }
        uf.merge(i, j);
        ans = (abc[i].0, abc[j].0);
    }
    println!("{}", ans.0 * ans.1);
}

終わりに

Day9も頑張ります！