ABC404:Rustで解く！問題解説
AtCoder Beginner Contest 404のA~E問題をRustで解いた際の解法をまとめました。
A問題
問題
解説
この問題は、英小文字 a から z のうち、文字列
文字列
- 英小文字
aからzの26種類の各文字について、それが含まれているかどうかを記録するためのbool配列を用意します。 - 入力文字列
S trueに設定します。文字aのインデックスは0、bは1、...、zは25となるように計算します。 - 配列を順に確認し、
falseになっているインデックスを見つけたら、それに対応する文字を出力します。
コード
use proconio::{input, marker::Chars};
const MOJI_SZ : usize = 26; // アルファベットの数
const LOWER_ASCII: usize = 0x61; // 'a' のASCIIコード
fn main() {
// 入力
input! {
s: Chars,
}
// a~zの各文字の出現有無を記録する配列
let mut moji = vec![false; MOJI_SZ];
// 入力文字列に含まれている文字を記録
for ch in s {
let idx = ch as usize - LOWER_ASCII;
moji[idx] = true;
}
// 含まれていない文字を探して出力
for idx in 0..MOJI_SZ {
if !moji[idx] {
let c = (idx + LOWER_ASCII) as u8 as char;
println!("{}", c);
return;
}
}
}
B問題
問題
解説
この問題では、グリッド
- グリッド
S .」→「#」または「#」→「.」に変更する。 - グリッド
S
まず、90度回転を任意回数（最大3回）行い、その後、グリッド
したがって、以下1~3の手順で解きます。
- 回転回数を0～3回試す。
- 各回転状態で、グリッド
S T - 「回転回数 + 一致しないマスの個数」の合計値を計算し、その最小値を求める。
コード
use proconio::{input, marker::Chars};
use std::cmp::min;
use std::mem::swap;
const INF: usize = 1 << 60;
fn main() {
// 入力
input! {
n: usize,
mut s: [Chars; n],
t: [Chars; n],
}
let mut ans = INF;
// 回転回数を0～3回試す
for rot_cnt in 0..4 {
// グリッドSとTを比較して一致しないマスの個数を計算
let mis_cnt = get_mismatch_cnt(n, n, &s, &t);
// 回転回数 + 一致しないマスの個数を操作回数として最小値を更新
ans = min(ans, rot_cnt + mis_cnt);
// グリッドを90度右に回転
rotate_grid(n, n, &mut s, false);
}
// 結果を出力
println!("{}", ans);
}
// グリッドSとTの一致しないマスの個数を計算
fn get_mismatch_cnt(h: usize, w: usize, s: &Vec<Vec<char>>, t: &Vec<Vec<char>>) -> usize {
let mut cnt = 0;
for i in 0..h {
for j in 0..w {
if s[i][j] != t[i][j] {
cnt += 1;
}
}
}
cnt
}
fn rotate_grid(h: usize, w: usize, s: &mut Vec<Vec<char>>, isleft: bool){
// 右回転なら1度、左回転なら3度実施
let k = if isleft {3} else {1};
let mut ret = vec![vec!['.'; h]; w];
for _ in 0..k {
// 90度回転
for i in 0..h {
for j in 0..w {
ret[j][h - 1 - i] = s[i][j];
}
}
}
swap(s, &mut ret);
}
C問題
問題
解説
入力として与えられた
サイクルグラフ
- 頂点
1 N
具体的には、以下1~2の条件をすべて満たしているかを確認します。
- 各頂点の次数が
2 - 頂点
1 N
条件 2 の判定には Union-Find というデータ構造を使用すると効率的に判定できます。
コード
use proconio::{input, marker::Usize1};
use std::mem::swap;
fn main() {
// 入力
input! {
n: usize, m: usize,
ab: [(Usize1, Usize1); m],
}
// 隣接リストを作成
let graph = create_adjacency_list(n, &ab);
// 各頂点の次数が2であるかを確認
for i in 0..n {
if graph[i].len() != 2 {
println!("No");
return;
}
}
// Union-Findを用いて辺を連結
let mut uf = UnionFind::new(n);
for &(a, b) in &ab {
uf.merge(a, b);
}
// 全頂点が連結しているかを確認
if uf.size(0) != n {
println!("No");
} else {
println!("Yes");
}
}
// 隣接リストを作成する関数
fn create_adjacency_list(n: usize, edges: &Vec<(usize, usize)>) -> Vec<Vec<usize>> {
let mut adj_list = vec![Vec::new(); n];
for &(a, b) in edges {
adj_list[a].push(b);
adj_list[b].push(a);
}
adj_list
}
// Union-Find構造体
struct UnionFind {
size: Vec<usize>, // 各頂点の集合サイズ
parent: Vec<isize>, // 親情報
}
impl UnionFind {
// 初期化
fn new(n: usize) -> Self {
UnionFind { size: vec![1; n], parent: vec![-1; n] }
}
// 代表元を求める
fn find(&mut self, u: usize) -> usize {
if self.parent[u] == -1 {
return u;
}
let p = self.parent[u] as usize;
let root = self.find(p);
self.parent[u] = root as isize; // 経路圧縮
root
}
// 2つの集合を併合
fn merge(&mut self, u: usize, v: usize) -> bool {
let mut x = self.find(u);
let mut y = self.find(v);
if x == y {
return false; // 既に同じ集合
}
if self.size[x] < self.size[y] {
swap(&mut x, &mut y);
}
self.parent[y] = x as isize;
self.size[x] += self.size[y];
true
}
// 集合のサイズを取得
fn size(&mut self, u: usize) -> usize {
let root = self.find(u);
self.size[root]
}
}
D問題
問題
解説
問題の入力より、どの動物についても
以上を踏まえて、以下1~2の方針で解きます。
-
入力データの整理
各動物が見られる動物園の情報をもとに、各動物園で見られる動物のリストを作成します。この変換により、動物園を訪問した際にどの動物が見られるかを簡単に把握できるようになります。 -
3^N
各動物園の訪問パターンを全て試します。各訪問パターンをN桁の3進数で表現して、桁ごとの値分だけその動物園を訪れることとします。訪問した動物園で見られる動物の回数をカウントし、全ての動物を2回以上見ているかを判定します。条件を満たす場合は、その訪問パターンの入園料を計算し、最小値を更新します。全ての訪問パターンを試した後、最小の入園料を出力します。
コード
use proconio::{input, marker::Usize1};
use num::pow;
use std::cmp::min;
const INF: usize = 1 << 60;
fn main() {
// 入力
input! {
n: usize, // 動物園の数
m: usize, // 動物の数
c: [usize; n], // 各動物園の入園料
}
// 各動物が見られる動物園のリスト
let seen_list = input_seen_data(m);
// 各動物園で見られる動物リストを作成
let zoo_list = convert_zoo_list(&seen_list, n, m);
// 入園料の最小値
let mut ans = INF;
// 各動物園を0~2回選ぶ全探索
let sz = pow(3, n) as usize;
for state in 0..sz {
let mut cost = 0; // 現在の入園料
let mut seen = vec![0; m]; // 各動物の観覧回数
let convert_state = get_ternary_number(state, n); // 3進数に変換
for idx in 0..n {
let cnt = convert_state[idx]; // 動物園idxを訪れる回数
for &animal in &zoo_list[idx] {
seen[animal] += cnt; // 動物の観覧回数を加算
}
cost += cnt * c[idx]; // 入園料を加算
}
// 全ての動物が2回以上見ている場合、最小値を更新
if seen_complete(&seen) {
ans = min(ans, cost);
}
}
// 結果を出力
println!("{}", ans);
}
// 各動物が見られる動物園のリストを入力
fn input_seen_data(m: usize) -> Vec<Vec<usize>> {
let mut seen_list = vec![Vec::new(); m];
for i in 0..m {
input! {
k: usize, // 動物が見られる動物園の数
a: [Usize1; k], // 動物園のリスト
}
seen_list[i] = a;
}
seen_list
}
// 各動物園で見れる動物リストを作成
fn convert_zoo_list(seen_list: &Vec<Vec<usize>>, n: usize, m: usize) -> Vec<Vec<usize>> {
let mut zoo_list = vec![Vec::new(); n];
for i in 0..m {
for &place in &seen_list[i] {
zoo_list[place].push(i);
}
}
zoo_list
}
// 10進数をN桁の3進数に変換
fn get_ternary_number(mut state: usize, n: usize) -> Vec<usize> {
let mut ret = vec![0; n];
for i in 0..n {
ret[i] = state % 3;
state /= 3;
}
ret
}
// 全ての動物が2回以上見られているか判定
fn seen_complete(seen: &Vec<usize>) -> bool {
seen.iter().all(|&x| x >= 2)
}
E問題
問題
解説
この問題は、茶碗の中にある豆をゴール（左端の茶碗）まで動かす際の手数を最小化する問題です。
豆の動かし方についてですが、以下のように豆を動かすのが最適な操作となります。
- 豆を複数動かせる場合はまとめて同じ場所に動かす。
- 豆が置かれている箇所では必ず合流し、合流後はまとめて動かす。
1.について
1つの茶碗にある豆は、1度に何個動かしても1手と数えるルールになっています。そのため、1箇所の茶碗にある豆は全て取り出して移動させます。また、移動先も1箇所にまとめる方が望ましいため、全て同じ場所に動かすものと考えて問題ありません。
2.について
複数の茶碗に豆が置かれている場合、ゴール側にある茶碗の位置で合流させることで移動手数を最小化できます。その理由を以下に説明します。
図1のようにAとBの位置に豆がそれぞれ置かれている場合を考えます。
この2つの豆をゴール地点Gまで独立して最短手数で動かした場合、Aの豆は2手(赤い矢印の通りに動かす)、Bの豆は3手(青い矢印の通りに動かす)で合計5手必要になります。
図1
ここで、図2のように、Aの1手目の移動先をBの豆の経路上にあるXに変更すると、Xの地点で同時に動かすことができるようになり、合計4手に減らすことができます。(赤い矢印、青い矢印、緑の矢印の順に動かす)
図2
この合流地点Xですが、Aの豆の最短経路上であればさらに右側でもよく、Aの地点で合流をさせても、同じ手数で動かすことができます。(図3)
図3
よって、初めに豆が置かれている位置をチェックポイントとして、各区間での移動手数を最小化することで全体の移動手数を最小化することができます。なお、各区間での移動手数の最小化はBFS(幅優先探索)を用いて求められるため、各区間で求めた移動手数を合計して、全体の最小手数を求めます。
コード
use proconio::input;
use std::collections::VecDeque;
use std::cmp::max;
const INF: usize = 1 << 60;
fn main() {
// 入力
input! {
n: usize,
mut c: [usize; n - 1], // 各マス: 左側へ移動できるマス目の最大値
mut a: [usize; n - 1], // 各マス: 豆の個数
}
// 地点0の情報を追加
c.insert(0, 0);
a.insert(0, 1); // 地点0は豆が置かれているものと考える
// 初めに豆が置かれている位置をチェックポイントとして調べる
let check_points = get_check_points(n, &a);
let mut ans = 0;
// チェックポイント毎にBFS
for i in (0..check_points.len() - 1).rev() {
let from = check_points[i + 1];
let to = check_points[i];
// from -> toに動かすときの最小手数をBFSで求める
let cnt = bfs(from, to, n, &c);
// 各区間での最小手数を加算
ans += cnt;
}
// 出力
println!("{}", ans);
}
// 豆が置かれている位置（チェックポイント）を取得
fn get_check_points(n: usize, a: &Vec<usize>) -> Vec<usize> {
let mut ret = Vec::new();
for idx in 0..n {
if a[idx] != 0 {
ret.push(idx);
}
}
ret
}
// BFSで最小手数を計算
fn bfs(from: usize, to: usize, n: usize, c: &Vec<usize>) -> usize {
// 最小手数
let mut cost = vec![INF; n];
cost[from] = 0;
// キュー
let mut dq = VecDeque::new();
dq.push_back(from);
while let Some(cur) = dq.pop_front() {
// 地点0は移動が不要なので、抜ける
if cur == 0 {
break;
}
// [l~r]の間で移動
let mv_l = max(cur - c[cur], to);
let mv_r = cur - 1;
for next in mv_l..=mv_r {
if cost[next] == INF {
// 最小手数とキューを更新
cost[next] = cost[cur] + 1;
dq.push_back(next);
}
}
}
cost[to]
}
Discussion