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

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

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

 ABC426-A問題
https://atcoder.jp/contests/abc426/tasks/abc426_a
OSのバージョンがアップデート済みかを判定する問題です。
解説
この問題では、現在のOSバージョン X と対象バージョン Y を比較し、 Y が X のバージョンに対してアップデート済みかどうかを判定します。

この問題でのバージョンの関係性は以下の通りなので、このルールに従って判定します。

Ocelot は最も古いバージョンです。

Serval は Ocelot より新しいバージョンです。

Lynx は最も新しいバージョンです。
コード
abc426a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        x: String, // 現在のバージョン
        y: String, // 対象バージョン
    }

    // アップデート済みかどうかを判定
    let mut updated = false;

    if x == "Ocelot" {
        if y == "Ocelot" {
            updated = true;
        }
    }
    else if x == "Serval" {
        if y == "Ocelot" || y == "Serval" {
            updated = true;
        }
    }
    else {
        updated = true;
    }

    // 判定結果を出力
    println!("{}", if updated { "Yes" } else { "No" });
}

 ABC426-B問題
https://atcoder.jp/contests/abc426/tasks/abc426_b
1度だけ現れる英小文字を答える問題です。
解説
文字列 S を1文字ずつ確認し、各文字の出現回数を数えます。

この情報を連想配列（HashMap）に格納します。

連想配列を調べ、出現回数が1回の文字を見つけて出力します。
コード
abc426b.rs
use proconio::{input, marker::Chars};
use std::collections::HashMap;

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

    // 文字毎の出現回数を数える
    let mut mp = HashMap::new();
    for c in s {
        *mp.entry(c).or_insert(0) += 1;
    }

    // 1度だけ現れる文字を探す
    let mut ans = '?';
    for (&key, &val) in &mp {
        if val == 1 {
            ans = key;
            break;
        }
    }

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

 ABC426-C問題
https://atcoder.jp/contests/abc426/tasks/abc426_c
PCのバージョンアップを行う問題です。
解説
複数のバージョンをまとめると、それらは全て同じバージョンになり、以後はバラバラになることはありません。

また、バージョンアップは小さい順に見ていく必要があります。

上の2点の性質を踏まえて効率的に処理を行うため、順序付きの連想配列である（BTreeMap）を使用します。
このデータ構造を用いると、効率的にバージョン管理と更新を行うことができます。
コード
abc426c.rs
use proconio::input;
use std::collections::BTreeMap;

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

    // 各PCのバージョン値を管理するBTreeMap
    let mut bmp = BTreeMap::new();
    for i in 1..=n {
        *bmp.entry(i).or_insert(0) += 1;
    }

    // クエリ処理
    for _ in 0..q {
        input! {
            x: usize, // アップデート対象のバージョン
            y: usize, // アップデート後のバージョン
        }

        // x以下のものを全て取り出す
        let ans = take_update_machine(x, &mut bmp);
        
        // 取り出した個数を出力
        println!("{}", ans);

        // 取り出したものを全てyに変更してセットする
        *bmp.entry(y).or_insert(0) += ans;
    }
}

// 指定されたバージョン以下のPCを取り出し、その台数を返す関数
fn take_update_machine(x: usize, bmp: &mut BTreeMap<usize, usize>) -> usize {
    let mut ret = 0;
    while let Some((&version, &cnt)) = bmp.iter().next() {
        // xより大きいものしかないなら終了
        if version > x { break; }
        // 個数を加算
        ret += cnt;
        // 取り除く
        bmp.remove(&version);
    }
    ret
}

 ABC426-D問題
https://atcoder.jp/contests/abc426/tasks/abc426_d
01文字列について、端にある文字を選んで削除し、0または1のみの文字列にするための操作回数を最小化する問題です。
解説
文字列をすべて 0 に揃える場合とすべて 1 に揃える場合の2通りを考えます。

ここでは 0 に揃えるものとして説明します。

1 の文字を移動させる場合

0 に反転後、以後操作させない区間に退避させます。
この操作は1手です。


0 の文字を移動させる場合

1 に判定後、 0 に再反転させて以後操作させない区間に退避させます。
この操作は2手です。

この退避させる操作は、退避後は見る必要がないので、消すという操作に置き換えられます。

なので、両端から選んで削除する問題と考えることができます。

そのため、左からの削除コスト、右からの削除コストを累積和を事前に計算します。
次に、ランレングス圧縮を用いて、文字列内の 0 や 1 の連続する区間をまとめます。

上で調べた区間について、削除しない(操作させない) 0 の区間を全探索します。

この区間について、その時の左端から削除するコストと右端から削除するコストを足した操作コストの最小値を求めます。
1 を残す場合の最小コストについても同様に計算し、操作コストがより小さいものを答えます。
コード
abc426d.rs
use proconio::{input, marker::Chars};
use std::cmp::min;

const INF: usize = 1 << 60;

fn main() {
    // クエリ数の入力
    input! {
        t: usize,
    }
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    // 入力
    input! {
        n: usize, // 文字列の長さ
        mut s: Chars, // 01文字列
    }

    let mut ans = INF;

    // 0で揃える
    for _ in 0..2 {
        // 左から削除する個数に対するコストの累積和
        let lacc = calc_acc(n, &s);
        // 右から削除する個数に対するコストの累積和
        let racc = calc_racc(n, &s);
        // ランレングス圧縮で0と1の固まりをまとめる
        let rung = runlen(&s);

        // 左から削除する個数(開始位置)
        let mut lcnt = 0;
        
        // 選択する0と1の固まりを調べる
        for &(c, val) in &rung {
            // 0を残す場合はチェックする
            if c == '0' { 
                // 右から削除する個数
                let rcnt = n - lcnt - val;
                
                // 操作コストの最小値を更新
                let lcost = lacc[lcnt];
                let rcost = racc[rcnt];
                ans = min(ans, lcost + rcost);
            }   
                    
            // 開始位置をずらす
            lcnt += val;
        }

        // 0と1を入れ替え
        change_01(n, &mut s);
    }

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

fn calc_acc(n: usize, s: &Vec<char>) -> Vec<usize> {
    let mut acc = vec![0; n+1];
    for i in 0..n {
        acc[i+1] = acc[i];
        if s[i] == '0' { acc[i+1] += 2;}
        else { acc[i+1] += 1;}
    }
    acc
}

fn calc_racc(n: usize, s: &Vec<char>) -> Vec<usize> {
    let mut acc = vec![0; n+1];
    for i in 0..n {
        acc[i+1] = acc[i];
        if s[n-1-i] == '0' { acc[i+1] += 2;}
        else { acc[i+1] += 1;}
    }
    acc
}

fn change_01(n: usize, s: &mut Vec<char>) {
    for i in 0..n {
        if s[i] == '0'{ 
            s[i] = '1'; 
        }
        else { 
            s[i] = '0'; 
        }
    }
}

// ランレングス圧縮
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
}
ABC426-A

ABC426-B

ABC426-C

ABC426-D

Discussion
