はじめに
AtCoder Beginner Contest 213 の E問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたら LGTM いただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。
なぜやるのか
コンテストから時間をあけて解きなおすことで、記憶へ定着すればいいなと思っています。
また、会社で Rust を使うのですが私はまだ慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)
目次
A - Bitwise Exclusive Or (Difficulty 33)
B - Booby Prize (Difficulty 26)
C - Reorder Cards (Difficulty 481)
D - Takahashi Tour (Difficulty 710)
E - Stronger Takahashi (Difficulty 1423)
前提
この記事にあるコードはこちらを import しています。
# [allow(unused_imports)]
use proconio::{input, fastout, marker::Chars};
# [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 - Bitwise Exclusive Or
XOR は排他的論理和という計算です。
Rust に限らず多くのプログラム言語では、XOR は ^ の演算子で計算できます。
今回は全探索をすれば答えがわかりますね。
もしくは、XORの性質から $A\ xor\ B$ を計算すれば答えがわかります。
fn main() {
input! {
a: usize,
b: usize
}
println!("{}", a ^ b);
}
B - Booby Prize
大きい方から2番目の値の「インデックス」を求める問題です。
値ではなくて「インデックス」な点が少し複雑です。
そのままソートをするとインデックスがわからなくなるので、 enumerate() でインデックスを追加しましょう。
enumerate() をすると、 (インデックス, 値) のペアになります。
そのうえで、sorted_by_key() を使って値でソートした後に、大きい方から2番目の値のインデックスを出力すれば答えがわかります。
インデックスは $0$ から始まるので、 +1 することに注意です。
fn main() {
input! {
n: usize,
mut a: [usize; n]
}
let a = a.into_iter()
.enumerate()
.sorted_by_key(|x| x.1)
.collect_vec();
println!("{}", a[n - 2].0 + 1);
}
C - Reorder Cards
座標圧縮をする問題ですね。
まずこの問題は、「縦方向の値」と「横方向の値」がお互いに影響しあうことはありません。つまり、縦方向と横方向で独立して考えることができます。
これは、「行に関する操作」と「列に関する操作」の順序に関わらず答えが一意に定まることからわかります。お互いに影響する場合は、操作の順序で答えが変わるためです。
なので、考えやすくするために「行に関する操作 (縦方向の操作)」をすべて終えた後、「列に関する操作 (横方向の操作)」をすることにします。
さて、行に関する操作、つまり、 $A_i$ に関する操作を考えます。この時に大事なのが、「値の大小関係」は変わらずに「値が小さくなっている」ことです。これは 座標圧縮 という操作になります。
座標圧縮は ABC036-C にそのままの問題と詳しい定義があるのでリンクを載せておきます。
私は座標圧縮をする関数を作って解きました。関数化すると他のコンテストでも使えるためです。座標圧縮を使って高速化するテクニックはよく出るので、関数化してとっておくのもオススメです。
下の実装にある compress() 関数で座標圧縮をしているので、これについて説明します。
まず、B問題と同様に enumerate() をしてから値でソートしています。
・ソートをするのは大小関係をはっきりさせるためです
・ソートをすると元の位置がわからなくなるので、enumerate() のインデックスで元の位置の情報を持たせています
後に続く for() 文で、大小関係を維持したまま値を小さくしています。
now は変換前の値で、 val は変換後の値です。
(インデックス, 値) の2番目(値)をキーにしてソートされているため、 (_, x) の x は小さい順に処理されます。
最後に sort() でインデックス順 (元の並び) に戻してから map() で値だけを抽出して、座標圧縮が完了しました。
続いて列に関する操作ですが、やることは行に関する操作と同じ処理で問題ありません。これは行と列は独立しているためです。
これで $A_i$ と $B_i$ が座標圧縮されたので、出力して答えになります。それぞれ +1 するので注意です。
fn compress(v: Vec<usize>) -> Vec<usize> {
let mut v = v.into_iter()
.enumerate()
.sorted_by_key(|val| val.1)
.collect_vec();
let mut now = v[0].1;
let mut val = 0_usize;
for (_, x) in v.iter_mut() {
if now != *x {
now = *x;
val += 1;
}
*x = val;
}
v.sort();
v.into_iter().map(|(_, x)| x).collect_vec()
}
fn main() {
input! {
_: usize,
_: usize,
n: usize,
ab: [(usize, usize); n]
}
let mut a = Vec::with_capacity(n);
let mut b = Vec::with_capacity(n);
for (_a, _b) in ab.into_iter() {
a.push(_a);
b.push(_b);
}
let a = compress(a);
let b = compress(b);
for i in 0..n {
println!("{} {}", a[i] + 1, b[i] + 1);
}
}
D - Takahashi Tour
オイラーツアーという名前の付いた数列を出力する問題です。
少しだけ手を加えますが、やることは DFS そのままです。これが解けると DFS に強くなれます。
DFS には再帰を使う方法と、 stack と while を使う方法があります。 今回は再帰で解きました。
再帰 DFS はグローバル変数が使えると楽なのですが、Rust にはありません (ですよね...?) 。
なので、再帰に必要な情報を引数で渡します。
あとは
・頂点番号の小さい順に訪れるために、あらかじめソートすること
・初めて頂点に来た時に出力
・他の頂点から帰ってくる時に出力
に気を付ければ答えになります。
fn dfs(now: usize, parent: usize, graph: &Vec<Vec<usize>>) {
print!("{} ", now + 1); // 初めて頂点に来た時に出力
for &next in graph[now].iter() {
if next == parent { continue; }
dfs(next, now, graph);
print!("{} ", now + 1); // 他の頂点から帰ってくる時に出力
}
}
fn main() {
input! {
n: usize,
ab: [(usize, usize); n - 1]
}
let mut graph = vec![vec![]; n];
for &(a, b) in ab.iter() {
graph[a - 1].push(b - 1);
graph[b - 1].push(a - 1);
}
for i in 0..n {
graph[i].sort(); // 頂点番号の小さい順に訪れるために、あらかじめソートすること
}
dfs(0, 0, &graph);
}
E - Stronger Takahashi
01BFS を使って解く問題です。
ABC176-D に似ています。これを知っていたので解けました。
移動には、コストの かからない 移動と、コストの かかる パンチがありますね。
コストをかけずに行けるところまでいって、移動できなくなったらパンチをするというのが最適ルートになります。
これをうまく扱うのが01BFSです。通常の BFS は queue を使いますが、 01BFS は deque を使います。
・コストのかからない移動は push_front()
・コストのかかる移動は push_back()
として、 pop_front() で BFS を進めるというアルゴリズムです。
こうすると、コストをかけずに行けるところまでいって、移動できなくなったら、コストをかけた移動をするという挙動を実現できます。
また、今回の問題では地形を変えられますが、地形の情報を BFS にのせると複雑になります。試していないですが、恐らくメモリ制限も超えてしまいます。なので、地形の情報を変えない方法を使います。
さて実装ですが、 dx, dy を使った BFS を拡張したものです。
2次元配列がでちゃっていて複雑に見えますね。py, px はパンチをした場合の移動先です。
パンチをした方向で移動できるマスが変わるので、このような実装になりました。
右を向いてパンチした場合 (dy[0] と dx[0] の場合) について説明します。
上の図で、白色が通路で、緑色が壁です。 ◎ のマスにいるときに右へいこうとすると壁があるので進めません。そのため、パンチします。◎ の位置でパンチをすると進める先は 0,1,2,3,4,5 の6か所ですね。その相対位置を py[0], px[0] で表しています。プログラムでの ny, nx が 2 の位置になるので、 2 の位置からの相対位置を表しています。
同様に、
・下は py[1], px[1]
・左は py[2], px[2]
・上は py[3], px[3]
で表しています。
不要かもしれませんが、変数名について書いておきます。
・dy は diff_y
・py は punch_y
・ny は next_y
のつもりです。
fn main() {
input! {
h: i32,
w: i32,
mp: [Chars; h]
}
// 右 下 左 上
let dy = [0, 1, 0, -1];
let dx = [1, 0, -1, 0];
let py = [
[-1, -1, 0, 0, 1, 1], // 右
[0, 0, 0, 1, 1, 1], // 下
[-1, -1, 0, 0, 1, 1], // 左
[-1, -1, -1, 0, 0, 0], // 上
];
let px = [
[0, 1, 0, 1, 0, 1], // 右
[-1, 0, 1, -1, 0, 1], // 下
[-1, 0, -1, 0, -1, 0], // 左
[-1, 0, 1, -1, 0, 1], // 上
];
let mut ans = vec![vec![100100100; w as usize]; h as usize];
let mut que = VecDeque::<(i32, i32, i32)>::new();
que.push_front((0, 0, 0));
ans[0][0] = 0;
while let Some((y, x, pt)) = que.pop_front() {
if y == h - 1 && x == w - 1 { // ゴールに来たら終了
println!("{}", pt);
break;
}
for i in 0..4 {
let ny = y + dy[i];
let nx = x + dx[i];
if ny < 0 || h <= ny { continue; }
if nx < 0 || w <= nx { continue; }
let ny = ny as usize;
let nx = nx as usize;
if ans[ny][nx] <= pt { continue; } // より低いコストで移動できないなら continue
if mp[ny][nx] == '.' { // 通路のとき
ans[ny][nx] = pt;
que.push_front((ny as i32, nx as i32, pt));
} else { // 壁のとき
for j in 0..6 {
let npy = ny as i32 + py[i][j];
let npx = nx as i32 + px[i][j];
if npy < 0 || h <= npy { continue; }
if npx < 0 || w <= npx { continue; }
let npy = npy as usize;
let npx = npx as usize;
if ans[npy][npx] <= pt + 1 { continue; } // より低いコストで移動できないなら continue
ans[npy][npx] = pt + 1;
que.push_back((npy as i32, npx as i32, pt + 1));
}
}
}
}
}
最後まで読んでいただきありがとうございます！