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

2025/05/25に公開
AtCoder Beginner Contest 407のA-E問題をRustで解いた際の解法をまとめました。

 A 問題問題
https://atcoder.jp/contests/abc407/tasks/abc407_a
解説
A を B で割った結果を小数点第1位で四捨五入した値を求める問題です。
浮動小数点による誤差を避けるため、整数演算だけで四捨五入を実装します。具体的には、\frac{A}{B} の結果に 0.5 を加えた値を整数に切り捨てることで四捨五入を実現します。この操作を整数演算で表現するために、以下の式を用いて計算を行います。

\text{AをBで割った結果} = \left\lfloor \frac{2A + B}{2B} \right\rfloor
コード
abc407a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        a: usize, 
        b: usize
    }

    // 四捨五入の計算
    // 分子: 2 * a + b
    // 分母: 2 * b
    let numerator = 2 * a + b;
    let denominator = 2 * b;

    // 出力
    println!("{}", numerator / denominator);
}

 B 問題問題
https://atcoder.jp/contests/abc407/tasks/abc407_b
解説
この問題では、2つのサイコロを振ったときに以下いずれかの条件を満たす確率を求めます。
2つの出目の合計が X 以上である。

2つの出目の差の絶対値が Y 以上である。
サイコロ2つの出目の組み合わせは全部で 6 \times 6 = 36 通りあります。それぞれの組み合わせについて条件を満たすかどうかを確認し、条件を満たす組み合わせの個数を数えます。その後、条件を満たす個数を 36 で割ることで確率を求めます。
コード
abc407b.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        x: usize, // 合計がX以上
        y: usize, // 差の絶対値がY以上
    }

    // 条件を満たす組み合わせの個数をカウント
    let mut cnt = 0;
    for i in 1..=6 {
        for j in 1..=6 {
            if (i + j >= x) || (i.abs_diff(j) >= y) {
                cnt += 1;
            }
        }
    }

    // 確率を計算して出力
    println!("{}", cnt as f64 / 36.0);
}

 C 問題問題
https://atcoder.jp/contests/abc407/tasks/abc407_c
解説
この問題では、何も表示されていない状態から、以下の2つのボタン操作を行い、文字列 S を表示するために必要な操作回数を求めます。
ボタンAを押して、末尾に0を追加する。
ボタンBを押して、各桁の値を1つ大きくする。ただし、9の場合のみ0にする。
文字列 S を実現するための操作は、以下のようになります。(各 X_{i} は0～9)
ボタンAを1回押す → ボタンBを X_{1} 回押す → ボタンAを1回押す → ボタンBを X_{2} 回押す → ... → ボタンAを1回押す → ボタンBを X_{N} 回押す
上記について、ボタンA、ボタンBの操作回数をそれぞれ求めて合計を求めます。
(1)ボタンAの操作回数

文字列 S の各桁を作るために、ボタンAは必ず1回押されます。そのため、ボタンAの操作回数は文字列 S の長さに等しくなります。
(2)ボタンBの操作回数
各桁の値について、ボタンAが押されてから値が大きくなった回数に注目します。すると、以下のようになります。
末尾： X_{N} 回

末尾から2番目： X_{N-1} + X_{N} 回

・・・

先頭： X_{1} + X_{2} + ... + X_{N} 回
上記より、文字列の先頭の値がボタンBを押した回数と一致しますが、9→0による繰り上がり分が失われています。なので、各桁の値を後ろからみて繰り上がり分を再計算します。具体的には以下のように求めます。
文字列 S を後ろから順に見て、現在の桁の値が前の桁の値より大きい(9→1のように戻って増えている)場合、ボタンBを10回分として数えます。
最後に、文字列の先頭の桁の値を加えます。
コード
abc407c.rs
use proconio::{input, marker::Chars};

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

    // ボタンAの回数は、文字列の長さに一致
    let btn_a = s.len();

    // ボタンBの回数を計算
    let btn_b = calc_btn_b_cnt(&s);

    // 出力
    println!("{}", btn_a + btn_b);
}

fn calc_btn_b_cnt(s: &Vec<char>) -> usize {
    // 繰り上がり回数
    let mut carry_cnt = 0;

    // 後ろから繰り上がりを計算
    for i in (0..s.len() - 1).rev() {
        let cur = s[i + 1] as usize - 0x30; // 現在の桁
        let prev = s[i] as usize - 0x30;   // 1つ前の桁
        if prev < cur {
            carry_cnt += 1;
        }
    }

    // 一の位の値
    let first_digit = s[0] as usize - 0x30;

    // ボタンBの回数を計算
    carry_cnt * 10 + first_digit
}

 D 問題問題
https://atcoder.jp/contests/abc407/tasks/abc407_d
解説
1 \times 2 のサイズのドミノを任意のマスに配置した際のスコア（※）を最大化する問題です。

※スコアは、空いているマスに書かれている値の総XORです。
この問題は、H行W列のマス目へのドミノの置き方を再帰関数を用いて全て試すことで解くことができます。具体的には以下の手順で実装します。
H行W列のマス目について、1行1列目（左上）を0番目として、0から H \times W -1 の1次元インデックスを割り当てます。
割り当てた番号について、0番目から順番に以下のいずれかを実施します。
現在のマスとその右隣のマスの2マス分にドミノを配置して、次のマスを探索します。
現在のマスとその下隣のマスの2マス分にドミノを配置して、次のマスを探索します。
ドミノを置かずに、次のマスを探索します。

右下のマスまで探索が終わったら、空いているマスの値のXORを計算し、スコアの最大値を記録します。
コード
abc407d.rs
use proconio::input;
use std::cmp::max;

fn main() {
    // 入力
    input! {
        h: usize, w: usize,
        a: [[usize; w]; h],
    }

    let mut ans = 0;
    let mut used = vec![vec![false; w]; h];

    // 配置の仕方を再帰で全て試す
    rec(0, h, w, &mut ans, &mut used, &a);

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

fn rec(pos: usize, h: usize, w: usize,
    ans: &mut usize,
    used: &mut Vec<Vec<bool>>,
    a: &Vec<Vec<usize>>,
) {
    // 右下まで見た
    if pos == h * w {
        // 空いているマスのXOR計算
        let ret = calc_score(h, w, used, a);
        *ans = max(ret, *ans);
        return;
    }
    // まだ見ていないマスあり

    // 縦、横の座標を取得
    let x = pos / w;
    let y = pos % w;

    // 右向きに配置する
    if y+1 < w && !used[x][y] && !used[x][y+1] {
        set_domino((x, y), (x, y+1), used);
        rec(pos+1, h, w, ans, used, a);
        unset_domino((x, y), (x, y+1), used);
    }
    // 下向きに配置する
    if x+1 < h && !used[x][y] && !used[x+1][y] {
        set_domino((x, y), (x+1, y), used);
        rec(pos+1, h, w, ans, used, a);
        unset_domino((x, y), (x+1, y), used);
    }
    // 置かない
    rec(pos+1, h, w, ans, used, a);
}

fn calc_score(h: usize, w: usize,
    used: &Vec<Vec<bool>>, a: &Vec<Vec<usize>>
) -> usize {
    let mut ret = 0;
    for i in 0..h {
        for j in 0..w {
            if !used[i][j] {
                ret ^= a[i][j];
            }
        }
    }
    ret
}

fn set_domino(
    pos1: (usize, usize), pos2: (usize, usize),
    used: &mut Vec<Vec<bool>>) {
    used[pos1.0][pos1.1] = true;
    used[pos2.0][pos2.1] = true;
}
fn unset_domino(
    pos1: (usize, usize), pos2: (usize, usize),
    used: &mut Vec<Vec<bool>>) {
    used[pos1.0][pos1.1] = false;
    used[pos2.0][pos2.1] = false;
}

 E 問題問題
https://atcoder.jp/contests/abc407/tasks/abc407_e
解説
この問題は、正しい括弧列を作る際に「(」の位置を決めたときのスコアを最大化する問題です。
正しい括弧列を作るためには、常に「(」の数が「)」の数以上である必要があります。この条件を満たしながら、与えられたスコア配列から「(」を選ぶことでスコアを最大化します。
具体的には、以下の手順で解きます。
最初の「(」は必ず1文字目に配置します。このとき、スコア配列の最初の値を加算します。
2つ目以降の「(」は、直前までに追加していない A[2i - 1], A[2i] の2つを候補に追加した上で、持っている候補の中で値が最も大きいものを取り出して配置します。この選択を繰り返すことで、スコアを最大化できます。
候補の管理には、 BinaryHeap を使用します。これにより、効率的にスコアが高い「(」を選ぶことができます。
コード
abc407e.rs
use proconio::input;
use std::collections::BinaryHeap;

fn main() {
    // テストケース数を入力
    input! {
        t: usize,
    }

    for _ in 0..t {
        solve();
    }
}

fn solve() {
    // 入力
    input! {
        n: usize,
        a: [usize; 2 * n],
    }

    let mut tot = 0;
    let mut heap = BinaryHeap::new();

    // 最初の「(」を選択
    tot += a[0];

    // 2つ目以降の「(」を選択
    for i in 1..n {
        heap.push(a[2 * i - 1]);
        heap.push(a[2 * i]);
        if let Some(max_val) = heap.pop() {
            tot += max_val;
        }
    }

    // 結果を出力
    println!("{}", tot);
}
A 問題

B 問題

C 問題

D 問題

E 問題

Discussion
