はじめに
AtCoder Beginner Contest 293 の C問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたらいいねいただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。
なぜやるのか
プログラミングは知っているけれどアルゴリズムは知らない、という方に向けて書いています。半分は社内向けです。
また、私は Rust に慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)
問題
A - Swap Odd and Even (Difficulty 12)
B - Call the ID Number (Difficulty 65)
C - Make Takahashi Happy (Difficulty 431)
D - Tying Rope (Difficulty 830)
E - Geometric Progression (Difficulty 1453)
F - Zero or One (Difficulty 2038)
G - Triple Index (Difficulty 1753)
Ex - Optimal Path Decomposition (Difficulty 2831)
前提
この記事にあるコードはこちらを import しています。
#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars, marker::Usize1};
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BTreeSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use itertools::Itertools;
A - Swap Odd and Even
入力された文字列を入れ替える問題ですね。
入れ替え方が独特で、
- 1文字目と2文字目
- 3文字目と4文字目
- ...
という入れ替え方をします。
入力を mut でもらったあと、 swap を使って入れ替えることで実装できました。
input! {
mut s: Chars
};
for i in 0..s.len() / 2 {
s.swap(i * 2, i * 2 + 1);
}
println!("{}", s.into_iter().join(""));
B - Call the ID Number
ちょっと複雑な問題ですね。
実際にシミュレーションをしてみれば問題概要がわかるかと思います。
また、この問題は効率的な解き方が浮かびにくいかもしれませんが、そういうときは愚直にシミュレーションをすると解けたりします。
実際にこの問題もシミュレーションで解きます。
ひとりずつ順番に見ていけばシミュレーションができるので、計算量は $O(N)$ になります。十分間に合います。
コードはこのようになりました。
input! {
n: usize,
a: [Usize1; n]
};
// 1 だったら呼ばれていない
let mut res = vec![1; n];
for i in 0..n {
// 呼ばれていなければ
if res[i] == 1 {
// a[i]番目 の人を呼ぶ
res[a[i]] = 0;
}
}
// 呼ばれていない人数
println!("{}", res.iter().sum::<usize>());
// 呼ばれていない人の番号
for i in 0..n {
if res[i] == 1 {
println!("{}", i + 1);
}
}
C - Make Takahashi Happy
グリッド上を動きながら、同時に数字を管理する問題ですね。
AtCoder ではこのようなグリッドを扱う問題はよく出ます。
計算量を考えてみます。まずは全探索から。
取り得るルートを列挙してみると、 $H = 10, W = 10$ の時に最大となって、 $C(H + W - 2, W - 1) = C(18, 9) = 48620$ 通りです。
今回の問題はそれに加えて整数の重複判定もあるのですが、これに $O((H + W)^2)$ かかるとして、 $C(18, 9) * 20^2 = 19448000$ ステップです。
実際は重複判定の部分が $(H + W)^2$ よりも小さくなるので、全探索で十分に間に合う計算量になりました。
続いて実装です。グリッドでの全探索は DFS や BFS をよく使います。今回も例に漏れずDFSを使います。
DFS といえば再帰ですね。もしくは while と vec を使っても実装できます。今回は再帰でやりました。
while と vec を使うときは、ループ部分でこのようにするとスマートです
while let Some(val) = vec.pop() {
...
}
コードはこのようになりました。
fn dfs(y: usize, x: usize, mp: &Vec<Vec<usize>>, stack: &mut Vec<usize>) -> usize {
// 枝刈り
// 見たことある数字だったら return
if stack.contains(&mp[y][x]) {
return 0;
}
let h = mp.len();
let w = mp[0].len();
// 端まで来た
if y == h - 1 && x == w - 1 {
return 1;
}
// いまのグリッドの整数を stack にいれる
stack.push(mp[y][x]);
let mut ret = 0;
// 下
if y < h - 1 {
ret += dfs(y + 1, x, mp, stack);
}
// 右
if x < w - 1 {
ret += dfs(y, x + 1, mp, stack);
}
// いまのグリッドから抜けるときに、
// この回で stack に入れた整数 (mp[y][x]) を抜く
stack.pop();
ret
}
#[fastout]
fn main() {
input! {
h: usize,
w: usize,
mp: [[usize; w]; h]
};
let mut stack = vec![];
println!("{}", dfs(0, 0, &mp, &mut stack));
}
最後まで読んでいただきありがとうございます！