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

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

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

 ABC421-A問題
https://atcoder.jp/contests/abc421/tasks/abc421_a
N 部屋あるマンションの宛先の名前が正しいかどうかを判定する問題です。
解説
与えられた名前リストの中で、指定された部屋番号 X の名前が、与えられた名前 Y と一致しているかを判定します。

一致していれば Yes を、一致していなければ No を出力します。
コード
abc421a.rs
use proconio::{input, marker::Usize1};

fn main() {
    // 入力
    input! {
        n: usize, // 部屋の数
        s: [String; n], // 名前リスト
    }

    input! {
        x: Usize1, // 部屋の番号(0-index)
        y: String // 名前
    }

    // 名前リストのx番目が名前yと一致しているかを判定
    println!("{}", if s[x] == y { "Yes" } else { "No" });
}

 ABC421-B問題
https://atcoder.jp/contests/abc421/tasks/abc421_b
数列の10項目を求める問題です。
解説
この問題では、以下のような数列が与えられます。
f(1) = X
f(2) = Y

f(i) = g(f(i-1) + f(i-2)) （※）

(※ gは数値を反転させる関数で、例えば g(123) = 321 となります。)
最初の2項目（f(1) と f(2)）を入力として受け取り、3項目以降を順次計算していきます。各項は、直前の2項を足し、その結果を反転させることで求められます。

数値の反転を行う際には、数値を文字列に変換し、文字列を反転させてから再び数値に戻すという手法を用います。
コード
abc421b.rs
use proconio::input;

const SZ: usize = 10;

fn main() {
    // 入力
    input! {
        x: usize, // 1項目の値
        y: usize, // 2項目の値
    }

    // 求める数列の初期化
    let mut num_seq = vec![0; SZ];
    num_seq[0] = x;
    num_seq[1] = y;
    
    // 数列を10項目まで計算
    for i in 2..SZ {
        // 前の2項を足して、計算結果を反転させた値を求める
        let val = calc_value(num_seq[i - 1], num_seq[i - 2]);
        num_seq[i] = val;
    }

    // 10項目を出力
    println!("{}", num_seq[SZ - 1]);
}

// 2つの値を足して反転させる関数
fn calc_value(bef1: usize, bef2: usize) -> usize {
    // 2項を足す
    let val = bef1 + bef2;

    // 計算結果を反転させる(値をchar配列に直して反転してから、値に戻す)
    let str_val = val.to_string();
    let mut char_val: Vec<char> = str_val.chars().collect();
    char_val.reverse();
    let rstr_val: String = char_val.iter().collect();
    let r_val = rstr_val.parse().unwrap();

    // 計算結果を返す
    r_val
}

 ABC421-C問題
https://atcoder.jp/contests/abc421/tasks/abc421_c
A と B の文字列について、隣り合う2つの文字を入れ替えて A と B が交互に並ぶ状態にするために必要な手数を最小化する問題です。
解説
A と B が交互に並ぶ状態は、以下の2通りがあります。

A が先頭に来る場合（例: ABAB... ）

B が先頭に来る場合（例: BABA... ）
この2通りをそれぞれ試して、必要な手数を計算し、最小値を求めます。

A を適切に並べると B も正しく並ぶため、A の位置に注目して考えます。 A を並べる際、順番を変えずに並べるのが最適です。

具体的には、A の現在の位置と、目標とする位置のずれを計算し、その距離の総和を求めます。
コード
abc421c.rs
use proconio::{input, marker::Chars};
use std::cmp::min;

fn main() {
    // 入力
    input! {
        n: usize, // A, Bの各文字の個数
        s: Chars, // AB文字列
    }

    // Aの位置を記録
    let mut pos_a = Vec::new();
    for i in 0..2 * n {
        if s[i] == 'A' {
            pos_a.push(i);
        }
    }

    // Aが先頭に来る並べ方の最短手数
    let mut pattern_a = 0;
    for i in 0..n {
        pattern_a += pos_a[i].abs_diff(2 * i);
    }

    // Bが先頭に来る並べ方の最短手数
    let mut pattern_b = 0;
    for i in 0..n {
        pattern_b += pos_a[i].abs_diff(2 * i + 1);
    }

    // 2つのパターンのうち、最短の手数を答える
    println!("{}", min(pattern_a, pattern_b));
}

 ABC421-D問題
https://atcoder.jp/contests/abc421/tasks/abc421_d
二人が同時に移動するときに、同じマスに重なる回数を求めるという問題です。
解説
二人が移動する際、向きが変わるタイミングで相対的な位置関係が変化します。そのため、向きが変わる時刻をイベントとして管理し、シミュレーションを行います。
二人が同じマスに重なる状況は以下の2つです。
すれ違う場合

二人が異なる方向に動いてすれ違う場合、1度だけ同じマスに重なります。

この場合、重なる可能性がある時刻を計算し、その時に同じマスにいるかを確認します。
同じ方向に移動する場合

二人が同じマスにいて、そこから同じ方向に移動し続ける場合、その移動時間分だけ重なります。
二人の位置関係を相対座標で管理します。高橋君を基準とした青木君の相対座標を計算し、相対座標が (0, 0) になるタイミングを探します。

向きが変わるタイミングをイベントキューで管理し、時刻を進めながら相対座標を更新していきます。
コード
abc421d.rs
use proconio::input;
use std::collections::{VecDeque, BinaryHeap};
use std::cmp::Reverse;
const JUST : Pos = Pos{r: 0, c:0};

// 座標
#[derive(Clone, PartialEq)]
struct Pos {
    r: i64,
    c: i64,
}

// 向きを変える行動
#[derive(Clone)]
struct Action {
    time: i64, // 時刻
    dir: char, // 変更する向き
}

fn main() {
    input! {
        rc_t: (i64, i64), // 高橋君の座標
        rc_a: (i64, i64), // 青木君の座標
        _n: i64, // 各人の移動手数
        m: i64, // 高橋君が向きを決める回数
        l: i64, // 青木君が向きを決める回数
        sa: [(char, i64); m], // 高橋君の向きごとの移動
        tb: [(char, i64); l], // 青木君の向きごとの移動
    }

    // 高橋君から見た青木君の相対座標を計算
    let mut relative_pos = Pos {r: rc_a.0 - rc_t.0, c: rc_a.1 - rc_t.1};

    // 向きの変化が起きる時刻イベントキュー
    let mut event = BinaryHeap::new();

    // 高橋君と青木君の向き変更イベントキュー
    let mut dq_t = VecDeque::new();
    let mut dq_a = VecDeque::new();
    
    // キューの初期化
    set_queue(m, &sa, &mut event, &mut dq_t);
    set_queue(l, &tb, &mut event, &mut dq_a);

    // 現在時刻
    let mut cur_time = 0;

    // 高橋君と青木君の現在の向き
    let mut dir_t = sa[0].0;
    let mut dir_a = tb[0].0;

    // 座標が重なった回数
    let mut ans = 0;

    // 時刻イベントキューを順番に処理
    while let Some(Reverse(next_time)) = event.pop() {
        // 時刻が重複しているイベントはスキップ
        if cur_time == next_time { continue; }

        // 高橋君と青木君の向きを更新
        update_direction(cur_time, &mut dir_t, &mut dq_t);
        update_direction(cur_time, &mut dir_a, &mut dq_a);

        // 移動時間
        let move_time = next_time - cur_time;

        // 時刻1あたりの相対座標の変化量を計算
        let changes = calc_amount_of_changes(dir_t, dir_a);

        // 相対座標が異なる場合
        if relative_pos != JUST {
            // 2人が出会う時間を計算
            let meet_time = (relative_pos.r.abs() + relative_pos.c.abs()) / 2;
            if meet_time <= move_time {
                let meet_pos = Pos{
                    r: relative_pos.r + changes.r * meet_time, 
                    c: relative_pos.c + changes.c * meet_time
                };
                // 出会う時間に相対座標が0になる場合
                if meet_pos == JUST { 
                    ans += 1;
                }
            }
        }
        // 相対座標が0の場合
        else {
            // 同じ方向に移動している場合
            if changes == JUST {
                ans += move_time;
            }    
        }

        // 相対座標と時刻を更新
        relative_pos.r += changes.r * move_time;
        relative_pos.c += changes.c * move_time;
        cur_time = next_time;
    }

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

fn set_queue(
    dir_cnt: i64, // 向きを決める回数
    dt: &Vec<(char, i64)>, // 向きごとの移動
    event: &mut BinaryHeap<Reverse<i64>>, // 時刻イベントキュー
    dq: &mut VecDeque<Action>) { // 向き変更イベントキュー

    let mut total_time = 0;
    for i in 0..dir_cnt as usize {
        total_time += dt[i].1;
        dq.push_back(Action{time: total_time, dir: dt[i].0});
        event.push(Reverse(total_time));
    }
}

fn update_direction(
    cur_time: i64, // 現在時刻
    cur_dir: &mut char, // 現在の向き
    dq: &mut VecDeque<Action> // 向き変更イベントキュー
) {
    // キューから現在時刻より先のイベントの向きを取得
    while let Some(event) = dq.front() {
        if event.time <= cur_time {
            dq.pop_front();
            continue;
        }
        *cur_dir = event.dir;
        break;
    }
}

fn calc_amount_of_changes(t: char, a: char) -> Pos {
    let mut changes = Pos{r: 0, c: 0};
    
    // 青木君の移動
    if a == 'D' {changes.r += 1; } 
    else if a == 'U' {changes.r -= 1; }
    else if a == 'R' {changes.c += 1; }
    else { changes.c -= 1; }
    
    // 高橋君の移動
    if t == 'U' {changes.r += 1; } 
    else if t == 'D' {changes.r -= 1; }
    else if t == 'L' {changes.c += 1; }
    else { changes.c -= 1; }

    changes
}
ABC421-A

ABC421-B

ABC421-C

ABC421-D

Discussion
