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

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

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

 ABC419-A問題
https://atcoder.jp/contests/abc419/tasks/abc419_a
与えられた文字列を特定のルールに従って変換する問題です。
解説
問題文に記載された変換ルールを整理すると以下表の通りになるため、この内容に沿って変換します。


変換前の文字列
変換後の文字列


red
SSS

blue
FFF

green
MMM

上記以外
Unknown

コード
abc419a.rs
use proconio::input;
fn main() {
    // 入力
    input! {
        s: String, // 文字列
    }

    // 文字列に応じた変換後の文字列を出力
    match s.as_str() {
        "red" => println!("SSS"),
        "blue" => println!("FFF"),
        "green" => println!("MMM"),
        _ => println!("Unknown"),
    }
}

 ABC419-B問題
https://atcoder.jp/contests/abc419/tasks/abc419_b
クエリの内容に従い、値の追加と今持っている値の最小値を取り出す問題です。
解説
この問題を解くのに用いるデータ構造としては、優先度付きキューを使用するのが適しています。Rustでは、 BinaryHeap というデータ構造を使うことで、効率的に値の追加や最小値の取り出しが可能です。

ただし、 BinaryHeap はデフォルトで最大値を優先する構造になっているため、最小値を優先するようにするには、 Reverse ラッパーを用いて値を反転させる必要があります。
コード
abc419b.rs
use proconio::input;
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn main() {
    // 入力
    input! {
        q: usize, // クエリ数
    }

    // 優先度付きキューで値を昇順で管理する
    let mut hp = BinaryHeap::new();

    // クエリ処理
    for _ in 0..q {
        input! {
            nm: usize, // 番号
        }
        // 1の場合は、値xをキューに追加
        if nm == 1 {
            input! {
                x: usize,
            }
            hp.push(Reverse(x));
        }
        // 2の場合は、キューから最も小さい値を取り出す
        else {
            if let Some(Reverse(val)) = hp.pop() {
                println!("{}", val);
            }
        }
    }
}

 ABC419-C問題
https://atcoder.jp/contests/abc419/tasks/abc419_c
各人が上下左右斜めに1マスずつ移動（移動しないも含む）する際に、全員が同じ位置に集まるために必要な移動距離を最小化する問題です。
解説
全員が集まる位置として、r座標（行）とc座標（列）の中心に集めるのが最適です。

中心座標は

\text{中心座標} = (\frac{{min_r + max_r}}{2}, \frac{{min_c + max_c}}{2})
で求められます。

次に各人の中心座標への移動ですが、今いる座標と中心座標との距離差になるため、r 軸方向、 c 軸方向について距離差を計算します。 r 軸方向への移動と c 軸方向への移動は同時に行えるため、各人の移動に必要な移動距離は、r 軸方向、 c 軸方向のうち大きい方になります。

これを全員分計算し、移動距離が最大のものが答えとなります。
コード
abc419c.rs
use proconio::input;
use std::cmp::max;

fn main() {
    // 入力
    input! {
        n: usize, // 人数
        rc: [(i64, i64); n], // 人の座標
    }

    // r軸方向、c軸方向を独立して管理
    let mut rlist = Vec::new();
    let mut clist = Vec::new();
    for (r, c) in rc {
        rlist.push(r);
        clist.push(c);
    }

    // r軸方向とc軸方向の中心を求める
    let r_center = calc_center(&rlist);
    let c_center = calc_center(&clist);

    // 各人について、中心座標から遠い距離差を選び、最大値を求める。
    let mut ans = 0;    
    for i in 0..n {
        let diff_r = (rlist[i] - r_center).abs();
        let diff_c = (clist[i] - c_center).abs();
        let val = max(diff_r, diff_c);
        ans = max(val, ans);
    }

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

// 座標軸の中心を計算する関数
fn calc_center(pos_list: &Vec<i64>) -> i64 {
    // 座標軸の最小値、最大値を求める
    let pos_min = *pos_list.iter().min().unwrap();
    let pos_max = *pos_list.iter().max().unwrap();
    
    // 座標軸の中心を求める
    (pos_min + pos_max) / 2
}

 ABC419-D問題
https://atcoder.jp/contests/abc419/tasks/abc419_d
文字列 S と T に対して、指定された範囲での文字の交換操作を繰り返した後の文字列 S を求める問題です。
解説
同じ添字 i に対して S[i] と T[i] を入れ替える操作なので、各 i について最終的に S[i] を採るか T[i] を採るかは、交換回数の偶奇で決まります。したがって、各文字の位置について交換回数を記録し、交換回数が奇数なら T の文字、偶数なら S の文字を出力すればよいです。

交換操作は指定された範囲でまとめて行われますが、範囲指定の加算処理を効率的に行うために、imos法を使用します。imos法では、範囲の始点に加算、終点の次の位置に減算を記録し、最後に累積和を取ることで範囲の加算を効率的に計算できます。
コード
abc419d.rs
use proconio::{input, marker::Chars, marker::Usize1};

fn main() {
    // 入力
    input! {
        n: usize, // 文字列の長さ
        m: usize, // 操作回数
        s: Chars, // 文字列S
        t: Chars, // 文字列T
        lr: [(Usize1, Usize1); m], // 操作範囲[l, r] (0-index)
    }

    // 各文字の操作回数をimos法で計算
    let mut imos = imos_init(n);
    
    // 加算する区間[l, r]をセット
    for &(l, r) in &lr {
        imos_set(l, r, &mut imos);
    }
    
    // 加算を実行
    imos_exe(&mut imos, n);

    // 文字を出力
    for i in 0..n {
        // 操作回数が奇数ならt、偶数ならsの文字を出力
        print!("{}", if imos[i] % 2 == 1 { t[i] } else { s[i] });
    }
    println!();
}

// imos法の初期化
fn imos_init(n: usize) -> Vec<i64> {
    // 余裕を持たせて n+2 にする
    vec![0; n + 2]
}

// 区間 [l, r] の変化量を設定
fn imos_set(l: usize, r: usize, cnt: &mut Vec<i64>) {
    cnt[l] += 1;
    cnt[r + 1] -= 1;
}

// 累積和を計算
fn imos_exe(cnt: &mut Vec<i64>, n: usize) {
    for i in 0..n {
        cnt[i + 1] += cnt[i];
    }
}

 ABC419-E問題
https://atcoder.jp/contests/abc419/tasks/abc419_e
数列 A の各要素に 0 から M-1 の間で任意に加算して、連続部分列の総和がすべて M の倍数になるようにするための加算量の総和(操作回数)を最小化する問題です。
解説
長さ L の連続部分列の総和がすべて同じになる場合、数列を L 個おきに見ていくと、それらの値は同じ値に揃える必要があります。この性質を利用して、数列を L 個のグループに分けて考えます。

各グループについて、どの値に揃えるかを動的計画法(DP)により選択しながら、必要な操作回数を最小化するように計算します。

DPの状態と遷移は以下のように定義します。
状態
\text{dp[r] = 操作回数の最小値}

※ r はこれまで処理したグループの合計を M で割った余り
遷移
\text{next\_dp[(r + adds) \% M]} =

\text{min(next\_dp[(r + adds) \% M], cur\_dp[r] + 増加する操作回数[idx][adds])}

※ idx は選択するグループ 、 adds はグループで選択する値
実装方針としては、以下1~4のとおりになります。
数列を L 個のグループに分けます。
各グループについて、どの値に揃えるかを選択した際に増加する操作回数を事前計算します。
DPを用いて、グループごとに操作回数を最小化しながら進めていきます。
最終的に、総和の状態が 0 となる場合の操作回数を出力します。
コード
abc419e.rs
use proconio::input;
use std::cmp::min;

const INF: usize = 1 << 60;

fn main() {
    // 入力
    input! {
        n: usize, // 数列の長さ
        m: usize, // Mの倍数
        l: usize, // 連続部分列の長さ
        a: [usize; n], // 数列の各値
    }

    // 数列をL個のグループに分ける
    let groups = array_grouping(n, l, &a);

    // 各グループで、目標値(to)に揃える際に増加する操作回数を計算
    let add_cost = calc_addcost_groupby(m, l, &groups);
    
    // DP配列の初期化(dp[総和(Mで割った余り)] = 増加する操作回数のmin)
    let mut cur_dp = vec![INF; m];
    cur_dp[0] = 0;

    // グループごとにDPを更新
    for idx in 0..l {
        let mut next_dp = vec![INF; m];
        // 操作前と操作後の総和を全探索
        for from in 0..m {
            for to in 0..m {
                // idx番目のグループで選択する目標値
                let adds = (to + m - from) % m;
                // DP更新
                next_dp[to] = min(next_dp[to], cur_dp[from] + add_cost[idx][adds]);
            }
        }
        cur_dp = next_dp;
    }

    // 総和が0のときの操作回数を出力
    println!("{}", cur_dp[0]);
}

// 数列をL個のグループに分ける関数
fn array_grouping(n: usize, l: usize, a: &Vec<usize>) -> Vec<Vec<usize>> {
    let mut groups = vec![Vec::new(); l];
    for i in 0..n {
        let idx = i % l;
        groups[idx].push(a[i]);
    }
    groups
}

// 各グループで、現在の各値(from)を目標値(to)に揃える際に増加する操作回数を計算する関数
fn calc_addcost_groupby(m: usize, l: usize, groups: &Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let mut add_cost = vec![vec![0; m]; l];
    for idx in 0..l {
        for to in 0..m {
            let mut cost = 0;
            for &from in &groups[idx] {
                cost += (to + m - from) % m;
            }
            add_cost[idx][to] = cost;
        }
    }
    add_cost
}
変換前の文字列	変換後の文字列
`red`	`SSS`
`blue`	`FFF`
`green`	`MMM`
上記以外	`Unknown`
ABC419-A

ABC419-B

ABC419-C

ABC419-D

ABC419-E

Discussion
