Zenn
👨‍🍳

ABC410: Rustで解く！問題解説

に公開
Rust
競技プログラミング
AtCoder
tech

AtCoder Beginner Contest 410のA-E問題をRustで解いた際の解法をまとめました。

A 問題

問題

https://atcoder.jp/contests/abc410/tasks/abc410_a

解説

K 歳の馬が出場可能なレースの個数を求める問題です。
各レースには年齢制限があり、その上限が A_i で与えられています。したがって、A_i \geq K を満たすレースの個数を数えれば答えが求まります。

コード

abc410a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // レース数
        a: [usize; n], // 各レースの年齢制限
        k: usize, // 年齢
    }

    // K歳の馬が参加可能なレースの数を数える
    let mut cnt = 0;
    for limit in a {
        if limit >= k {
            cnt += 1;
        }
    }

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

B 問題

問題

https://atcoder.jp/contests/abc410/tasks/abc410_b

解説

以下のルールで、クエリごとにどの箱にボールを入れるかを答える問題です。

  1. X_i \geq 1 の場合、X_i 番目の箱にボールを入れます。
  2. X_i = 0 の場合、ボールの個数が最も少ない箱を選びます。同数の場合は、番号が最小の箱を選びます。

具体的な処理は以下の通りです。

  1. X_i \geq 1 の場合
    X_i をそのまま箱の番号とします。

  2. X_i = 0 の場合
    全ての箱を調べてボールの個数が最小の箱を選びます。同数の場合は番号が小さい箱を優先します。

なお、箱は1から N までの番号が付けられているため、配列を1インデックスで扱えるように、ダミーの0番目の箱を用意します。

コード

abc410b.rs
use proconio::input;
const INF: usize = 1 << 60;

fn main() {
    // 入力
    input! {
        n: usize, // 箱の数
        q: usize, // クエリの数
        x: [usize; q], // クエリの内容
    }

    // 各箱に入っているボールの個数を管理 (0番目はダミー)
    let mut boxes = vec![0; n + 1];
    boxes[0] = INF; // 0番目の箱は使用しないため、無限大に設定

    // 各クエリを実施
    for &val in &x {
        // 入れる箱のインデックスを特定して、ボールを1個入れる
        let idx = find_idx(val, &boxes, n);
        boxes[idx] += 1;

        // 入れた箱の番号を出力
        println!("{}", idx);
    }
}

// 入れるべき箱のインデックスを特定する関数
fn find_idx(val: usize, boxes: &Vec<usize>, n: usize) -> usize {
    // Xが1以上なら、その番号の箱に入れる
    if val >= 1 {
        return val;
    }

    // Xが0の場合、ボールの個数が最小の箱を探す
    let mut idx_min = INF; // 最小の箱のインデックス
    let mut cnt_min = INF; // 最小のボール数
    for i in 1..=n {
        if boxes[i] < cnt_min {
            cnt_min = boxes[i];
            idx_min = i;
        }
    }

    // 最小の箱のインデックスを返す
    idx_min
}

C 問題

問題

https://atcoder.jp/contests/abc410/tasks/abc410_c

解説

数列に対して以下の3つのクエリを処理する問題です。

  1. 数列 A の p 番目の値を x に変更する。
  2. 数列 A の p 番目の値を出力する。
  3. 数列 A の先頭の要素を末尾に移動する操作を k 回行う。

クエリ1とクエリ2はそのまま処理できますが、クエリ3の操作で k が非常に大きい場合（最大 10^9 ）にそのまま処理すると計算量が膨大になります。そのため、クエリ3では実際に配列を回転させるのではなく、回転した回数を記録しておき、クエリ1やクエリ2を処理する際にインデックスを調整することで効率的に処理します。

具体的には、配列のインデックスを計算する際に、現在の回転数を考慮して以下のように調整すると、配列の回転をシミュレートすることができます。

\text{idx} = (\text{p} + \text{rotate\_k}) \mod n

コード

abc410c.rs
use proconio::{input, marker::Usize1};

fn main() {
    // 入力
    input! {
        n: usize, // 配列の長さ
        q: usize, // クエリの数
    }

    // 初期値を設定
    let mut val = vec![0; n];
    for i in 0..n { 
        val[i] = i + 1;
    }

    // 回転回数を記録
    let mut rotate_k = 0;

    // クエリを処理
    for _ in 0..q {
        input! {
            query_type: usize, // クエリの種類
        }

        // クエリ1: p番目にxを入れる
        if query_type == 1 {
            input! {
                p: Usize1, // p番目
                x: usize,  // 入れる値
            }
            let idx = (p + rotate_k) % n;
            val[idx] = x;
        }
        // クエリ2: p番目の値を出力
        else if query_type == 2 {
            input! {
                p: Usize1, // p番目
            }
            let idx = (p + rotate_k) % n;
            println!("{}", val[idx]);
        }
        // クエリ3: k回移動させる
        else{
            input! {
                k: usize, // 移動回数
            }
            // 回転回数を更新
            rotate_k = (rotate_k + k) % n;
        }
    }
}

D 問題

問題

https://atcoder.jp/contests/abc410/tasks/abc410_d

解説

頂点1から頂点 N までの任意の経路を通る際に、通過する辺の重みの総XOR値を最小化する問題です。

辺の重みは 0 から 2^{10}-1 の範囲（1024通り）であるため、各頂点で考えられる状態も1024通りとなります。そのため、頂点数 N \times XORの状態（1024通り）について、初期状態（頂点1、XORが0）から到達可能な状態を幅優先探索（BFS）を用いて調べます。

すべての状態を調べ終わった後、頂点 N に到達した際のXOR値の最小値を求めます。もし頂点 N に到達する経路が存在しない場合は、-1を出力します。

コード

abc410d.rs
use proconio::{input, marker::Usize1};
use std::collections::VecDeque;
const SZ: usize = 1 << 10;

fn main() {
    // 入力
    input! {
        n: usize, m: usize,
        abw: [(Usize1, Usize1, usize); m],
    }

    // 有向グラフを作成
    let graph = make_graph(n, &abw);

    // キュー (XORの状態, 現在の頂点)
    let mut dq = VecDeque::new();
    // 状態管理: [頂点i][XORの状態j] = 遷移可否
    let mut used = vec![vec![false; SZ]; n];

    // 初期状態をセット
    dq.push_back((0, 0));
    used[0][0] = true;

    // BFSで到達可能な状態を調べる
    while let Some((cur_state, cur_pos)) = dq.pop_front() {
        for &(weight, next_pos) in &graph[cur_pos] {
            let next_state = cur_state ^ weight;
            if !used[next_pos][next_state] {
                used[next_pos][next_state] = true;
                dq.push_back((next_state, next_pos));
            }
        }
    }

    // 頂点Nについて、遷移可能なXOR状態の最小値を求める
    let result = get_min_state(&used, n);

    // 出力
    if result == SZ {
        println!("-1");
    } else {
        println!("{}", result);
    }
}

// グラフを作成
fn make_graph(n: usize, abw: &Vec<(usize, usize, usize)>) -> Vec<Vec<(usize, usize)>> {
    let mut graph = vec![Vec::new(); n];
    for &(a, b, w) in abw {
        graph[a].push((w, b));
    }
    graph
}

// 頂点Nにおける最小のXOR値を取得
fn get_min_state(used: &Vec<Vec<bool>>, n: usize) -> usize {
    for state in 0..SZ {
        if used[n - 1][state] {
            return state;
        }
    }
    SZ
}

E 問題

問題

https://atcoder.jp/contests/abc410/tasks/abc410_e

解説

体力または魔力を消費して敵を順番に倒していく際に、倒すことができる敵の数の最大値を求める問題です。

この問題は動的計画法 (DP) を用いることで解くことができます。DP配列は以下のように定義します。

  • DP[体力]：その体力で可能な魔力の最大値。

遷移は以下のように行います。
現在の体力を cur_hp、消費後の体力を next_hp 、
現在の魔力を cur_magic、消費後の魔力を next_magic
とすると、

  1. 体力を使う場合
    dp_{next}[next\_hp] = \max(dp_{next}[next\_hp], cur\_magic)
  2. 魔力を使う場合
    dp_{next}[cur\_hp] = \max(dp_{next}[cur\_hp], next\_magic)

各敵について遷移を行い、魔力が0以上の状態が存在しない場合や全ての敵を倒し終わった場合に終了し、その時点で倒した敵の数を出力します。

コード

abc410e.rs
use proconio::input;
use std::mem::swap;
use std::cmp::max;

const INF: i64 = 1 << 60;

fn main() {
    // 入力
    input! {
        n: usize, // 敵の数
        h: usize, // 初期体力
        m: usize, // 初期魔力
        ab: [(i64, i64); n], // 各敵を倒すのに必要な体力と魔力
    }

    // i匹目を倒した時の、DP[体力] = 可能な魔力の最大値
    let mut cur_dp = vec![-INF; h + 1];
    // 初期状態をセット
    cur_dp[h] = m as i64;

    for i in 0..n {
        // 次の状態
        let mut next_dp = vec![-INF; h + 1];

        for cur_hp in 0..=h {
            let cur_magic = cur_dp[cur_hp];

            // 体力を使う場合 (魔力はそのまま)
            if cur_hp as i64 >= ab[i].0 {
                let next_hp = (cur_hp as i64 - ab[i].0) as usize;
                next_dp[next_hp] = max(next_dp[next_hp], cur_magic);
            }

            // 魔力を使う場合 (体力はそのまま)
            if cur_magic >= ab[i].1 {
                let next_magic = cur_magic - ab[i].1;
                next_dp[cur_hp] = max(next_dp[cur_hp], next_magic);
            }
        }

        // 魔力が0以上の状態が存在するか判定
        if !has_positive_magic(&next_dp, h) {
            println!("{}", i);
            return;
        }

        // 次の状態と入れ替え
        swap(&mut cur_dp, &mut next_dp);
    }

    // 全ての敵を倒した場合
    println!("{}", n);
}

// 魔力が0以上の状態が存在するか判定
fn has_positive_magic(dp: &Vec<i64>, h: usize) -> bool {
    for i in 0..=h {
        if dp[i] >= 0 {
            return true;
        }
    }
    false
}

Discussion