👨‍🍳

ABC408: Rustで解く！問題解説

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

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

A 問題

問題

https://atcoder.jp/contests/abc408/tasks/abc408_a

解説

この問題は、 S 秒間反応がなかった場合に寝てしまう人について、入力された時刻列 T の最後まで一度も寝ることなく起きていたかどうかを判定する問題です。

具体的には、最初に cur = 0 (起点の時刻) とし、次に肩をたたく時刻 t_i と前回肩をたたいた時刻 cur の差を計算し、その差が S を超えていないかを順番に確認します。時刻の差が S を超えていれば、その時点で寝てしまったと判定します。

コード

abc408a.rs
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 時刻の数
        s: usize, // 寝るまでの秒数
        t: [usize; n], // 肩をたたく時刻のリスト
    }

    let mut cur = 0; // 前回肩をたたいた時刻
    let mut awake = true; // 起きているかどうかのフラグ

    // 時刻差が s より大きい場合は寝ていると判定
    for tt in t {
        if tt - cur > s {
            awake = false;
        }
        cur = tt;
    }

    // 起きていたかどうかを判定
    println!("{}", if awake { "Yes" } else { "No" });
}

B 問題

問題

https://atcoder.jp/contests/abc408/tasks/abc408_b

解説

長さ N の整数列 A から重複を取り除き、昇順に並べた結果を出力する問題です。

順序付き集合(BTreeSet)に配列の要素を格納すると、重複なしで昇順に出来るのでこのデータ構造を利用して出力します。

コード

abc408b.rs
use std::collections::BTreeSet;
use itertools::Itertools;
use proconio::input;

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

    // 順序付き集合に格納
    let bst = BTreeSet::from_iter(a);
    
    // 個数と要素を出力
    println!("{}", bst.len());
    println!("{}", bst.iter().join(" "));
}

C 問題

問題

https://atcoder.jp/contests/abc408/tasks/abc408_c

解説

1からNまでのマスについて、砲台によって守られていない無防備なマスを作る際に、壊す必要がある砲台の数を最小化する問題です。

砲台が守る区間 [l, r] を効率よく管理するために、imos法を使用します。imos法を使うことで、区間加算を効率的に処理できます。

imos法の手順は以下の通りです。

  1. 区間の開始位置に加算、終了位置の次に減算を行います。
    • cnt[l] ← cnt[l] + 1
    • cnt[r+1] ← cnt[r+1] - 1
  2. 配列全体に累積和を取ることで、各位置の最終的な値を計算します。

コード

abc408c.rs
use proconio::input;
use std::cmp::min;

fn main() {
    // 入力
    input! {
        n: usize, // マスの数
        m: i64,   // 砲台の数
    }

    // 配列の初期化
    let mut cnt = imos_init(n);

    for _ in 0..m {
        // 区間 [l, r] を取得
        input! {
            l: usize, r: usize,
        }
        // 区間の変化量をセット
        imos_set(l, r, &mut cnt);
    }

    // 累積和を計算
    imos_exe(&mut cnt, n);

    // 1~Nの最小値を取得
    let mut ans = m;
    for i in 1..=n {
        ans = min(ans, cnt[i]);
    }

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

// 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];
    }
}

D 問題

問題

https://atcoder.jp/contests/abc408/tasks/abc408_d

解説

この問題では、長さ N の 01文字列 S を「最初は0が0個以上、次に1が0個以上、最後に再び0が0個以上」の0→1→0形式にするために必要な操作回数の最小値を求めます。

この形式を達成するために、文字列を3つの状態に分けて考えます。

  • 状態0：左側の0の区間
  • 状態1：中央の1の区間
  • 状態2：右側の0の区間

動的計画法（DP）を用いて、各文字を見たときにどの状態に遷移するかを考え、操作回数を最小化します。DPテーブル dp[cur][state] は、文字列の先頭から cur 文字目までを見たときに、状態 state（0, 1, 2）で終了するための最小操作回数を表します。

現在の文字(0,1)、現在の状態(0~2)と次に選択する文字(0,1)の計12通りについて、次の状態と必要操作回数を考えると以下表の通りです。

現在の文字 現在の状態 次の選択 次の状態 必要操作回数
'0' 状態0 '0' 状態0 0回
'0' 状態0 '1' 状態1 1回
'0' 状態1 '0' 状態1 1回
'0' 状態1 '1' 状態2 0回
'0' 状態2 '0' 状態2 0回
'0' 状態2 '1' 遷移不可 -
'1' 状態0 '0' 状態0 1回
'1' 状態0 '1' 状態1 0回
'1' 状態1 '0' 状態1 0回
'1' 状態1 '1' 状態2 1回
'1' 状態2 '0' 状態2 1回
'1' 状態2 '1' 遷移不可 -

最後に、文字列全体を見た後の状態0, 1, 2の中で最小の操作回数を出力します。

コード

abc408d.rs
use proconio::{input, marker::Chars};
use std::cmp::min;
const INF: usize = 1 << 60;

fn main() {
    // テストケース数の入力
    input! {
        t: usize,
    }
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    // 入力
    input! {
        n: usize,
        s: Chars,
    }

    // DP[curまで見た][現在の状態0,1,2] = 操作回数の最小値
    let mut dp = vec![vec![INF; 3]; n + 1];
    dp[0][0] = 0;

    for cur in 0..n {
        for state in 0..=2 {
            // 現在の状態を維持する場合
            state_no_change(&mut dp, cur, state, s[cur]);
            // 次の状態に遷移する場合
            state_change(&mut dp, cur, state, s[cur]);
        }
    }

    // 状態0, 1, 2の最小値を求める
    let ans: usize = *dp[n].iter().min().unwrap();

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

// 現在の状態を維持する場合
fn state_no_change(dp: &mut Vec<Vec<usize>>, cur: usize, state: usize, c: char) {
    // 操作コスト
    let mut cost = 0;

    // '1' を '0' に変える場合
    if (state == 0 || state == 2) && c == '1' {
        cost += 1;
    }
    // '0' を '1' に変える場合
    else if state == 1 && c == '0' {
        cost += 1;
    }

    // DPテーブルを更新
    dp[cur + 1][state] = min(dp[cur + 1][state], dp[cur][state] + cost);
}

// 次の状態に遷移する場合
fn state_change(dp: &mut Vec<Vec<usize>>, cur: usize, state: usize, c: char) {
    // 状態2からは遷移できない
    if state == 2 {
        return;
    }

    // 操作コスト
    let mut cost = 0;

    // '0' を '1' に変える場合
    if state == 0 && c == '0' {
        cost += 1;
    }
    // '1' を '0' に変える場合
    else if state == 1 && c == '1' {
        cost += 1;
    }

    // DPテーブルを更新
    dp[cur + 1][state + 1] = min(dp[cur + 1][state + 1], dp[cur][state] + cost);
}

E 問題

問題

https://atcoder.jp/contests/abc408/tasks/abc408_e

解説

頂点1から頂点Nまでの単純パスにおいて、経由する辺の重みの OR を最小化する問題です。

解法としては、移動を許可するビットの集合を管理し、上位ビットから順に特定のビットを禁止しても頂点1から頂点Nまで移動可能かを調べます。移動可否の判定には深さ優先探索（DFS）を用います。

具体的には以下の手順で解きます。

  1. 初期状態ではすべてのビットを許可します。
  2. 上位ビットから順に、特定のビットを禁止しても移動可能かをDFSで判定します。
  3. 移動可能であれば、そのビットを禁止（不要）とします。
  4. 最後まで判定した後、残ったビットの集合が答えとなります。

コード

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

fn main() {
    // 入力
    input! {
        n: usize, m: usize,
    }

    // 無向グラフの構築
    let mut graph = vec![Vec::new(); n];
    for _ in 0..m {
        input! {
            u: Usize1, v: Usize1, w: usize,
        }
        graph[u].push((v, w));
        graph[v].push((u, w));
    }

    // 必要なビットの集合を初期化（全ビットを許可）
    let mut need_mask = (1 << 30) - 1;

    // 上位ビットから順に調べる
    for bit in (0..30).rev() {
        // 禁止するビットを試す
        let ban_bit = 1 << bit;
        // 禁止しても移動可能なら、そのビットは不要
        if dfs(0, n, &graph, need_mask ^ ban_bit, &mut vec![false; n]) {
            need_mask ^= ban_bit;
        }
    }

    // 結果を出力
    println!("{}", need_mask);
}

// 深さ優先探索（DFS）で移動可能かを判定
fn dfs(
    cpos: usize, n: usize, 
    graph: &Vec<Vec<(usize, usize)>>, allow_mask: usize,
    used: &mut Vec<bool>,
) -> bool {
    // 現在の頂点を訪問済みにする
    used[cpos] = true;

    // 頂点Nに到達した場合
    if cpos == n - 1 {
        return true;
    }

    // 次の頂点を探索
    for &(npos, weight) in &graph[cpos] {
        // 訪問済み、または許可されていないビットを含む場合はスキップ
        if used[npos] || (weight & allow_mask != weight) {
            continue;
        }
        // 再帰的に探索
        if dfs(npos, n, graph, allow_mask, used) {
            return true;
        }
    }

    false
}

Discussion