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

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

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

 ABC423-A問題
https://atcoder.jp/contests/abc423/tasks/abc423_a
銀行に預けている残高から引き下ろすことができる最大金額を求める問題です。
解説
1回の引き出しで1000円を引き出すことができ、その際に手数料として C 円が発生します。

そのため、残高 X を (1000 + C) で整数除算することで、引き出し可能な回数が求められます。

引き出し可能な回数に1000円を掛けた値が、引き出し可能な最大金額となります。
コード
abc423a.rs
use proconio::input;
const UNIT : usize = 1000;

fn main() {
    // 入力
    input! {
        x: usize, // 残高
        c: usize, // 手数料
    }

    // 引き出し回数
    let cnt = x / (UNIT + c);

    // 引き出し金額を出力
    println!("{}", cnt * UNIT);
}

 ABC423-B問題
https://atcoder.jp/contests/abc423/tasks/abc423_b
両端にいる2人が隣の部屋へ行き来する際に、どちらの人も行き来できない部屋の数を求める問題です。
解説
部屋を頂点、ドアを辺とするグラフとして考えることができます。

ドアが開いている場合、その部屋間は双方向に行き来可能です。

幅優先探索（BFS）を使い、左端（部屋0）と右端（部屋 N ）の両方から到達可能な部屋を探索します。

探索後、到達できなかった部屋の数を数えることで、答えを求めることができます。
コード
abc423b.rs
use std::collections::VecDeque;
use proconio::input;

#[derive(Clone)]
struct MoveInfo {
    left: bool,
    right: bool,
}

fn main() {
    // 入力
    input! {
        n: usize, // ドアの数
        l: [usize; n], // ドアの開閉状態
    }

    // 各部屋の行き来の無向グラフ
    let graph = make_graph(n, &l);

    // BFSで到達可能な部屋を探索
    let reached = bfs(n, &graph);

    // 到達していない部屋数を出力
    let mut ans = 0;
    for i in 0..=n {
        if !reached[i] {
            ans += 1;
        }
    }
    println!("{}", ans);
}

// グラフを構築する関数
fn make_graph(n: usize, l: &Vec<usize>) -> Vec<MoveInfo> {
    let mut graph = vec![MoveInfo { left: false, right: false }; n + 1];
    for i in 0..n {
        // ドアが開いている場合は行き来可能
        if l[i] == 0 {
            graph[i].right = true;
            graph[i + 1].left = true;
        }
    }
    graph
}

// BFSで到達可能な部屋を探索する関数
fn bfs(n: usize, graph: &Vec<MoveInfo>) -> Vec<bool> {
    let mut reached = vec![false; n + 1];
    reached[0] = true; // 左端の部屋
    reached[n] = true; // 右端の部屋
    let mut dq = VecDeque::new();
    dq.push_back(0);
    dq.push_back(n);

    while let Some(cur) = dq.pop_front() {
        // 右方向に移動可能で、到達していない部屋の場合
        if graph[cur].right && !reached[cur + 1] {
            reached[cur + 1] = true;
            dq.push_back(cur + 1);
        }
        // 左方向に移動可能で、到達していない部屋の場合
        if graph[cur].left && !reached[cur - 1] {
            reached[cur - 1] = true;
            dq.push_back(cur - 1);
        }
    }
    reached
}

 ABC423-C問題
https://atcoder.jp/contests/abc423/tasks/abc423_c
すべてのドアを施錠するのに必要なドアの開閉回数を最小化する問題です。
解説
ドアの開閉回数を最小化するには、以下1~3の手順で処理します。
右側の処理
現在位置から最も右側にある開いているドアの部屋まで移動します。
ドアが開いている場合は帰りに施錠を1回行い、閉まっている場合は解錠と施錠の2回を行います。
この移動で必要な開閉回数を計算します。
左側の処理
部屋の位置とドアの開閉状態を反転させて、同様に左側の処理を行います。
合計
右側と左側の処理で得られた開閉回数を合計します。
コード
abc423c.rs
use proconio::input;

#[derive(Clone)]
struct MoveInfo {
    left: bool,
    right: bool,
}

fn main() {
    // 入力
    input! {
        n: usize, // ドアの数
        mut r: usize, // 現在の部屋の位置 (0-index)
        mut l: [usize; n], // ドアの開閉状態 (0: 開いている, 1: 閉まっている)
    }

    // ドアの開閉回数
    let mut cnt = 0;

    for _ in 0..2 {
        // 各部屋の行き来の無向グラフ
        let graph = make_graph(n, &l);
        // 最も右にある開いている部屋を探す
        let rpos = simulate_rpos(r, n, &graph);
        // 現在位置から右側に進んだ時の開閉回数
        cnt += calc_rock_right_cnt(r, rpos, &graph);

        // 位置とドア情報を反転して、左側を見る
        r = n - r;
        l.reverse();
    }

    // 開閉回数を出力
    println!("{}", cnt);
}

// グラフを構築する関数
fn make_graph(n: usize, l: &Vec<usize>) -> Vec<MoveInfo> {
    let mut graph = vec![MoveInfo { left: false, right: false }; n + 1];
    for i in 0..n {
        // ドアが開いている場合は行き来可能
        if l[i] == 0 {
            graph[i].right = true;
            graph[i + 1].left = true;
        }
    }
    graph
}

// 最も右側にある開いている部屋を探す関数
fn simulate_rpos(spos: usize, epos: usize, graph: &Vec<MoveInfo>) -> usize {
    let mut ret_pos = spos; // 最も右側にあるドアが空いている部屋
    let mut cpos = spos; // 現在の部屋
   
    // 右方向に進めるだけ進む
    while cpos < epos {
        if graph[cpos].right {
            ret_pos = cpos + 1; // ドアが空いていたら更新
        }
        cpos += 1;
    }
    ret_pos
}

// 現在位置から最も右の部屋までの往復の開閉回数を計算する関数
fn calc_rock_right_cnt(spos: usize, epos: usize, graph: &Vec<MoveInfo>) -> usize {
    let mut cnt = 0; // 開閉回数
    let mut cpos = spos; // 現在の部屋
    
    // 右方向に進めるだけ進む
    while cpos < epos {
        if graph[cpos].right {
            cnt += 1; // ドアが空いていたら帰りに施錠
        } else {
            cnt += 2; // ドアが閉まっていたら行きと帰りに施錠
        }
        cpos += 1;
    }
    cnt
}

 ABC423-D問題
https://atcoder.jp/contests/abc423/tasks/abc423_d
各団体客の入店時刻を求める問題です。
解説
各団体客を以下の1~3の手順で処理します。
団体客が入店可能な場合、そのまま入店させます。
団体客が入店できない場合、退店時刻が早い順に団体客を追い出して、入店可能な状態を作ります。
入店時刻を記録し、次の団体客に進みます。
退店時刻と団体客の人数は優先度付きキュー（BinaryHeap）を用いると、退店時刻が早い順に取り出せるようにします。
コード
abc423d.rs
use std::collections::BinaryHeap;
use std::cmp::{max, Reverse};
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 団体数
        k: i64,   // 定員
        abc: [(i64, i64, i64); n], // 各団体(最短入店時刻, 滞在時間, 人数)
    }

    let mut ans = Vec::new();

    // 現在の到達時刻
    let mut cur_time = 0;
    // 現在の滞在人数
    let mut cur_people = 0;
    // 退店時刻のキュー (退店時刻, 人数)
    let mut out_queue = BinaryHeap::new();
    
    // 各団体客を順番に処理する
    for &(fastest_time, stay_time, in_people) in &abc {
        // 現在の時刻を更新
        cur_time = max(cur_time, fastest_time);

        // 入店できない場合、退店処理を行う
        while cur_people + in_people > k {
            proceed_leave(&mut out_queue, &mut cur_time, &mut cur_people);
        }

        // 入店処理
        ans.push(cur_time);
        proceed_enter(&mut out_queue, cur_time, in_people, stay_time, &mut cur_people);
    }

    // 各団体の入店時刻を出力
    for &time in &ans {
        println!("{}", time);
    }
}

// 退店処理
fn proceed_leave(
    out_queue: &mut BinaryHeap<Reverse<(i64, i64)>>,
    cur_time: &mut i64,
    cur_people: &mut i64,
) {
    assert!(!out_queue.is_empty());
    let Reverse((out_time, out_people)) = out_queue.pop().unwrap();

    // 退店時に時刻と滞在人数を更新
    *cur_time = max(*cur_time, out_time);
    *cur_people -= out_people;
}

// 入店処理
fn proceed_enter(
    out_queue: &mut BinaryHeap<Reverse<(i64, i64)>>,
    cur_time: i64,
    in_people: i64,
    stay_time: i64,
    cur_people: &mut i64,
) {
    // 入店時に滞在人数を更新
    *cur_people += in_people;
    // 退店時刻をキューに追加
    out_queue.push(Reverse((cur_time + stay_time, in_people)));
}
ABC423-A

ABC423-B

ABC423-C

ABC423-D

Discussion
