ABC412: Rustで解く！問題解説

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

A 問題

問題

https://atcoder.jp/contests/abc412/tasks/abc412_a

解説

$N$ 日間のデータについて、目標タスク数より多くタスクが完了できた日数を求める問題です。
各日について、目標タスク数 $A_i$ と完了タスク数 $B_i$ が与えられます。
条件 $A_i < B_i$ を満たす日数をカウントし、その結果を出力します。

コード

abc412a.rs

use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 日数
        ab: [(usize, usize); n], // 各日の目標タスク数と完了タスク数
    }

    // 条件 a < b を満たす日数をカウント
    let mut cnt = 0;
    for &(a, b) in &ab {
        if a < b {
            cnt += 1;
        }
    }

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

B 問題

問題

https://atcoder.jp/contests/abc412/tasks/abc412_b

解説

文字列 $S$ が以下の条件を満たすかを判定する問題です。

• 文字列 $S$ の2文字目以降の各英大文字について、その直前の文字が文字列 $T$ に含まれる文字か

文字列 $T$ に含まれる文字の集合を HashSet というデータ構造を用いて集合として保持します。その後、文字列 $S$ を先頭から順に調べます。2文字目以降で大文字を見つけた場合、その直前の文字が集合に含まれるかを判定します。
すべて条件を満たした場合は Yes 、そうでない場合は、 No を出力します。

コード

abc412b.rs

use proconio::{input, marker::Chars};
use std::collections::HashSet;

fn main() {
    // 入力
    input! {
        s: Chars, // 文字列 S
        t: Chars, // 文字列 T
    }

    // 文字列 T の各文字を集合として保持
    let mut t_set = HashSet::new();
    for &ch in &t {
        t_set.insert(ch);
    }

    // 文字列 S の2文字目以降を探索
    for i in 1..s.len() {
        // 大文字の場合に条件をチェック
        if s[i].is_uppercase() {
            // 直前の文字が T に含まれていない場合は "No"
            if !t_set.contains(&s[i - 1]) {
                println!("No");
                return;
            }
        }
    }

    // 条件をすべて満たしている場合は "Yes"
    println!("Yes");
}

C 問題

問題

https://atcoder.jp/contests/abc412/tasks/abc412_c

解説

$N$ 個のドミノを倒す際に、間に挿入するドミノの個数を最小化することを求める問題です。ドミノの倒し方は以下の条件に従います。

• 現在倒しているドミノの値を $S_i$ とするとき、その右隣にあるドミノの値が $2S_i$ 以下ならそのドミノを倒すことができます。

考え方としては、現在倒しているドミノで末尾のドミノを倒せる場合は末尾のドミノを倒して即座に終了し、そうでない場合は間にドミノを追加していけばよいです。
解法としては、以下の通りになります。

1. 現在倒しているドミノで末尾のドミノを倒せるかを確認します。
2. 倒せる場合は、末尾のドミノを倒して終了します。
3. 倒せない場合は、現在倒しているドミノの値の $2S_i$ 以下で最も大きいドミノを選びます。このとき、選ぶドミノは先頭と末尾以外の値から選びます。
4. 選んだドミノを倒した後、再び1～3を繰り返します。

3.で選ぶドミノは並び順や選び方に指定がないため、先頭と末尾以外の値を昇順にして選ぶことができます。そのため、先頭と末尾以外の値を昇順にソートしておくことで二分探索を用いて効率的に選ぶことができます。
なお、3.で挿入できるドミノが見つからない場合は、末尾のドミノを倒すことが不可能であるため、-1 を出力します。

コード

abc412c.rs

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

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

fn solve() {
    // 入力
    input! {
        n: usize, // ドミノの個数
        mut s: [usize; n], // ドミノの値
    }

    // 現在のドミノ、末尾のドミノの値を初期化
    let mut cur = s[0];
    let last = s[n - 1];

    // 中間の要素のみを取り出して昇順にソート
    let s = extract_and_sort_middle(n, s);

    // 挿入した中間ドミノの個数
    let mut cnt = 0;

    loop {
        // 現在のドミノで末尾のドミノを倒せる場合
        if cur * 2 >= last {
            // 挿入した中間ドミノの個数 + 最初 + 最後を出力
            println!("{}", cnt + 2);
            return;
        }

        // curの2倍以下で最も大きい値を探す
        let pos = below_bound(&s, cur * 2);

        // 見つからない、または更新されない場合は-1を出力
        if pos == INF || s[pos] <= cur {
            println!("-1");
            return;
        }

        // 選んだ値を現在のドミノに設定
        cur = s[pos];
        cnt += 1;
    }
}

// 中間の要素を取り出して昇順にソートする関数
fn extract_and_sort_middle(
    n: usize, // ドミノの個数
    s: Vec<usize>, // ドミノの値
) -> Vec<usize> {
    let mut middle = Vec::new();
    for i in 1..n - 1 {
        middle.push(s[i]);
    }
    middle.sort();
    middle
}

// 二分探索
// x以下の最大のposを返す。0番目より小さい値では異常値として、「1<<60」を返す
pub fn below_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize {
    let mut l = 0;
    let mut r = vec.len();
    while r - l > 0 {
        let m = (l + r) / 2;
        if vec[m] <= val {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if l == 0 { INF } else {l-1}
}

D 問題

問題

https://atcoder.jp/contests/abc412/tasks/abc412_d

解説

入力で与えられた単純無向グラフ $G$ を、すべての頂点の次数が2である単純無向グラフ $G'$ に変換する際に必要な辺の操作（追加または削除）の最小回数を求める問題です。

すべての頂点の次数が2であるグラフは、閉路（サイクル）を形成します。この条件を満たすには、辺の数がちょうど $N$ 本である必要があります。
入力の制約より、Nが最大のケースでも、${}_{28} C_8 \simeq 3 \times 10^6$ 程度のパターンしかないため、辺のパターンを全探索することで解くことができます。
そのため、以下の手順で解を求めることができます。

1. $N$ 頂点の単純無向グラフで考えられるすべての辺の中から、任意の $N$ 本を選びます。
2. 選んだ辺でグラフを構築し、すべての頂点の次数が2であるかを判定します。
3. 条件を満たす場合、元のグラフ $G$ と構築したグラフ $G'$ を比較し、必要な辺の操作回数を計算します。
4. すべてのパターンを試し、操作回数の最小値を求めます。

コード

abc412d.rs

use proconio::{input, marker::Usize1};
use std::cmp::min;
const INF: usize = 255;
fn main() {
    // 入力
    input! {
        n: usize, m: usize, // 頂点数、入力の辺の本数
        ab: [(Usize1, Usize1); m], // 入力の辺リスト
    }

    // 入力の無向グラフを隣接行列として作成
    let input_graph = make_input_graph(ab, n);

    // 無向グラフとして考えられる辺のリストを作成
    let edge_list = make_edge_list(n);
    let edge_count = n * (n - 1) / 2; // 辺の総数

    // 再帰的に辺を選び、最小操作回数を求める
    let mut ans = INF;
    rec(0, n, 0, edge_count, &edge_list, &mut vec![], &input_graph, &mut ans);

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

// 入力の無向グラフを隣接行列として作成
fn make_input_graph(
    edges: Vec<(usize, usize)>, // 入力の辺リスト
    n: usize // 頂点数
) -> Vec<Vec<bool>> {
    let mut graph = vec![vec![false; n]; n];
    for (a, b) in edges {
        graph[a][b] = true;
        graph[b][a] = true;
    }
    graph
}

// 無向グラフとして考えられる辺のリストを作成
fn make_edge_list(
    n: usize // 頂点数
) -> Vec<(usize, usize)> {
    let mut edges = vec![(0, 0); 1]; // 0番目はダミー
    for i in 0..n {
        for j in i + 1..n {
            edges.push((i, j));
        }
    }
    edges
}

// 再帰的に辺を選び、最小操作回数を求める
fn rec(
    cur_cnt: usize, // 現在選択した辺の数
    n: usize,       // 必要な辺の数
    cur_idx: usize, // 現在の辺のインデックス
    edge_count: usize, // 辺の総数
    edge_list: &Vec<(usize, usize)>, // 辺のリスト
    selected_edges: &mut Vec<usize>, // 選択した辺のインデックス
    input_graph: &Vec<Vec<bool>>,    // 入力のグラフ
    ans: &mut usize,      // 最小操作回数
) {
    if cur_cnt == n {
        // グラフを構築
        let cur_graph = make_graph(selected_edges, edge_list, n);
        // 次数がすべて2かを判定
        if is_valid_graph(&cur_graph, n) {
            // 条件を満たす場合、操作回数を計算
            let operations = calculate_operations(input_graph, &cur_graph, n);
            *ans = min(*ans, operations);
        }
        return;
    }

    for i in cur_idx+1..=edge_count {
        selected_edges.push(i);
        rec(cur_cnt + 1, n, i, edge_count, edge_list, selected_edges, input_graph, ans);
        selected_edges.pop();
    }
}

// 選択した辺でグラフを構築
fn make_graph(
    selected_edges: &Vec<usize>, // 選択した辺のインデックス
    edge_list: &Vec<(usize, usize)>, // 辺のリスト
    n: usize // 頂点数
) -> Vec<Vec<bool>> {
    let mut graph = vec![vec![false; n]; n];
    for &idx in selected_edges {
        let (u, v) = edge_list[idx];
        graph[u][v] = true;
        graph[v][u] = true;
    }
    graph
}

// グラフがすべての頂点の次数が2であるかを判定
fn is_valid_graph(
    graph: &Vec<Vec<bool>>, // グラフの隣接行列
    n: usize // 頂点数
) -> bool {
    let mut degree = vec![0; n];
    for i in 0..n {
        for j in i+1..n {
            if graph[i][j] {
                degree[i] += 1;
                degree[j] += 1;
            }
        }
    }
    degree.iter().all(|&d| d == 2)
}

// 入力のグラフと現在のグラフを比較し、操作回数を計算
fn calculate_operations(
    input_graph: &Vec<Vec<bool>>, // 入力のグラフ
    cur_graph: &Vec<Vec<bool>>, // 現在のグラフ
    n: usize // 頂点数
) -> usize {
    let mut operations = 0;
    for i in 0..n {
        for j in i + 1..n {
            if input_graph[i][j] != cur_graph[i][j] {
                operations += 1;
            }
        }
    }
    operations
}