はじめに
AtCoder Beginner Contest 265 の C問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたらいいねいただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。
なぜやるのか
プログラミングは知っているけれどアルゴリズムは知らない、という方に向けて書いています。半分は社内向けです。
また、私は Rust に慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)
問題
A - Apple (Difficulty 18)
B - Explore (Difficulty 152)
C - Belt Conveyor (Difficulty 212)
D - Iroha and Haiku (New ABC Edition) (Difficulty 727)
E - Warp (Difficulty 1531)
F - Manhattan Cafe (Difficulty 2290)
G - 012 Inversion (Difficulty 2436)
Ex - No-capture Lance Game (Difficulty 3319)
前提
この記事にあるコードはこちらを 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 - Apple
りんごが
- 1個で $X$ 円
- 3個で $Y$ 円
のときに、ちょうど $N$ 個手に入れるときの最低金額を求める問題です。
ちょうど $N$ 個手に入れるには2通りあって、
- $X$ 円で $N$ 個買う
- $Y$ 円でかって、あまりを $X$ 円で買う
の2通りです。
たとえばりんごが 10個のときは
- $X$ 円で 10個 → ($10X$円)
- $Y$ 円で 3セットと、$X$円で 1個 → ($3Y + X$円)
の 2通りになります。
このふたつの金額を比べれば答えがわかります。
コードはこのようになりました。
input! {
x: usize,
y: usize,
n: usize,
}
let x_only = x * n;
let mixed = n / 3 * y + x * (n % 3);
println!("{}", min(x_only, mixed));
B - Explore
洞窟を探索する問題です。
問題設定が少し複雑ですね。
考察
問題文を言い換えてみます。
部屋が $N$ 個ならんでいて、部屋を進むと $A$ の時間を使います。
また、ボーナス部屋に着くと時間が増えます。
はじめの持ち時間が $T$ のときに、最後の部屋に着くことはできますか？
と言い換えてみました。
問題設定が複雑ですが、理解すれば実装できそうですね。素直に実装すると計算量は $O(N)$ となります。制約より $2 \le N \le 10^5$ なので、実行時間制限も大丈夫そうです。
実装
ボーナス部屋について、サイズ $M$ の vec で受け取ることになりますが、このままだと少し扱いにくいです。
そのため、bonus[i] = 部屋 i についた時にもらえるボーナス として、サイズ $N$ の vec としています。
残り時間を計算するときに usize 同士の引き算がでてくるのですが、計算結果が負になるとエラーになるので注意してください。
コードはこのようになりました。
input! {
n: usize,
m: usize,
mut t: usize,
a: [usize; n - 1],
xy: [(Usize1, usize); m],
}
// bonus[i] = 部屋 i についた時にもらえるボーナス
let mut bonus = vec![0; n + 1];
for (x, y) in xy {
bonus[x] = y;
}
for i in 0..n-1 {
if t <= a[i] { // 先に t - a[i] をすると、型が usize なのに負になって実行時エラーになるので注意
println!("No");
return;
}
t -= a[i]; // i から i+1 に移動する
t += bonus[i + 1]; // 部屋 i+1 のボーナスをもらう
}
println!("Yes");
C - Belt Conveyor
グリッド上を移動する問題ですね。はじめは (0, 0) にいて、マスの文字によって移動先が変わります。
移動し続けて、どこかのマスにとまればその位置を出力します。
永遠に移動し続けるときは -1 を出力します。
考察
2パターンあるので、分けて考えましょう。
どこかのマスに止まるパターン
以下のような場合ですね。
左側に今回の問題の形式、右側に矢印に直したものを書いてみます。
RD | →↓
RD | →↓
この場合は右下のマスに止まるので、(1, 1) と出力します。移動できなくなったら終了なので、なんとなく実装できそうです。
永遠に移動し続けるパターン
以下のようなパターンですね。
RD | →↓
UL | ↑←
これは動き続けるので、さきほどのような、明確な終了条件がありません。考察が必要です。
ここでキーになるのは、どのルートを動くかです。試してみるとわかりますが、同じところを動き続けますね。これを言い換えると、同じマスに2回以上きたときはループすると言えます。マスA からマスB へ向かうルートがあって、マスB からマスA へ向かうルートがあれば、それはループしますね。
なので、「同じマスに2回以上きたかどうか」を判定します。
これが難しいというときは、「マスは最大でも 250000 なので、300000回くらい移動してみて、まだ移動していたら
-1を出力し、止まっていたらいまの座標を出力する」という解き方もあります。
気になるのは計算量ですが、すべてのマスを動いたときは $H * W$ マス移動することになるので $O(H*W)$ です。
制約より $1 \le H, W \le 500$ なので、実行制限時間内に間に合いそうなことがわかります。
実装
移動してみて、同じマスに来たら -1 を出力し、移動できなかったら今いるマスを出力します。なので、「いまどこにいるか」と「来たことのあるマスか」の情報が必要ですね。
「いまどこにいるか」は整数、「来たことのあるマスか」は2次元vec でもってみました。
移動する部分はいろいろ書き方がありますが match で書いてみました。
コードはこのようになります。
input! {
h: usize,
w: usize,
mp: [Chars; h],
}
let mut come = vec![vec![false; w]; h];
let mut y = 0;
let mut x = 0;
loop {
match mp[y][x] { // マスの文字を見て移動する
'U' if y > 0 => { y -= 1 },
'D' if y < h - 1 => { y += 1 },
'L' if x > 0 => { x -= 1 },
'R' if x < w - 1 => { x += 1 },
_ => break, // 移動先がなかった
}
if come[y][x] { // 同じマスに 2回来た
println!("-1");
return;
}
come[y][x] = true; // (y, x) のマスに来た
}
println!("{} {}", y + 1, x + 1);
最後まで読んでいただきありがとうございます！