Advent of Code 2025 Day 2: Gift Shop をRustで解いた

Advent of Code

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

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

Day 2: Gift Shop

part1 問題概要

ギフトショップの商品IDが範囲で与えられます。
例：
11-22,95-115,998-1012,...
これは11〜22, 95〜115, 998〜1012…という感じで「連続したIDの区間」がカンマ区切りで並んでいる。

無効なID（invalid ID）の定義：
10進数表記がある数字列 X を「ちょうど2回」並べた形になっているもの

例：

• 55 = 5 を2回 → 無効ID
• 6464 = 64 を2回 → 無効ID
• 123123 = 123 を2回 → 無効ID

先頭に 0 が付くようなIDは存在しない（0101 みたいなのはそもそもIDとして出てこない）。
なので 101 は「パターン+パターン」ではないので無視してよい。

やること：

• すべての範囲の中に現れる 無効ID を全部探す。
• それらの 数値を全部足し合わせる。
• その合計が答え。

回答

入力の最大桁が10桁だったので、5桁までの数を回していって、invalid numberを作り、
これが範囲に入っているかを判定します。範囲は入力が小さかったので全探索していますが、適切にB木とかで管理しとけばここももう少し計算量サボれる気がします。

use std::cmp::max;

use itertools::Itertools;
use proconio::input;

fn parse_input(s: &str) -> Vec<(usize, usize)> {
    let hi = s.split(',').collect_vec();
    hi.into_iter()
        .map(|e| {
            let sp = e
                .split('-')
                .map(|e| e.parse::<usize>().unwrap())
                .collect_vec();
            (sp[0], sp[1])
        })
        .collect_vec()
}

fn main() {
    input! {
        s: String
    }
    let ab = parse_input(s.as_str());
    let ma = ab
        .iter()
        .map(|&e| max(e.0, e.1))
        .max()
        .unwrap()
        .to_string()
        .len();
    let mut ans = 0;
    for num in 1usize.. {
        let rep = format!("{}{}", num, num).parse::<usize>().unwrap();
        if rep.to_string().len() > ma {
            break;
        }
        for &(l, r) in ab.iter() {
            if l <= rep && rep <= r {
                ans += rep;
                break;
            }
        }
    }
    println!("{}", ans);
}

part2 問題概要

Part 1 のルール：

「ある数字列を ちょうど2回 繰り返した形だけが無効ID」

例：

• 55 = 5×2
• 6464 = 64×2
• 123123 = 123×2

Part 2 の新ルール：

「ある数字列を 2回以上 繰り返した形 なら全部無効ID」

つまりパターンを2回だけじゃなく、3回・4回・5回…でもOK

例：

• 12341234 = 1234×2 → 無効
• 123123123 = 123×3 → 無効
• 1212121212 = 12×5 → 無効
• 1111111 = 1×7 → 無効

回答

上の方針を2回以上も探索できるようにちょっと探索すれば答えです。特別なことはしていません。
max桁が10桁なので追加したループも最大高々5回しか回らないです。

use std::{cmp::max, collections::HashSet};

use itertools::Itertools;
use proconio::input;

fn parse_input(s: &str) -> Vec<(usize, usize)> {
    let hi = s.split(',').collect_vec();
    hi.into_iter()
        .map(|e| {
            let sp = e
                .split('-')
                .map(|e| e.parse::<usize>().unwrap())
                .collect_vec();
            (sp[0], sp[1])
        })
        .collect_vec()
}

fn main() {
    input! {
        s: String
    }
    let ab = parse_input(s.as_str());
    let ma = ab
        .iter()
        .map(|&e| max(e.0, e.1))
        .max()
        .unwrap()
        .to_string()
        .len();
    let mut ans = HashSet::new();
    for num in 1usize.. {
        let rep = num.to_string().repeat(2).parse::<usize>().unwrap();
        if rep.to_string().len() > ma {
            break;
        }
        for rc in 2.. {
            let rep = num.to_string().repeat(rc).parse::<usize>().unwrap();
            if rep.to_string().len() > ma {
                break;
            }
            for &(l, r) in ab.iter() {
                if l <= rep && rep <= r {
                    ans.insert(rep);
                    break;
                }
            }
        }
    }
    let ans = ans.iter().sum::<usize>();
    println!("{}", ans);
}

おわりに

Day3も頑張ります！