Advent of Code 2025 Day 7: Laboratories をRustで解いた

Advent of Code

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

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

Day 7: Laboratories

part1 問題概要

• 2Dグリッドの図が入力（. と ^ と S）。
• 1本のタキオンビームが S の位置から真下に向かって進む。
• マスの意味：
  • . … 空間。ビームはそのまま下に進む。
  • S … ビームの開始位置（ここから下方向へ進む）。
  • ^ … スプリッター（分岐装置）。

スプリッター ^ の挙動
ビームが ^ に到達したら：

• そのビームは そこで止まる（下には進まない）。
• 代わりに 左右に 1 マスずれた位置から、真下に向かう新しいビームを 2本 発射する。
• これを「ビームが 1 回分岐した」と数える。
• ただし、複数のビームが同じマスに来ることがある。これは同じビームとして数える。

スプリッターによって発生したビーム分岐の回数（split回数） の合計を求める。

解答

dp[i][j] := 上からi行目の左からj番目にレーザーが到達するか yes/no でdpする。
で、このdpを回しながら '^' に辿りついていたらans++すれば、dpを回しているうちに答えがもとまっている。

use std::mem::swap;

use proconio::{input, marker::Chars};

fn main() {
    let n = 142;
    input! {
        s: [Chars; n]
    }
    let m = s[0].len();
    let mut start = (usize::MAX, usize::MAX);
    for i in 0..n {
        for j in 0..m {
            if s[i][j] == 'S' {
                start = (i, j);
            }
        }
    }
    let mut now = vec![false; m];
    now[start.1] = true;
    let mut ans = 0usize;
    for i in start.0..n {
        let mut new = vec![false; m];
        for j in 0..m {
            if !now[j] {
                continue;
            }
            let djs = if s[i][j] == '^' { vec![-1, 1] } else { vec![0] };
            if s[i][j] == '^' {
                ans += 1usize;
            }
            for &dj in djs.iter() {
                let nj = j as isize + dj;
                if nj < 0 || nj >= m as isize {
                    continue;
                }
                let nj = nj as usize;
                new[nj] = true;
            }
        }
        swap(&mut now, &mut new);
    }

    println!("{}", ans);
}

part2問題概要

part1では同じマスに来たレーザーは1種として数えたが、part2では、由来の経路が違うものは違うものと数える。
つまりはどんなふうに分岐しながら進んだかで、それぞれ違うものとして数える
→ 最終的に存在する 「経路のパターンの数」 を数えたい。

解答

dp[i][j] := 上からi番目、左からj番目に到達するパスの個数
としてdpすれば良い。part1とほとんど実装が一緒。

最終的にはdp[n]の総和を計算すればよい。

fn main() {
    let n = 142;
    input! {
        s: [Chars; n]
    }
    let m = s[0].len();
    let mut start = (usize::MAX, usize::MAX);
    for i in 0..n {
        for j in 0..m {
            if s[i][j] == 'S' {
                start = (i, j);
            }
        }
    }
    let mut now = vec![0usize; m];
    now[start.1] = 1;
    for i in start.0..n {
        let mut new = vec![0usize; m];
        for j in 0..m {
            if now[j] == 0 {
                continue;
            }
            let djs = if s[i][j] == '^' { vec![-1, 1] } else { vec![0] };
            let num = now[j];
            for &dj in djs.iter() {
                let nj = j as isize + dj;
                if nj < 0 || nj >= m as isize {
                    continue;
                }
                let nj = nj as usize;
                new[nj] += num
            }
        }
        swap(&mut now, &mut new);
    }

    let ans = now.iter().sum::<usize>();
    println!("{}", ans);
}

最後に

day8も頑張ります！