👨‍🍳
緑コーダーがRustで解説してみた(ABC433 A～E)

2025/11/24に公開
AtCoder Beginner Contest 433のA～E問題を緑コーダーが自分なりの解説と解答コードをまとめました。

参考になりましたら幸いです。

 ABC433-A問題
https://atcoder.jp/contests/abc433/tasks/abc433_a
高橋君の年齢が青木君の年齢のちょうど Z 倍となるタイミングがあるかを判定する問題です。
解説
未来のある時点で、高橋君の年齢 x + i が青木君の年齢 y + i の Z 倍に一致するかを調べます。

具体的には、加算する年数 i を 0 から 100 までの範囲で試し、以下の条件を満たすかを確認します。
(y + i) \times Z = x + i
この条件を満たす i が存在すれば Yes を出力し、存在しなければ No を出力します。
コード
abc433a.rs
use proconio::input;

fn main() {
    input! {
        x: usize, // 高橋君の現在の年齢
        y: usize, // 青木君の現在の年齢
        z: usize, // 倍数
    }

    // 0年後から100年後まで調べる
    for i in 0..=100 {
        // 条件を満たすか確認
        if (y + i) * z == (x + i) {
            println!("Yes");
            return;
        }
    }

    // 条件を満たす年数が見つからなかった場合
    println!("No");
}

 ABC433-B問題
https://atcoder.jp/contests/abc433/tasks/abc433_b
N 人の人について、自身より前にいる身長の高い人の位置を答える問題です。
解説
1番目にいる人を先頭として、各人について自分より前にいる人を順番に調べます。

自分より身長が高い人が見つかった場合、その人の位置を出力し、見つからなかった場合は、-1 を出力します。
コード
abc433b.rs
use proconio::input;
const INF: usize = 1 << 60;

fn main() {
    input! {
        n: usize, // 人数
        a: [usize; n], // 各人の身長
    }

    // 各人について調べる
    for i in 0..n {
        // 前にいる人を調べて、自身より身長が高い人の位置を答える
        let idx = find_large_person(i, &a);
        if idx == INF {
            println!("-1");
        } else {
            println!("{}", idx + 1); // 1-indexedで出力
        }
    }
}

fn find_large_person(cur: usize, a: &Vec<usize>) -> usize {
    for i in (0..cur).rev() {
        if a[cur] < a[i] {
            return i;
        }
    }
    INF
}

 ABC433-C問題
https://atcoder.jp/contests/abc433/tasks/abc433_c
文字列 S から連続部分文字列を作る際に作ることができる 1122文字列 の個数を答える問題です。

1122文字列 とは、以下の条件を満たす文字列のことを指します。
連続部分文字列の長さを 2T としたとき、
前半の 1～T 文字目が同じ数字
後半の T+1～2T 文字目が同じ数字
前半の数字に+1した値が、後半の数字と一致する

解説
ランレングス圧縮を用いて、文字列を同じ文字が連続する部分ごとにまとめます。

例えば、文字列 1112233 は [(1, 3), (2, 2), (3, 2)] という形式に変換されます。

次にランレングス圧縮後の結果を使い、1122文字列 の条件を満たしているかを調べます。

条件を満たす場合は、2つの固まりのうち、長さが短い方の個数だけ 1122文字列 を作ることができます。

条件を満たすペアごとに作れる個数を加算し、最終的な答えを出力します。
コード
abc433c.rs
use proconio::{input, marker::Chars};
use std::cmp::min;

fn main() {
    input! {
        s: Chars, // 入力文字列
    }

    // ランレングス圧縮して、(値, 個数)のペアにする
    let rungs = runlen(&s);
    let sz = rungs.len();

    // 作れる1122文字列の個数
    let mut ans = 0;
    
    // 隣接する2種類の文字を調べる
    for i in 0..sz-1 {
        // 2種類の文字(s,t)について、s+1==tかをチェック
        if !check_conditions(rungs[i].0, rungs[i+1].0) { 
            continue;
        }
        // 個数の少ない方を加算
        let cnt = min(rungs[i].1, rungs[i+1].1);
        ans += cnt;
    }

    // 作れる個数の合計を出力
    println!("{}", ans);
}

// 条件を満たすかをチェックする関数
fn check_conditions(s: char, t: char) -> bool {
    let val1 = s as u8 as usize;
    let val2 = t as u8 as usize;
    val1 + 1 == val2
}

// ランレングス圧縮
pub fn runlen(arr: &Vec<char>) -> Vec<(char, usize)> {
    let len = arr.len();
    let mut arr_ret = Vec::new();
    let mut tail = 0;
    let mut top = 0;
    while tail < len {
        let cur = arr[tail];
        while top < len && cur == arr[top] {
            top += 1;
        }
        arr_ret.push((cur, top - tail));
        tail = top;
    }
    arr_ret
}

 ABC433-D問題
https://atcoder.jp/contests/abc433/tasks/abc433_d
数列 A について、値を2個（同じものも含む）選んで連結した値が M の倍数となる個数を求める問題です。
解説
数列 A の i 番目の値 A_i と j 番目の値 A_j を連結した値は、以下の式で表されます。 (k は A_j の桁数です。)

\begin{aligned}
A_i \times 10^k + A_j
\end{aligned}
また、この値が M の倍数であるためには、以下の条件を満たす必要があります。

\begin{aligned}
(A_i \times 10^k + A_j) \mod M &= 0 \\
(A_i \times 10^k) \mod M &= -A_j \mod M \\
&= (M-A_j) \mod M
\end{aligned}
よって、左辺の値について、数列 A の k（桁数）と A_i（数列の値）を全探索し、右辺について、条件を満たすペアの個数を数え上げることで解くことができます。
コード
abc433d.rs
use std::collections::HashMap;
use proconio::input;
const SZ: usize = 10;

fn main() {
    input! {
        n: usize, // 数列の長さ
        m: usize, // 倍数
        a: [usize; n], // 数列の値
    }

    // 数列aについて、桁数ごとに値(mod M)を管理
    let vec_mp = get_vec_mp(&a, m);
    // 10^iを事前計算
    let power10 = get_power10(SZ);
   
    // 条件を満たすペアの個数
    let mut ans = 0;
    
    // 桁数kを全探索
    for k in 0..=SZ {
        // 数列aの値を全探索
        for &ai in &a {
            // 左辺のmodを計算
            let left = (ai * power10[k]) % m;
            
            // 右辺のmodを計算
            let right = if left == 0 { 0 } else { m - left };
            if let Some(cnt) = vec_mp[k].get(&right) {
                ans += cnt;
            }
        }
    }
    // 答えを出力
    println!("{}", ans);
}

// 数列aを桁数ごとに分類し、mod Mの値を管理
fn get_vec_mp(a: &Vec<usize>, m: usize) -> Vec<HashMap<usize, usize>> {
    let mut vec_mp = vec![HashMap::new(); SZ + 1];
    for &aa in a {
        let digit = format!("{aa}").len();
        let value = aa % m;
        *vec_mp[digit].entry(value).or_insert(0) += 1;
    }
    vec_mp
}

// 10^iを事前計算
fn get_power10(sz: usize) -> Vec<usize> {
    let mut ret = vec![0; sz + 1];
    ret[0] = 1;
    for i in 0..sz {
        ret[i + 1] = ret[i] * 10;
    }
    ret
}

 ABC433-E問題
https://atcoder.jp/contests/abc433/tasks/abc433_e
N \times M の行列に 1 から N \times M までの番号を1つずつ配置し、各行と各列の最大値が指定された条件を満たすかどうかを判定する問題です。
解説
各行と各列の最大値が決まっているため、値が大きい順に配置していくのが効率的です。

これにより、条件を満たす配置を効率よく探索できます。
値を配置する際には以下1.~3.のいずれかのルールを適用していきます。
配置する値が行と列の両方の最大値と一致する場合、そのマスに配置します。
配置する値が行または列のどちらか一方の最大値と一致する場合、その行または列の中から適切なマスを選んで配置します。
配置する値が行と列のどちらの最大値とも一致しない場合、値以下の行と列から適切なマスを選んで配置します。
ルール3での値以下の行と列を見つけやすくするために、各行と各列の最大値を降順にソートしておき、全て配置した後に元の並び順に戻します。
全てのマスに値を配置できた場合は Yes を出力し、その配置を出力します。

配置できなかった場合は No を出力します。
コード
abc433e.rs
use proconio::input;
use std::collections::{BTreeMap, BTreeSet};
use itertools::Itertools;

fn main() {
    input! {
        t: usize, // テストケース数
    }
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    input! {
        n: usize, m: usize, // 行と列の数
        mut x: [usize; n], // 各行の最大値
        mut y: [usize; m], // 各列の最大値
    }
    
    // 同じ行または列に同じ最大値が複数ある場合は不可
    if is_duplicate(&x) || is_duplicate(&y) {
        println!("No");
        return;
    }

    // 元の並びを記憶
    let mut memo_row = MemorizeIndex::new(&x);
    let mut memo_col = MemorizeIndex::new(&y);

    // 降順にソート
    x.sort_by(|i, j| j.cmp(i)); 
    y.sort_by(|i, j| j.cmp(i));

    // 配置を実施
    let mut ret = vec![vec![0; m]; n];
    if !execute_set(n, m, &x, &y, &mut ret) {
        println!("No");
        return;
    }

    // 元の並び順に戻す
    let ans = relocate(n, m, &x, &y, &mut memo_row, &mut memo_col, &ret);

    // 結果を出力
    println!("Yes");
    for i in 0..n {
        println!("{}", ans[i].iter().join(" "));
    }
}

fn is_duplicate(vec: &Vec<usize>) -> bool {
    let st: BTreeSet<usize> = BTreeSet::from_iter(vec.clone());
    st.len() != vec.len()
}

fn execute_set(n: usize, m: usize, x: &Vec<usize>, y: &Vec<usize>, ans: &mut Vec<Vec<usize>>) -> bool {
    let mut cnt_row = 0; // 選択済みの行数
    let mut cnt_col = 0; // 選択済みの列数
    
    // 候補のスタック
    let mut stack = Vec::new();

    // 値の大きい順に配置
    for val in (1..=n*m).rev() {
        // 新たな行を選択する場合
        if cnt_row < n && x[cnt_row] == val {
            for idx in 0..cnt_col {
                stack.push((cnt_row, idx));
            }
            cnt_row += 1;
        }
        // 新たな列を選択する場合
        if cnt_col < m && y[cnt_col] == val {
            for idx in 0..cnt_row {
                stack.push((idx, cnt_col));
            }
            cnt_col += 1;
        }
        
        // スタックが空の場合は配置不可
        if stack.is_empty() {
            return false;
        }
        // スタックから座標を取り出して配置
        if let Some((r, c)) = stack.pop() {
            ans[r][c] = val;
        }
    }

    true
}

fn relocate(
    n: usize, m: usize, x: &Vec<usize>, y: &Vec<usize>,
    memo_row: &mut MemorizeIndex, memo_col: &mut MemorizeIndex,
    ret: &Vec<Vec<usize>>
) -> Vec<Vec<usize>> {
    let mut ans = vec![vec![0; m]; n];
    for i in 0..n {
        for j in 0..m {
            // 元のインデックスを取得
            let r = memo_row.get_idx_bykey(x[i]);
            let c = memo_col.get_idx_bykey(y[j]);
            ans[r][c] = ret[i][j];
        }
    }
    ans
}

#[allow(unused)]
struct MemorizeIndex {
    bmp: BTreeMap<usize, usize>, // bmp[key] = idx
    sz: usize
}
impl MemorizeIndex {
    // 初期化
    pub fn new(v: &Vec<usize>) -> Self {
        let mut bmp = BTreeMap::new();
        let mut sz = 0;
        for &item in v {
            bmp.insert(item, sz);
            sz += 1;
        }
        MemorizeIndex { bmp, sz }
    }

    #[allow(unused)]
    pub fn get_idx_bykey(&mut self, key: usize) -> usize {
        match self.bmp.get(&key) {
            Some(&idx) => idx,
            None => INVALID_VALUE,
        }
    }
}

// 値が見つからなかった場合の定数
const INVALID_VALUE: usize = 1 << 60;
ABC433-A

ABC433-B

ABC433-C

ABC433-D

ABC433-E

Discussion
