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

2025/07/21に公開
AtCoder Beginner Contest 415のA-E問題を緑コーダーが分かりやすく解説をまとめてみました。参考になりましたら幸いです。

 ABC415-A問題
https://atcoder.jp/contests/abc415/tasks/abc415_a
値 X が整数列 A に含まれるかを判定する問題です。
解説
整数列 A を順番に調べ、 X と一致する値が見つかった場合は Yes を出力し、見つからなかった場合は No を出力します。
コード
abc415a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 配列の長さ
        a: [usize; n], // 配列の各値
        x: usize, // 探す値
    }

    // xと一致する値を見つける
    let mut found = false;
    for &val in &a {
        if val == x {
            found = true;
        }
    }

    // 一致したかどうかを出力
    println!("{}", if found { "Yes" } else { "No" });
}

 ABC415-B問題
https://atcoder.jp/contests/abc415/tasks/abc415_b
倉庫内の荷物がある区間の番号を2つずつ出力する問題です。
解説
倉庫の区画を順番に調べて、 # が現れるたびにその区画番号を記録します。記録した区画番号が2つになった時点でそれらを出力し、記録をリセットします。この操作を倉庫全体に対して繰り返します。
コード
abc415b.rs
use proconio::{input, marker::Chars};

fn main() {
    // 入力
    input! {
        s: Chars, // 倉庫の区画情報
    }
    
    // 荷物情報
    let mut luggage = Vec::new();

    // 区画を順番に調べる
    for i in 0..s.len() {
        if s[i] == '#' {
            // 現在の区画番号を記録
            luggage.push(i + 1);

            // 荷物を2つ持っていたら、区画番号を出力して荷物を空にする
            if luggage.len() == 2 {
                println!("{},{}", luggage[0], luggage[1]);
                luggage.clear();
            }
        }
    }
}

 ABC415-C問題
https://atcoder.jp/contests/abc415/tasks/abc415_c
N 種類の薬品を任意の順番で1つずつ混ぜたとき、危険な状態を作ることなく混ぜることができるかどうかを判定する問題です。
解説
まず、各薬品の混ぜ合わせ状態をbitで表現します。たとえば、薬品が3種類ある場合、状態は3ビットで表現され、 000 は何も混ぜていない状態、 101 は1番目と3番目の薬品を混ぜた状態を意味します。

上を踏まえたうえで、各薬品の混ぜ合わせ状態を動的計画法(DP)を用いて順番に調べていくことで解くことができます。(bitで表した状態についてDPを用いるため、通称bitDPと呼ばれるテクニックになります。)

DPの状態、遷移は以下のように定義します。
状態

DP配列 dp[state]を用いて、状態が安全であれば true 、危険であれば false とします。
遷移

現在の状態 cstate から、1つの薬品を混ぜて次の状態 nstate に遷移します。

現在の状態 cstate から、i 番目の薬品を選んだ時の遷移は以下の通りになります。

    dp[nstate] = dp[cstate] | (1 << i)
    このとき、すでに安全と判定されている状態への遷移は不要です。

また、遷移先の状態が危険であれば遷移を行いません。
初期状態は何も混ぜていない状態 000 で、これは安全とします。この状態から実際に順にすべての状態を調べ、遷移可能な状態を更新していきます。

すべての薬品を混ぜた状態 111 が安全であれば Yes、そうでなければ Noを出力します。
コード
abc415c.rs
use proconio::{input, marker::Chars};

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

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

fn solve() {
    // 入力
    input! {
        n: usize, // 薬品の種類数
        mut s: Chars, // 薬品の組み合わせ状態(0:安全、1:危険)
    }
    // 初期状態の組み合わせを追加
    s.insert(0, '0');
    
    // DP初期化
    let sz = s.len();
    let mut dp = vec![false; sz];
    dp[0] = true;

    // 各状態からの遷移を探索
    for cstate in 0..sz {
        // 危険な状態であれば処理しない
        if !dp[cstate] { continue; }

        // 混ぜる薬品を選択
        for bits in 0..n {
            // 混ぜた後の状態
            let nstate = cstate | 1 << bits;

            // 安全と分かっている状態への遷移は不要
            if dp[nstate] { continue; }
            // 危険な状態へは遷移しない
            if s[nstate] == '1' { continue; }

            // 安全な状態として遷移
            dp[nstate] = true;
        }
    }

    // 全て混ぜた状態は安全かどうかを判定
    println!("{}", if dp[sz-1] {"Yes"} else {"No"});
}

 ABC415-D問題
https://atcoder.jp/contests/abc415/tasks/abc415_d
持っている瓶を交換して手に入れることができるシールの枚数を最大化する問題です。
解説
この問題では、各店で瓶をシールに交換する際に、以下の条件が与えられています。
交換には最低限必要な瓶の本数 A
交換後に戻ってくる瓶の本数 B
交換を行うと、差し引き A-B 本の瓶を消費して1枚のシールを得ることができます。

このとき、A-B が小さい店ほど効率的にシールを得られるため、A-B が小さい順に交換を行うのが最適です。
具体的には以下の1~4の手順で解きます。
各店の A-B を計算し、A-B が小さい順に並べます。
現在持っている瓶の本数が A 以上であれば、その店で交換を繰り返します。

交換可能な回数は、(\text{現在の瓶の本数} - A) / (A-B) + 1 で計算できます。
交換できなくなったら、次に A-B が小さい店に移動します。
これを繰り返し、最終的に得られるシールの枚数を計算します。
コード
abc415d.rs
use proconio::input;

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Store {
    diff: i64, // a-bの値
    min_bottles: i64, // 交換に必要なaの値
}

fn main() {
    // 入力
    input! {
        n: i64, // はじめの瓶の本数
        m: usize, // 店の数
        ab: [(i64, i64); m], // 各店の情報
    }

    // a-bが小さい順に店の交換情報を構築 
    let stores = make_store_info(&ab);

    // 交換による手に入るシールの枚数の計算結果を取得して、出力
    let ans = calc_get_stickers(n, m, &stores);
    println!("{}", ans);
}

fn make_store_info(ab: &Vec<(i64, i64)>) -> Vec<Store> {
    // a-bが小さい順に並べる(a-b, a)
    let mut stores = Vec::new();
    for &(a, b) in ab {
        stores.push(Store{diff: a-b, min_bottles: a});
    }
    stores.sort();
    stores
}

fn calc_get_stickers(n: i64, m: usize, stores: &Vec<Store>) -> i64 {
    // シールの取得枚数
    let mut ret = 0;
    // 現在持っている瓶入りのコーラの本数
    let mut cur = n;
    // 現在チェックしている店のインデックス
    let mut idx = 0;

    // 店を順番にチェック
    while idx < m {
        // 交換可能
        if cur >= stores[idx].min_bottles {
            // 交換できる回数
            // 「x - t(-a+b) < a」のtを求める。
            // 式変形して、「t > (x-a) / (a-b)」
            let cnt = (cur - stores[idx].min_bottles) / stores[idx].diff + 1;

            // シールを取得し、瓶を消費
            ret += cnt;
            cur -= cnt * stores[idx].diff;
        }
        // 交換できない場合は次の店
        else {
            idx += 1;
        }
    }
    ret
}

 ABC415-E問題
https://atcoder.jp/contests/abc415/tasks/abc415_e
グリッド上を移動しながらコインを取得・消費する際に、移動を完了するために必要な初期所持金を求める問題です。
解説
初期所持金を仮定し、その金額で移動が可能かどうかを判定して解きます。初期所持金の仮定には二分探索を用い、移動可能であれば初期所持金を減らし、不可能であれば初期所持金を増やすと、効率よく調べることができます。

決めた初期所持金で左上から右下まで移動可能かどうかの判定を動的計画法 (DP) を用いて行います。DPの状態、遷移は以下のように定義します。
状態

グリッドの位置 (i, j) における移動直前の所持金を記録します。
遷移

現在の位置から右または下に移動した際の所持金を計算し、0円以上であれば遷移可能とします。

現在の位置 (i, j) から次の位置 (ni, nj) に移動する際の所持金は以下のように計算します。

   \text{次の所持金} = \text{現在の所持金} + A[ni][nj] - P[ni + nj]
   ここで、A[ni][nj] は移動先のグリッドにあるコインの枚数、P[ni + nj] は移動先で消費するコインの枚数です。

DPの最終地点 (右下) の所持金が0円以上であれば、その初期所持金で移動可能と判定します。
初期所持金を仮定し最終地点までの移動できたかどうかの結果に応じて、初期所持金として考えられる範囲を狭めていくと最小の初期所持金を求めることができます。
コード
abc415e.rs
use proconio::input;
use std::cmp::max;
const INF: i64 = 1 << 60;

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

    // 答え(はじめの所持金)を二分探索
    let ans = binary_search(h, w, &a, &p);
    // 結果を出力
    println!("{}", ans);
}

fn binary_search(
    h: usize, w: usize,
    a: &Vec<Vec<i64>>,
    p: &Vec<i64>
) -> i64 {
    let mut ng = -1;
    let mut ok = INF;

    for _ in 0..70 {
        let mid = (ng + ok) / 2;
        if isok(mid, h, w, &a, &p) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    ok 
}

fn isok(x: i64, 
    h: usize, w: usize,
    a: &Vec<Vec<i64>>, p: &Vec<i64>,
) -> bool {
    // DP:位置(i,j)にいるときの移動直前に持っている所持金
    let mut dp = vec![vec![-INF; w]; h];

    // 初期状態をセット
    dp[0][0] = x + a[0][0] - p[0];
    
    // DPの遷移
    for ci in 0..h {
        for cj in 0..w {
            // 0円未満なら移動不可
            if dp[ci][cj] < 0 { continue; }

            // 右に移動
            if cj + 1 < w {
                let ni = ci;
                let nj = cj + 1;
                // DPの遷移
                dp_transition((ci, cj), (ni, nj), a, p, &mut dp);
            }
            // 下に移動
            if ci + 1 < h {
                let ni = ci + 1;
                let nj = cj;
                // DPの遷移
                dp_transition((ci, cj), (ni, nj), a, p, &mut dp);
            }
        }
    }

    // 最後まで移動して0円以上ならOK
    dp[h-1][w-1] >= 0
}

fn dp_transition(
    cpos: (usize, usize), npos: (usize, usize),
    a: &Vec<Vec<i64>>, p: &Vec<i64>, dp: &mut Vec<Vec<i64>>) {
    let nyen = dp[cpos.0][cpos.1] + a[npos.0][npos.1] - p[npos.0 + npos.1];
    // 0円以上なら遷移
    if nyen >= 0 {
        dp[npos.0][npos.1] = max(dp[npos.0][npos.1], nyen);
    }
}
ABC415-A

ABC415-B

ABC415-C

ABC415-D

ABC415-E

Discussion
