ABC387:Rustで解く！問題解説

AtCoder Beginner Contest 387のA~D問題をRustで解いた際の解法をまとめました。

A問題

• 問題

https://atcoder.jp/contests/abc387/tasks/abc387_a

• 解説

$A + B$の二乗を計算します。

• コード

use proconio::input;
fn main() {
	input!{
		a: usize, b: usize,
	}
	println!("{}", (a+b)*(a+b));
}

B問題

• 問題

https://atcoder.jp/contests/abc387/tasks/abc387_b

• 解説

九九表で掛け算の結果が$X$になるもの以外を全て足し合わせます。

• コード

use proconio::input;
fn main() {
    input!{
		x: usize,
	}

	let mut ans = 0;
	for i in 1..=9 {
		for j in 1..=9 {
			let val = i*j;
			if val != x { ans += val; }
		}
	}
	println!("{}", ans);
}

C問題

• 問題

https://atcoder.jp/contests/abc387/tasks/abc387_c

• 解説

$L$以上$R$以下に含まれる個数は、①「$0$ ～ $R$に含まれる個数」 - ②「$0$ ～ $L-1$に含まれる個数」で求めることができます。
①②は各桁を分解し、以下の三つのケースに分けて数え上げていきます。

(1) 桁数が同じで、先頭桁と同じ値の場合
2桁目以降の値を順番に数え上げます。先頭桁の値を $A$、確定させた桁の値を $B$、残りの桁数を $C$ とすると、確定させた桁の値の選び方は $0$ ～ $B-1$ の $B$ 通り、残りの桁の値の選び方はそれぞれ $0$ ～ $A-1$ の $A$ 通りとなります。
したがって、$B \times A^C$ を数え上げていきます。

(2) 桁数が同じで、先頭桁より小さい値の場合
先頭桁の値は $1$ から $A-1$ の範囲で全て試します。
確定させた桁の値 $B$ を決めると、残りの桁の値の決め方はそれぞれ $0$ ～ $B-1$ の $B$ 通りになります。
これを $B$ を変化させながら、$B$ の(桁数-1)乗を数え上げていきます。

(3) 桁数が元の桁数より小さい場合
先頭桁の値を $0$ として桁を一つ落とすことで、先頭桁の値を自由に決めることができます。
桁を一つ以上落として先頭桁の値を $1$ ～ $9$ に決めた場合は(2)と同様に計算し、桁を落とした後の先頭桁の値が $0$ の場合は再度 $1$ ～ $9$ もしくは $0$ を再帰関数を使用して選択します。

• コード

use proconio::input;
use num::pow;

fn main() {
    input! {
        l: usize, r: usize,
    }
    
    // [l..r] = r以下の数 - l-1以下の数
    let cnt_r = calc_cnt(r);
    let cnt_l = calc_cnt(l - 1);
    println!("{}", cnt_r - cnt_l);
}

fn calc_cnt(mut x: usize) -> usize {
    // xを桁毎に分解
    let mut array_x = Vec::new();
    while x > 0 {
        array_x.push(x % 10);
        x /= 10;
    }
    array_x.reverse();
    let sz_x = array_x.len();

    // 桁毎に分解したxをへび数の最大値に修正
    let mut repair = false;
    for i in 1..sz_x {
        if repair || array_x[i] >= array_x[0] {
            array_x[i] = array_x[0] - 1; // 先頭桁より小さくする
            repair = true;
        }
    }

    let mut ret = 0;

    // (1) 桁数が同じで、先頭桁と同じ値の場合
    // 2桁目以降を順番に調べる
    for i in 1..=sz_x {
        // 最後の桁まで見た場合は、1通り加算
        if i == sz_x {
            ret += 1;
            break;
        }
        let now_digit = array_x[i]; // 現在の桁の値
        let rest_digits = pow(array_x[0], sz_x - 1 - i); // 残りの桁数
        ret += now_digit * rest_digits;
    }

    // (2) 桁数が同じで、先頭桁より小さい値の場合 
    let less_x = array_x[0] - 1; // 先頭桁より小さい値
    for i in 1..=less_x {
        ret += pow(i, sz_x - 1); // 残りの桁の全てを考慮
    }

    // (3) 桁数が元の桁数より小さい場合
    // 次の桁で1~9(B)を選択 → 残りの桁の値：0~B-1の各B通り
    // 次の桁で0を選択 → 再選択(再帰的に行う)
    fn rec(now: usize, digit: usize) -> usize {
        // 0以外を選択した場合
        if now != 0 {
            // 選択した値 ^ 残りの桁数
            return pow(now, digit);
        }
        // これ以上選択できない場合
        if digit == 0 {
            return 0;
        }
        // 0~9を選択
        let mut ret = 0;
        for i in 0..10 {
            ret += rec(i, digit - 1);
        }
        ret
    }
    
    ret += rec(0, sz_x - 1); // 0の場合の数え上げを追加

    // (1)~(3) の数え上げた結果を返す
    ret
}

D問題

• 問題

https://atcoder.jp/contests/abc387/tasks/abc387_d

• 解説

幅優先探索(BFS)を用いて問題を解決します。
移動の向きについては、初めに横移動を選んだ場合は「横→縦→横→・・・」、縦移動では「縦→横→縦→・・・」となります。
BFSを行う際、次に進む向きはスタート地点からの最短距離の偶奇に基づいて決定でき、偶数距離の場合は初期の移動向きと同じ、奇数距離の場合は異なる向きで移動することになります。

• コード

use proconio::{input, marker::Chars};
use std::collections::VecDeque;
use std::cmp::min;

const INF: i64 = 1 << 60;
const D4: [(usize, usize); 4] = [(!0, 0), (0, !0), (1, 0), (0, 1)]; // 上左下右

fn main() {
    input!{
        h: usize, w: usize,
        s: [Chars; h],
    }

    // スタート、ゴールを見つける
    let mut spos = (0, 0);
    let mut gpos = (0, 0);
    for i in 0..h {
        for j in 0..w {
            if s[i][j] == 'S' { spos = (i, j); }
            if s[i][j] == 'G' { gpos = (i, j); }
        }
    }

    let mut ans = INF;

    // 幅優先探索(横移動から開始、縦移動から開始の2つを試す)
    for i in 0..2 {
        ans = min(ans, bfs(spos, gpos, h, w, &s, i));
    }

    println!("{}", if ans == INF {-1} else {ans});
}

fn bfs(
    spos: (usize, usize), gpos: (usize, usize),
    h: usize, w: usize,
    s: &Vec<Vec<char>>,
    direction: usize, // 0:横移動、1:縦移動
) -> i64 {
    // 各地点までの最短距離
    let mut dist = vec![vec![INF; w]; h];
    dist[spos.0][spos.1] = 0;

    // キュー
    let mut dq = VecDeque::new();
    dq.push_back(spos);

    // BFSの開始
    while dq.len() > 0 {
        let cpos = dq.pop_front().unwrap();
        let turn = dist[cpos.0][cpos.1];

        for i in 0..4 {
            // 偶数ターンの移動は、開始時と同じ移動のみ
            if (turn % 2 == 0) && (i % 2 == direction % 2) { continue; }
            // 奇数ターンの移動は、開始時と異なる移動のみ
            if (turn % 2 == 1) && (i % 2 != direction % 2) { continue; }
            
            let nx = cpos.0.wrapping_add(D4[i].0);
            let ny = cpos.1.wrapping_add(D4[i].1);

            if nx >= h || ny >= w || s[nx][ny] == '#' { continue; }
            if dist[nx][ny] == INF {
                dist[nx][ny] = turn + 1;
                dq.push_back((nx, ny));
            }
        }
    }
    dist[gpos.0][gpos.1]
}