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

2025/07/13に公開
AtCoder Beginner Contest 414のA-E問題をRustで解いた際の解法をまとめました。

 A 問題問題
https://atcoder.jp/contests/abc414/tasks/abc414_a
解説
配信を開始時刻 L から終了時刻 R まで視聴できるリスナーの人数を数える問題です。
リスナーが配信を最初から最後まで見られる条件は、リスナーの視聴可能時間帯が配信の時間帯を完全に含むことになります。

つまり、 X_i \leq L かつ R \leq Y_i の条件を満たすリスナーの人数を数えれば答えが求まります。
コード
abc414a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // リスナーの人数
        l: usize, r: usize, // 配信の開始時刻と終了時刻
        xy: [(usize, usize); n], // 各リスナーの視聴可能時間帯
    }

    // 配信を最初から最後まで見られるリスナーの人数をカウント
    let mut cnt = 0;
    for (start, end) in xy {
        // リスナーの視聴可能時間が配信時間を完全に含む場合
        if start <= l && r <= end {
            cnt += 1;
        }
    }

    // 答えを出力
    println!("{}", cnt);
}

 B 問題問題
https://atcoder.jp/contests/abc414/tasks/abc414_b
解説
ランレングス圧縮形式で与えられたデータ (文字, 個数) を元に、文字列を復元して出力する問題です。

ただし、復元した文字列の長さが100文字を超える場合は、Too Long を出力する必要があるため、先に文字列の長さをチェックします。入力データ (文字, 個数) の個数をすべて合計した結果に応じて、以下を出力します。
長さが100を超える場合

Too Long を出力します。

長さが100以下の場合
各 (文字, 個数) に基づいて文字を展開し、順番に出力します。

コード
abc414b.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize,
        cl: [(char, u128); n],
    }

    // 100文字を超える場合は、Too Longを出力
    if get_tot_length(&cl) > 100 {
        println!("Too Long");
        return;
    }

    // 100文字以下の場合は、各長さ分の文字を順番に出力
    print_runlen(&cl);
}

// 総文字数を計算する関数
fn get_tot_length(cl: &Vec<(char, u128)>) -> u128 {
    let mut tot = 0;
    for &(_c, l) in cl {
        tot += l;
    }
    tot
}

// ランレングス圧縮を展開して出力する関数
fn print_runlen(cl: &Vec<(char, u128)>) {
    for &(c, l) in cl {
        for _ in 0..l {
            print!("{}", c);
        }
    }
    return;
}

 C 問題問題
https://atcoder.jp/contests/abc414/tasks/abc414_c
解説
1以上 N 以下の整数のうち、10進数と A 進数のどちらでも回文となる値の総和を求める問題です。

以下1~3の手順で解くことができます。
10進数の回文を列挙します。

N の制約は 10^{12} より最大12桁なので、1桁から6桁までの各値について、以下の通りに回文を作ります。
元の値を文字列 s = i.to_string() に変換します。
文字列 s から、偶数桁回文 s + reverse(s) を作成します。
文字列 s から、奇数桁回文 s + reverse(s).skip(1) を作成します。
偶数桁回文、奇数桁回文を数値に戻して、N 以下の回文だけを集合に追加します。

1で列挙した回文を A 進数に変換し、再度回文か判定します。
回文であれば合計に加算します。
コード
abc414c.rs
use proconio::input;
use std::collections::BTreeSet;
const MAX_SZ: usize = 1_000_000;

fn main() {
    // 入力
    input! {
        a: usize, // A進数
        n: usize, // 値の最大値
    }

    // 求める回文の総和
    let mut ans = 0;

    // N進数の回文の集合
    let st = generate_kaibun_set(n, MAX_SZ);

    // 回文の値をA進数に変換
    for &val in &st {
        // A進数に変換
        let convert_val = convert_base_n(val, a);

        // A進数が回文なら計上
        if iskaibun(&convert_val) {
            ans += val;
        }
    }

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

// 10進数の回文を生成する関数
fn generate_kaibun_set(n: usize, sz: usize) -> BTreeSet<usize> {
    let mut st = BTreeSet::new();
    for i in 0..sz {
        let s = i.to_string();

        // 偶数桁の回文(文字列sと反転文字列sを繋げる)
        let even_kaibun = 
            format!("{}{}", 
                s, 
                s.chars().rev().collect::<String>()
            );
        if let Ok(value) = even_kaibun.parse::<usize>() {
            if value <= n {
                st.insert(value);
            }
        }

        // 奇数桁の回文(文字列sと先頭を削った反転文字列sを繋げる)
        let odd_kaibun = 
            format!("{}{}", 
                s, 
                s.chars().rev().skip(1).collect::<String>()
            );
        if let Ok(value) = odd_kaibun.parse::<usize>() {
            if value <= n {
                st.insert(value);
            }
        }
    }
    st
}

// A進数に変換する関数
fn convert_base_n(mut val: usize, base: usize) -> Vec<char> {
    let mut ret = Vec::new();
    while val > 0 {
        let mods = val % base;
        ret.push((mods + 0x30) as u8 as char);
        val /= base;
    }
    ret
}

// 回文判定を行う関数
fn iskaibun(s: &Vec<char>) -> bool {
    let sz = s.len();
    for i in 0..sz / 2 {
        if s[i] != s[sz - 1 - i] {
            return false;
        }
    }
    true
}

 D 問題問題
https://atcoder.jp/contests/abc414/tasks/abc414_d
解説
基地局から発信する電波強度の総和を最小化する問題です。
基地局が発信する地域を M 個のグループに分けることを考えます。棟と棟の間の区間は N-1 個ありますが、これを M 個のグループに分けるためには、M-1 個の区間を切り離す必要があります。

したがって、選択する区間は

\begin{aligned}
&(N-1) - (M-1) 
&= N-M
\end{aligned}
個となります。

このとき、電波強度の総和を最小化するには、棟間の距離が短い区間を優先的に選ぶのが最適です。具体的には、棟間の距離をを昇順にソートして、最も短い N-M 個の距離を合計すれば答えが得られます。
コード
abc414d.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 棟の数
        m: usize, // 基地局の数
        mut x: [usize; n], // 棟の座標
    }
    
    // 座標を昇順にする
    x.sort();

    // 棟間で離れている距離を求める
    let mut diff = Vec::new();
    for i in 0..n-1 {
        diff.push(x[i+1] - x[i]);
    }
    diff.sort();

    // 離れている距離が近い順にN-M個選んで、総和を求める
    let mut ans = 0;
    for i in 0..n-m {
        ans += diff[i];
    }

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

 E 問題問題
https://atcoder.jp/contests/abc414/tasks/abc414_e
解説
1以上 N 以下の整数について、以下の条件を満たす組 (a, b, c) の個数を数える問題です。条件は以下の通りです。

条件1. 1 \leq a, b, c \leq N

条件2. a, b, c は相異なる。

条件3. a \mod b = c
まず条件3より、a \mod b = c という関係から a = b \cdot s + c（ s は商）と表せます。また、このとき b > c が成り立ちます。

次に条件2より、a, b, c は相異なるため、s \geq 1 である必要があります。ここからさらに、a > b > c という関係が導かれます。

条件1より、余りが0のケース（c = 0）は除外する必要があります。
以上を踏まえると、以下1~2を行うことで答えが求まります。

a > b > c の条件を満たす (a, b) の全組み合わせを数えます。
1の全組み合わせの個数から、a \mod b = 0 となるケースを引きます。
ここで2の a \mod b = 0 となるケースを引く際、a = b \cdot s という反比例の関係から、b は \sqrt{N} まで列挙することで全て数え上げることが可能です。そのうえで、b の範囲を区間ごとに分けて処理し、該当する範囲の個数を引きます。
コード
abc414e.rs
use proconio::input;

// 定数
const MOD93: usize = 998244353;
const INV2: usize = 499122177;

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

    // b < aの組の総数を計算
    let mut ans = calc_pair_cnt(n);

    // b >= 2で、a % b = 0の個数を引く
    let mut from_b = 2;
    while from_b <= n {
        // (from_b ~ to_b] の間の個数と区間を求める
        let cnt = n / from_b;
        let to_b = n / cnt + 1;

        // 該当する範囲の個数を引く
        sub_range_cnt(from_b, to_b, cnt, &mut ans);

        from_b = to_b;
    }

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

// b < aの組の総数を計算
fn calc_pair_cnt(n: usize) -> usize {
    let ret = n % MOD93 * ((n - 1) % MOD93) % MOD93;
    ret * INV2 % MOD93
}

// 指定された範囲の個数を引く
fn sub_range_cnt(from: usize, to: usize, cnt: usize, ret: &mut usize) {
    let range = to - from;
    let subs = ((range % MOD93) * cnt) % MOD93;
    *ret = (*ret + MOD93 - subs) % MOD93;
}
A 問題

B 問題

C 問題

D 問題

E 問題

Discussion
