👨‍🍳
ABC400:Rustで解く！問題解説

2025/04/06に公開
AtCoder Beginner Contest 400のA~E問題をRustで解いた際の解法をまとめました。

 A問題問題
https://atcoder.jp/contests/abc400/tasks/abc400_a
解説
400 が A で割り切れるかどうかを判定します。割り切れる場合は 400 \div A の結果を出力し、そうでない場合は -1 を出力します。
コード
abc400a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        a: usize,
    }

    // 400がaで割り切れるか判定
    if 400 % a == 0 {
        println!("{}", 400 / a);
    } else {
        println!("-1");
    }
}

 B問題問題
https://atcoder.jp/contests/abc400/tasks/abc400_b
解説
N^0 + N^1 + \dots + N^M を計算します。ただし、計算途中で値が 10^9 を超えた場合は inf を出力します。
コード
abc400b.rs
use proconio::input;
const INF: usize = 1_000_000_000;

fn main() {
    // 入力
    input! {
        n: usize,
        m: usize,
    }

    // 初期値を1 (x^0) で初期化
    let mut tot = 1;
    let mut cur = 1;

    // x^1 + ... + x^m を加算
    for _ in 1..=m {
        cur *= n;
        tot += cur;

        // 合計が 10^9 を超えた場合
        if tot > INF {
            println!("inf");
            return;
        }
    }
    
    // 出力
    println!("{}", tot);
}

 C問題問題
https://atcoder.jp/contests/abc400/tasks/abc400_c
解説
1以上 N 以下の正の整数 X について、正の整数の組 (a, b) を用いて X = 2^a \times b^2 を満たすXの個数を数え上げます。
考え方としては、a と b のうち片方を固定して、もう片方を順番に調べます。この問題では、N が 10^{18} と非常に大きいため、値の範囲が小さい a を固定して b を調べる方が効率的です。
また、X の個数を答える問題のため、正の整数の組 (a, b) が異なっていても最終的な値が同じになるものは1通りと数えます。この性質を考慮すると、実際に調べるべき a は 1 と 2 の場合だけで十分です。
理由a が奇数の場合、

a = 2m + 1 とおくと、

\begin{aligned}
X &= 2^{2m+1} \times b^2 \\
  &= 2^1 \times (2^m \times b)^2
\end{aligned}
と変形できるため、この X は、a = 1 に含まれます。
また、a が偶数の場合、

a = 2m とおくと、

\begin{aligned}
X &= 2^{2m} \times b^2 \\
  &= 2^2 \times (2^{m-1} \times b)^2 \\
\end{aligned}
と変形できるため、この X は、a = 2 に含まれます。
したがって、求める答えは以下の式で計算できます。
\lfloor \sqrt{\frac{N}{2}} \rfloor + \lfloor \sqrt{\frac{N}{4}} \rfloor
コード
abc400c.rs
use num_integer::Roots;
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize,
    }

    // 1以上N以下で、2^a * b^2 = Xを満たすXの個数を答える
    // aを固定してbの個数を数え上げるが、調べるaは1,2だけでよい
    let mut ans = 0;
    let mut multi = 1;
    for _ in 1..=2 {
        multi *= 2;
        ans += (n / multi).sqrt();
    }

    // 出力
    println!("{}", ans);
}

 D問題問題
https://atcoder.jp/contests/abc400/tasks/abc400_d
解説
最初の位置から目的の位置へ移動する際に、1つ先、2つ先にある壁を壊す回数を最小化します。これは、BFS(幅優先探索)を用いることで解くことができます。
特に、壁を壊す回数が0または1に限定されるため、01BFSを使用することで効率的に解くことが可能です。01BFSでは、移動コストが0の場合はキューの先頭に、移動コストが1の場合はキューの末尾に追加します。
解法としては、以下の通りになります。
最初の位置からスタートし、キューを用いて探索を進めます。
キューを取り出します。
現在のマスから上下左右の1つ先のマスを調べます。
道（.）の場合、壁を壊す回数は変わらず、そのマスをキューの先頭に追加します。
壁（#）の場合、壁を壊す回数を1増やし、そのマスをキューの末尾に追加します。

現在のマスから上下左右の2つ先のマスも調べます。
壁（#）の場合、壁を壊す回数を1増やし、そのマスをキューの末尾に追加します。

2~4を繰り返した後、目的の位置に到達した際の壁を壊す回数を出力します。
コード
abc400d.rs
use proconio::{input, marker::Chars, marker::Usize1};
use std::collections::VecDeque;

const INF: usize = 1 << 60;
const D4: [(usize, usize); 4] = [(!0, 0), (0, !0), (1, 0), (0, 1)]; // 上左下右
const D4_2: [(usize, usize); 4] = [(!1, 0), (0, !1), (2, 0), (0, 2)]; // 上左下右（2マス先）

fn main() {
    // 入力
    input! {
        h: usize, w: usize,
        s: [Chars; h],
        a: Usize1, b: Usize1, // 最初の位置
        c: Usize1, d: Usize1, // 目的の位置
    }

    // 最短距離とキューを初期化
    let mut dist = vec![vec![INF; w]; h];
    dist[a][b] = 0;
    let mut dq = VecDeque::new();
    dq.push_back((a, b));

    // BFS
    while let Some((cur_x, cur_y)) = dq.pop_front() {
        // 今のマスの四方にある1つ先の道に移動
        process_neighbors(cur_x, cur_y, h, w, &s, &mut dist, &mut dq, &D4, 0);
        // 今のマスの四方にある1つ先の壁に移動
        process_neighbors(cur_x, cur_y, h, w, &s, &mut dist, &mut dq, &D4, 1);
        // 今のマスの四方にある2つ先の壁に移動
        process_neighbors(cur_x, cur_y, h, w, &s, &mut dist, &mut dq, &D4_2, 1);
    }

    // 出力
    println!("{}", dist[c][d]);
}

fn process_neighbors(
    cur_x: usize, cur_y: usize,
    h: usize, w: usize,
    s: &Vec<Vec<char>>,
    dist: &mut Vec<Vec<usize>>,
    dq: &mut VecDeque<(usize, usize)>,
    directions: &[(usize, usize)],
    cost: usize,
) {
    for &(dx, dy) in directions {
        let nx = cur_x.wrapping_add(dx);
        let ny = cur_y.wrapping_add(dy);
        if nx >= h || ny >= w || (cost == 0 && s[nx][ny] == '#') || (cost == 1 && s[nx][ny] == '.') {
            continue;
        }
        if dist[nx][ny] > dist[cur_x][cur_y] + cost {
            dist[nx][ny] = dist[cur_x][cur_y] + cost;
            if cost == 0 {
                 // コスト0ならキューの先頭に追加
                dq.push_front((nx, ny));
            } else {
                // コスト1ならキューの末尾に追加
                dq.push_back((nx, ny));
            }
        }
    }
}

 E問題問題
https://atcoder.jp/contests/abc400/tasks/abc400_e
解説
この問題では、与えられる入力 A 以下の最大の「400 number」を求める必要があります。「400 number」とは「異なる2つの素因数について、それぞれの素因数の肩が偶数」の値で、具体的には以下の条件を満たす数値です。
a^p \times b^q \leq 10^{12}

a, b は素数

p, q は偶数
ここで、p, q が偶数であるため、a^p \times b^q は平方数となります。したがって、以下の式が成り立ちます。
a^{p'} \times b^{q'} \leq 10^6 (p' = \frac{p}{2}, q' = \frac{q}{2})
したがって、10^6 以下の素数を列挙し、素数2つを組み合わせて平方数を求めることで「400 number」が作ることができます。
解法としては、以下の通りになります。

10^6 以下の素数を列挙し、素数2つを用いて「400 number」を作成します。
クエリで与えられた A に対して、A 以下の最大の「400 number」を二分探索を用いて求めます。
コード
abc400e.rs
use proconio::input;
const SEARCH_MAX: usize = 1_000_000;
const INF: usize = 1 << 60;

fn main() {
    // クエリ数の入力
    input! {
        q: usize,
    }

    // 1~SEARCH_MAX の範囲で素因数の個数を数える
    let prime_count = count_primes(SEARCH_MAX);

    // 素因数が2個の数値を平方数に変換して候補を作成
    let candidates = generate_candidates(&prime_count);

    // クエリ処理
    for _ in 0..q {
        // 入力
        input! {
            a: usize,
        }

        // a 以下の最大の平方数を二分探索で取得
        let pos = below_bound(&candidates, a);
		
		// 出力
        println!("{}", candidates[pos]);
    }
}

// 素因数の個数を数える関数
fn count_primes(limit: usize) -> Vec<usize> {
    let mut cnt = vec![0; limit + 1];
    for i in 2..=limit {
        let mut cur = i;
        // 素数でない場合はスキップ
        if cnt[cur] != 0 {
            continue;
        }
        while cur <= limit {
            cnt[cur] += 1;
            cur += i;
        }
    }
    cnt
}

// 素因数が2個の数値を平方数に変換して候補を作成
fn generate_candidates(prime_count: &Vec<usize>) -> Vec<usize> {
    let mut candidates = Vec::new();
    for i in 0..=SEARCH_MAX {
        if prime_count[i] == 2 {
            candidates.push(i * i);
        }
    }
    candidates
}

// 二分探索で val 以下の最大の位置を取得
fn below_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize {
    let mut l = 0;
    let mut r = vec.len();
    while r - l > 0 {
        let m = (l + r) / 2;
        if vec[m] <= val {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if l == 0 {
        INF
    } else {
        l - 1
    }
}
A問題

B問題

C問題

D問題

E問題

Discussion
