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

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

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

 ABC427-A問題
https://atcoder.jp/contests/abc427/tasks/abc427_a
文字列 S の中央の文字を削除する問題です。
解説
まず、文字列 S の長さを取得し、その中央の文字の位置を計算します。

中央の文字の位置は、文字列の長さを |S| としたとき、0-index で |S| / 2 番目に位置します。

この位置の文字を削除し、結果の文字列を出力します。
コード
abc427a.rs
use proconio::{input, marker::Chars};
use itertools::Itertools;

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

    // 中央の文字を削除
    let midpos = s.len() / 2;
    s.remove(midpos);

    // 削除後の文字列を出力
    println!("{}", s.iter().join(""));
}

 ABC427-B問題
https://atcoder.jp/contests/abc427/tasks/abc427_b
数列 A の N 項目を求める問題です。
解説
この問題では、数列 A の各項が以下のように定義されています。
初項は 1 です。
第2項は初項の値の桁和です。
第3項は初項の値の桁和と第2項の桁和の和です。
以降、N 項目は初項から N-1 項目までの桁和の総和となります。
各項については、初項から第 i-1 項までの各桁和を累積して求めます。

桁和の計算については、 calc_digit_sum() を用意し、与えられた数値を1桁ずつ分解してその和を計算します。
コード
abc427b.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 数列の項数
    }

    // 数列の初期化
    let mut a = vec![0; n + 1];
    a[0] = 1;

    // 2項目以降を計算
    for idx in 1..=n {
        // 自身より前の項の総和を求める
        let ret = calc_next_a(idx, &a);
        a[idx] = ret;
    }

    // N項目を出力
    println!("{}", a[n]);
}

// idx番目の項を計算する関数
fn calc_next_a(idx: usize, a: &Vec<usize>) -> usize {
    let mut ret = 0;
    for jdx in 0..idx {
        // 桁和を加算
        ret += calc_digit_sum(a[jdx]);
    }
    ret
}

// 桁和を計算する関数
fn calc_digit_sum(mut x: usize) -> usize {
    let mut ret = 0;
    while x > 0 {
        ret += x % 10;
        x /= 10;
    }
    ret
}

 ABC427-C問題
https://atcoder.jp/contests/abc427/tasks/abc427_c
与えられたグラフが二部グラフを満たすようにする際に、削除する辺の本数を最小化する問題です。
解説
二部グラフとは、頂点を2つのグループに分け、同じグループ内に辺が存在しないようにしたグラフのことです。

つまり、隣接する頂点同士が異なるグループに属している必要があります。

ここで二部グラフの決め方ですが、頂点数 N が最大10と小さいため、各頂点を「グループ0」または「グループ1」に割り振る全てのパターン（2^N 通り）を試すことが可能です。

各パターンについて、二部グラフの条件を満たすようにするために削除する必要がある辺の本数を計算し、その最小値を求めます。
コード
abc427c.rs
use proconio::{input, marker::Usize1};
use std::cmp::min;

fn main() {
    // 入力
    input! {
        n: usize, // 頂点数
        m: usize, // 辺の本数
    }

    // 無向グラフを作成
    let graph = make_graph(n, m);

    // 削除する辺の本数の最小値
    let mut ans = m;

    // 全ての二部グラフのパターンを全探索
    let state = 1 << n;
    for st in 0..state {
        // 各頂点の色を決定
        let color = decide_color(st, n);
        // 矛盾する辺の本数を計算
        let ret = calc_cut_edge(n, &graph, &color);
        // 最小値を更新
        ans = min(ans, ret);
    }
    // 答えを出力
    println!("{}", ans);
}

// グラフを作成する関数
fn make_graph(n: usize, m: usize) -> Vec<Vec<usize>> {
    let mut graph = vec![Vec::new(); n];
    for _ in 0..m {
        input! {
            u: Usize1, v: Usize1, // 辺の頂点u,v (0-index)
        }
        graph[u].push(v);
        graph[v].push(u);
    }
    graph
}

// ビット列から各頂点の色を決定する関数
fn decide_color(st: usize, n: usize) -> Vec<bool> {
    let mut color = vec![false; n];
    for bi in 0..n {
        if st & (1 << bi) != 0 {
            color[bi] = true;
        }
    }
    color
}

// 矛盾する辺の本数を計算する関数
fn calc_cut_edge(n: usize, graph: &Vec<Vec<usize>>, color: &Vec<bool>) -> usize {
    let mut ret = 0;
    for cpos in 0..n {
        for &npos in &graph[cpos] {
            // 辺を1回だけ調べるため、cpos > npos の場合はスキップ
            if cpos > npos {
                continue;
            }
            // 同じ色の頂点を結ぶ辺をカウント
            if color[cpos] == color[npos] {
                ret += 1;
            }
        }
    }
    ret
}

 ABC427-D問題
https://atcoder.jp/contests/abc427/tasks/abc427_d
AliceとBobの2人が交互にコマを動かし、どちらが勝つかを判定する問題です。
解説
この問題では、ゲームの最終状態から逆順に遡ることで、初期状態の勝敗を求めることができます。

具体的には、動的計画法（DP）を用いて、各状態における勝敗を計算します。
DPの状態と遷移は以下のように定義します。
状態

\text{dp[state]} = AliceまたはBobが操作を行うときのプレイヤーの勝敗(true : 勝ち / false : 負け)
遷移
次の状態のどれかで相手が負ける(自分が勝てる)場合、\text{dp[state] = true}
上記以外の場合は、\text{dp[state] = false}
初期状態はAliceが操作を行う場面のため、コマの初期配置 \text{dp[0]} がtrueならAliceの勝ち、falseならBobの勝ちとなります。
コード
abc427d.rs
use std::mem::swap;
use proconio::{input, marker::Chars, marker::Usize1};

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

fn solve() {
    input! {
        n: usize, // 頂点数
        m: usize, // 辺の本数
        k: usize, // 2人の各操作回数
        s: Chars, // 文字列AB
    }

    // 有向グラフを作る
    let graph = make_graph(n, m);

    // DPの初期化
    // DP[state] = プレイヤーの勝敗(true : 勝ち / false : 負け)
    // 最終状態はAliceの操作前なので、Aliceの勝敗で初期化。
    let mut cur_dp = vec![false; n];
    for i in 0..n {
        if s[i] == 'A' {
            cur_dp[i] = true;
        }
    }

    // 逆順(Bob,Aliceの順)に調べる。
    for _ in 0..2 * k {
        // 操作前の状態を全て調べる
        let mut back_dp = vec![false; n];
        for ppos in 0..n {
            // 操作後勝てる状態を見つける
            let mut ret = false;
            for &cpos in &graph[ppos] {
                if !cur_dp[cpos] {
                    ret = true;
                    break;
                }
            }
            // 操作前の状態の勝敗を記録
            back_dp[ppos] = ret;
        }
        swap(&mut cur_dp, &mut back_dp);
    }
    
    // 遡って調べた結果の初期状態の勝敗を出力
    println!("{}", if cur_dp[0] { "Alice" } else { "Bob" });
}

// グラフを作成する関数
fn make_graph(n: usize, m: usize) -> Vec<Vec<usize>> {
    let mut graph = vec![Vec::new(); n];
    for _ in 0..m {
        input! {
            u: Usize1, v: Usize1, // 辺の頂点u,v (0-index)
        }
        graph[u].push(v);
    }
    graph
}
ABC427-A

ABC427-B

ABC427-C

ABC427-D

Discussion
