👨🍳
ABC405:Rustで解く！問題解説
AtCoder Beginner Contest 405のA~E問題をRustで解いた際の解法をまとめました。
A問題
問題
解説
与えられた値
以下表の条件に従って判定します。
| X | 判定対象の R の範囲 |
|---|---|
| 1 | |
| 2 |
コード
abc405a.rs
use proconio::input;
fn main() {
// 入力
input! {
r: usize, // レート
x: usize, // 条件
}
let mut is_rated = false;
// xに応じて、対象範囲のレートかどうかを判定
if x == 1 {
if 1600 <= r && r <= 2999 {
is_rated = true;
}
} else {
if 1200 <= r && r <= 2399 {
is_rated = true;
}
}
// 出力
println!("{}", if is_rated { "Yes" } else { "No" });
}
B問題
問題
解説
数列
以下1~3の処理を行うことで解くことができます。
- 数列
A M - 数列
A M - 揃っていない状態になった時点で、取り出した回数を出力します。
コード
abc405b.rs
use proconio::{input, marker::Usize1};
fn main() {
// 入力
input! {
n: usize, m: usize,
mut a: [Usize1; n], // 0-indexに変換
}
// 初めから 0~M-1 の値がすべて揃っていない場合は0
if not_all(&a, m) {
println!("{}", 0);
return;
}
// 1つずつ末尾を取り出す
for cnt in 1..=n {
a.pop();
// 0~M-1 の値がすべて揃っていない場合は取り出した回数を出力
if not_all(&a, m) {
println!("{}", cnt);
return;
}
}
}
// 数列 a が 0~M-1 の値をすべて揃っていないかを判定
fn not_all(a: &Vec<usize>, m: usize) -> bool {
let mut has_cnt = 0;
let mut has_value = vec![false; m];
for &aa in a {
if aa >= m {
continue;
}
// 初めて現れた値の場合
if !has_value[aa] {
has_value[aa] = true;
has_cnt += 1;
}
}
// M 個すべて揃っていない場合は true を返す
has_cnt != m
}
C問題
問題
解説
以下の値を求める問題です。
ただし、
まず、
また、この部分和は累積和を用いることで効率的に計算できます。具体的には、以下のように計算します。
ここで、
したがって、問題文の式は次のように変形できます。
この式を用いることで、累積和を計算しながら
コード
abc405c.rs
use proconio::input;
fn main() {
// 入力
input! {
n: usize,
a: [usize; n],
}
// 配列 a の累積和を計算
let mut acc_a = vec![0; n + 1];
for i in 0..n {
acc_a[i + 1] = acc_a[i] + a[i];
}
// 答えを計算
let mut ans = 0;
for i in 0..n {
// A[i] * (累積和の差分) を加算
let ret = a[i] * (acc_a[n] - acc_a[i + 1]);
ans += ret;
}
// 出力
println!("{}", ans);
}
D問題
問題
解説
各マスから最寄りの出口 E までの経路を出力する問題です。
この問題は、出口 E 全てを起点とする幅優先探索（BFS）を用いることで効率的に解くことができます。解法の手順は以下1~4の通りです。
- 出口
Eの座標をすべてキューに追加します。 - キューから座標を取り出し、まだ移動していない通路
.に移動します。 - 移動時に、移動した方向と反対の向きを出口への経路として記録し、移動後の座標をキューに追加します。
- 移動可能な通路
.がなくなるまで繰り返し、最後に経路を出力します。
コード
abc405d.rs
use proconio::{input, marker::Chars};
use std::collections::VecDeque;
const INF: usize = 1 << 60;
// 上、左、下、右の移動方向と、それに対応する経路記号
const D4: [(usize, usize, char); 4] =
[(!0, 0, 'v'), (0, !0, '>'), (1, 0, '^'), (0, 1, '<')];
fn main() {
// 入力
input! {
h: usize, w: usize,
s: [Chars; h],
}
// 出口 ('E') の座標リストを取得
let elist = get_exit_positions(&s, h, w);
// BFS の実行
let route = bfs(&elist, h, w, &s);
// 出力
print_grid(&route, h, w);
}
// 出口 ('E') の座標リストを取得
fn get_exit_positions(s: &Vec<Vec<char>>, h: usize, w: usize) -> Vec<(usize, usize)> {
let mut elist = Vec::new();
for i in 0..h {
for j in 0..w {
if s[i][j] == 'E' {
elist.push((i, j));
}
}
}
elist
}
// 出口情報を初期化
fn initialize_exit_info(
dq: &mut VecDeque<(usize, usize)>,
route: &mut Vec<Vec<char>>,
dist: &mut Vec<Vec<usize>>,
elist: &Vec<(usize, usize)>
){
for &(ex, ey) in elist {
dq.push_back((ex, ey));
route[ex][ey] = 'E';
dist[ex][ey] = 0;
}
}
// 幅優先探索 (BFS)
fn bfs(
elist: &Vec<(usize, usize)>,
h: usize, w: usize, s: &Vec<Vec<char>>
) -> Vec<Vec<char>> {
// キュー
let mut dq = VecDeque::new();
// 経路
let mut route = vec![vec!['#'; w]; h];
// 最短距離
let mut dist = vec![vec![INF; w]; h];
// 出口情報を初期化
initialize_exit_info(&mut dq, &mut route, &mut dist, &elist);
while let Some((cx, cy)) = dq.pop_front() {
// 4方向に移動
for &(dx, dy, dir) in &D4 {
let nx = cx.wrapping_add(dx);
let ny = cy.wrapping_add(dy);
// 範囲外または通路でない場合はスキップ
if nx >= h || ny >= w || s[nx][ny] != '.' { continue; }
// まだ移動していない通路の場合
if dist[nx][ny] == INF {
dq.push_back((nx, ny));
route[nx][ny] = dir;
dist[nx][ny] = dist[cx][cy] + 1;
}
}
}
route
}
// グリッドを出力
fn print_grid(route: &Vec<Vec<char>>, h: usize, w: usize) {
for i in 0..h {
for j in 0..w {
print!("{}", route[i][j]);
}
println!();
}
}
E問題
問題
解説
4種類の果物（リンゴ
- リンゴはすべて、バナナよりも左側に並べる。
- リンゴはすべて、ブドウよりも左側に並べる。
- オレンジはすべて、ブドウよりも左側に並べる。
解法としては、上の3つのルールをうまく組み合わせつつ、4種類の果物を1種類ずつ配置することで正しく答えを求めることができます。具体的には、以下1~3の順に果物を配置して考えます。
- オレンジ、ブドウを配置 → 3番目のルールを適応
- リンゴを配置 → 2番目のルールを適応
- バナナを配置 → 1番目のルールを適応
1.オレンジとブドウの配置
オレンジはすべてブドウよりも左側に配置されるため、オレンジを左側にすべて配置し、その後にブドウを右側にすべて配置します。この配置の組み合わせは常に1通りです。
2.リンゴの配置
リンゴはすべてブドウよりも左側に配置される必要があります。したがって、リンゴはオレンジの前後または間に挿入される形になります。この配置方法は、オレンジとリンゴを自由に並べるのと等しく、組み合わせの数は
3.バナナの配置
バナナはすべてリンゴよりも右側に配置される必要があります。リンゴの最も右側の位置を考慮しながら、バナナを配置します。具体的には、以下のように計算します。
- リンゴの最も右側の1個を固定し、その位置をオレンジの前から
i - 残りのリンゴ
A-1 B_i \binom{A-1+B_{i}}{A-1} - バナナ
C (B-B_{i}) D \binom{B-B_i+D+C}{C} - この2つの積が、オレンジの前から
i
- 残りのリンゴ
3について、すべての挿入位置について計算し、総和を取ることで並べ方の総数を求めます。
コード
abc405e.rs
use proconio::input;
const MOD: usize = 998244353;
fn main() {
// 入力
input! {
a: usize, // リンゴの個数
b: usize, // オレンジの個数
c: usize, // バナナの個数
d: usize, // ブドウの個数
}
// 組み合わせを求めるための階乗計算を初期化
let mut comb = CalcCombMod::new(a + b + c + d, MOD);
comb.precompute();
let mut ans = 0;
// オレンジとブドウを先に固定。最も右側に置くリンゴについて、オレンジとの挿入位置を全探索
for b_i in 0..=b {
// リンゴ1個は固定。残りのリンゴa-1個とオレンジb_i個から、リンゴを置く組み合わせ
let v1 = comb.get_comb(b_i + a - 1, a - 1);
// 上で置いていないオレンジ(b-b_i個) + ブドウd個 + バナナc個から、バナナを置く組み合わせ
let v2 = comb.get_comb(b - b_i + d + c, c);
// v1、v2の積を加算
ans += (v1 * v2) % MOD;
ans %= MOD;
}
// 出力
println!("{}", ans);
}
struct CalcCombMod {
n: usize,
fact: Vec<usize>,
ifact: Vec<usize>,
mods: usize,
}
impl CalcCombMod {
// 初期化
pub fn new(n: usize, mods: usize) -> Self {
let fact = vec![1; n + 1];
let ifact = vec![1; n + 1];
CalcCombMod { n, fact, ifact, mods }
}
// 階乗と逆元を事前計算
pub fn precompute(&mut self) {
for i in 1..=self.n {
self.fact[i] = self.fact[i - 1] * i % self.mods;
}
self.ifact[self.n] = self.mod_pow(self.fact[self.n], self.mods - 2);
for i in (1..self.n).rev() {
self.ifact[i] = self.ifact[i + 1] * (i + 1) % self.mods;
}
}
// 繰り返し二乗法
fn mod_pow(&self, mut base: usize, mut exp: usize) -> usize {
let mut result = 1;
while exp > 0 {
if exp % 2 == 1 {
result = result * base % self.mods;
}
base = base * base % self.mods;
exp /= 2;
}
result
}
// 組み合わせの値 (nCr) を返す
pub fn get_comb(&self, n: usize, r: usize) -> usize {
if n > self.n || r > self.n || r > n { return 0; }
let mut ret = self.fact[n];
ret *= self.ifact[r]; ret %= self.mods;
ret *= self.ifact[n-r]; ret %= self.mods;
ret
}
}
Discussion