👨‍🍳
ABC411: Rustで解く！問題解説

2025/06/22に公開
AtCoder Beginner Contest 411のA-D問題をRustで解いた際の解法をまとめました。

 A 問題問題
https://atcoder.jp/contests/abc411/tasks/abc411_a
解説
入力で与えられた文字列 P の長さが L 以上かどうかを判定する問題です。
文字列 P の長さを len 関数で取得し、その値が L 以上であれば Yes を出力し、そうでなければ No を出力します。
コード
abc411a.rs
use proconio::{input, marker::Chars};
fn main() {
    // 入力
    input! {
        p: Chars, // 入力文字
        l: usize, // 必要な文字列の長さ
    }

    // 長さl以上ならYes、そうでないならNo
    println!("{}", if p.len() >= l {"Yes"} else {"No"});
}

 B 問題問題
https://atcoder.jp/contests/abc411/tasks/abc411_b
解説
N 個の駅について、各駅間の距離を出力する問題です。
駅1を座標0とし、各駅の座標を計算します。その後、駅 i から駅 j (i < j) への距離を計算して出力します。
コード
abc411b.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 駅の数
        d: [usize; n-1], // 各駅間の距離
    }

    // 各駅の座標を計算
    let mut pos = vec![0; n];
    for i in 0..n-1 {
        pos[i + 1] = pos[i] + d[i];
    }

    // 駅iから駅jへの距離を出力
    for i in 0..n-1 {
        for j in i+1..n {
            print!("{} ", pos[j] - pos[i]);
        }
        println!();
    }
}

 C 問題問題
https://atcoder.jp/contests/abc411/tasks/abc411_c
解説
N 個のマスについて、白と黒の状態があり色を交互に変化させた際の黒の区間の個数を答える問題です。

クエリで指定されたマスの色を反転させた際に、黒の区間の個数がどのように変化するかを求めます。黒の区間の増減は、選択したマスとその両隣のマスの状態に依存し、以下3つのパターンが考えられます。
白白白 または 黒黒黒の場合

選択したマスが両隣と同じ色の場合、黒の区間が1つ増加します。
黒白黒 または 白黒白の場合

選択したマスが両隣と異なる色の場合、黒の区間が1つ減少します。
その他の場合

黒の区間の増減はありません。
各クエリについて、選択したマスとその両隣の状態を確認し、黒の区間の増減を計算します。その後、選択したマスの色を反転させ、更新後の黒の区間の個数を出力します。
コード
abc411c.rs
use proconio::input;

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

    // マスの情報を初期化 (false: 白, true: 黒。両端を追加)
    let mut grid = vec![false; n + 2];

    // 黒の区間の個数
    let mut cnt = 0;

    // 各クエリ
    for _ in 0..q {
        input! {
            a: usize, // 操作対象のマス
        }

        // 現在のマスと両隣の色を取得
        let cur = grid[a];
        let left = grid[a - 1];
        let right = grid[a + 1];

        // 黒の区間の変化量を計算
        let diff = judge_diff_cnt(left, cur, right);
        cnt += diff;

        // 黒の区間の個数を出力
        println!("{}", cnt);

        // 現在のマスの色を反転
        grid[a] ^= true;
    }
}

// 黒の区間の変化量を計算
fn judge_diff_cnt(left: bool, cur: bool, right: bool) -> i64 {
    // 白白白 または 黒黒黒の場合は +1
    if left == cur && cur == right {
        return 1;
    }
    // 黒白黒 または 白黒白の場合は -1
    else if left == right && cur != right {
        return -1;
    }
    // それ以外の場合は変化なし
    0
}

 D 問題問題
https://atcoder.jp/contests/abc411/tasks/abc411_d
解説
この問題では、Q 個のクエリを処理し、最終的にサーバに記録されたログの文字列を順番に出力します。クエリには以下の3種類があります。
PC p をサーバと同期させる。
PC p に文字列 s を末尾に追加（コミット）する。
サーバを PC p の状態に更新する。
クエリ2で文字列を追加する際、時刻と文字列の状態をノードとし、コミット前後の状態を有向辺で結んだ「木構造」を構築します。クエリ1やクエリ3では、PC p やサーバを他方の状態に合わせます。

すべてのクエリを処理した後、サーバの初期状態（時刻0）から最終状態（時刻t）までの経路を深さ優先探索（DFS）で見つけ、その経路上に記録された文字列を順に出力します。
コード
abc411d.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // PCの数
        q: usize, // クエリの数
    }
    // ログツリー
    let mut log_tree = vec![Vec::new(); q + 1];
    
    // ログ情報 (時刻, 文字列)
    let mut log_info = init_log_info(q + 1);
    
    // 各PCの現在のログポイント (0: サーバ, 1~N: クライアントPC)
    let mut log_point = vec![0; n + 1];

    // 各クエリの処理
    for t in 1..=q {
        input! {
            query_type: usize, // クエリの種類
            p: usize,          // クライアントPC番号
        }

        // クエリ1: クライアントpをサーバと同期
        if query_type == 1 {
            log_point[p] = log_point[0];
        }
        
        // クエリ3: サーバをクライアントpの状態に更新
        else if query_type == 3 {
            log_point[0] = log_point[p];
        }
        
        // クエリ2: クライアントpでログをコミット
        else {
            input! {
                log_msg: String, // ログメッセージ
            }
            
            // ログツリーを構築
            let from = log_point[p];
            log_tree[from].push(t);
            
            // ログ情報を更新
            log_info[t].1 = log_msg;
            
            // クライアントpのログポイントを進める
            log_point[p] = t;
        }
    }

    // サーバの初期位置から最終位置までの経路をDFSで探索
    dfs(0, log_point[0], &log_tree, &log_info, &mut vec![]);
}

// ログ情報を初期化
fn init_log_info(size: usize) -> Vec<(usize, String)> {
    let mut log_info = Vec::new();
    for i in 0..size {
        log_info.push((i, "".to_string()));
    }
    log_info
}

// 深さ優先探索 (DFS)
fn dfs(
    cur: usize,
    goal: usize,
    log_tree: &Vec<Vec<usize>>,
    log_info: &Vec<(usize, String)>,
    path: &mut Vec<usize>,
) {
    path.push(cur);

    // ゴールに到達した場合、経路上の文字列を出力
    if cur == goal {
        print_log(path, log_info);
        return;
    }

    // 次のノードを探索
    for &next in &log_tree[cur] {
        dfs(next, goal, log_tree, log_info, path);
    }

    path.pop();
}

// 経路上の文字列を出力
fn print_log(path: &Vec<usize>, log_info: &Vec<(usize, String)>) {
    for &pos in path {
        print!("{}", log_info[pos].1);
    }
    println!();
}
A 問題

B 問題

C 問題

D 問題

Discussion
