はじめに
私は最近 Rust を勉強しています。
Rust は以下のように人気のプログラミング言語です。
Rust は 2016–2022 年の間 Stack Overflow Developer Survey で「最も愛されているプログラミング言語」で一位を獲得し続けている。
Rust (プログラミング言語) - Wikipedia より
日本国内で Rust を採用している企業はまだ少ないかもしれませんが、今後増えていくと予想されます。
さて、大人気言語の Rust を paiza のスキルチェックでも使いたいのですが、2025 年 1 月現在、Rust はスキルチェック対応言語に含まれていません。
(※ キャンペーンの問題や、スキルチェック問題の再チャレンジでは Rust を選択できます)
最も愛されているプログラミング言語 なのに。不思議ですね。
今回は Rust で「電脳少女プログラミング2088 ─壊レタ君を再構築─」の対象問題を解き、paiza さんに Rust をスキルチェック対応言語に追加してほしい という思いを伝えたいと思います。
【電脳少女プログラミング2088-壊レタ君を再構築-】のコード問題を解く
入力について
Rust で paiza の問題を解く際、最初にぶつかる壁は入力の受け取りだと思います。
今回は hatoo@github さんが Rust で競技プログラミング スターターキット で公開されている get マクロを使った入力の受け取り方法を紹介します。
このマクロを使うと以下のように入力を受け取ることができます。
// 一行読み込み、空白で分解してusize２つパースする
let (n, q) = get!(usize, usize);
// usize usize u64 をq行読む Vec<(usize, usize,u64)>
let lrt = get!(usize, usize, u64; q);
// 一行読み込み、空白で分解して Vec<usize> を受け取る
let list = get!(usize;;);
// https://qiita.com/hatoo@github/items/fa14ad36a1b568d14f3e#%E5%85%A5%E5%8A%9B より引用
#[macro_export]
macro_rules! get {
($t:ty) => {
{
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.trim().parse::<$t>().unwrap()
}
};
($($t:ty),*) => {
{
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
let mut iter = line.split_whitespace();
(
$(iter.next().unwrap().parse::<$t>().unwrap(),)*
)
}
};
($t:ty; $n:expr) => {
(0..$n).map(|_|
get!($t)
).collect::<Vec<_>>()
};
($($t:ty),*; $n:expr) => {
(0..$n).map(|_|
get!($($t),*)
).collect::<Vec<_>>()
};
($t:ty ;;) => {
{
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.split_whitespace()
.map(|t| t.parse::<$t>().unwrap())
.collect::<Vec<_>>()
}
};
($t:ty ;; $n:expr) => {
(0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
};
}
以下すべての解答でこのマクロのコードを貼り付けているものとします。
D ランク問題
ネオン街の裏路地
fn main() {
let N = get!(usize);
let list = get!(i32;N);
println!("{}", list.iter().max().unwrap());
}
カジノ
fn main() {
let x = get!(i32;3);
println!("{}", x[0] + x[1] * 5 + x[2] * 10);
}
郊外のスラム街
fn main() {
let n = get!(i32);
println!("{}", n / 2 + 100);
}
C ランク問題
自然の残る公園
fn main() {
let (N, a, b) = get!(usize, i32, i32);
let mut best = (!0, 1e9 as i32);
for i in 0..N {
let (x, y) = get!(i32, i32);
let d = (x - a) * (x - a) + (y - b) * (y - b);
if best.1 > d {
best = (i + 1, d);
}
}
println!("{}", best.0);
}
廃マンションの一室
急に難くなったように感じます。
再帰関数を使う方法も考えましたが、N が大きくないので全探索しました。
(B ランクより難しいと感じたのでなにか見落としているのかもしれません…)
/// x (特殊3進数) を 10 進数に変換した値を求める
fn decode(mut x: i32) -> i32 {
let mut tot = 0;
let mut b = 1;
while x > 0 {
let v = x % 3;
tot += b * if v == 2 { -1 } else { v };
b *= 3;
x /= 3;
}
tot
}
fn main() {
let n = get!(i32);
for i in 0..1_000_000_000 {
if n == decode(i) {
let mut x = i;
let mut lst = vec![];
while x > 0 {
lst.push(x % 3);
x /= 3;
}
for v in lst.into_iter().rev() {
print!("{}", v);
}
println!();
return;
}
}
}
B ランク問題
一番通りの繁華街
全探索します。
fn main() {
let N = get!(usize);
let G = get!(String;N)
.into_iter()
.map(|s| s.chars().collect::<Vec<char>>())
.collect::<Vec<_>>();
let mut tot = 0;
for i in 0..N {
for j in 0..N {
if G[i][j] == '.' {
for sz in 1..N {
let k = i + sz;
let l = j + sz;
if k < N && l < N {
if G[k][l] == '.' && G[i][l] == '.' && G[k][j] == '.' {
tot += 1;
}
}
}
}
}
}
println!("{}", tot);
}
ギャングのアジト
全探索します。
fn main() {
let N = get!(usize);
let G = get!(usize;;N);
for i in 0..N {
for j in 0..N {
if G[i][j] != G[i][N - j - 1] {
println!("No");
return;
}
}
}
println!("Yes");
}
A ランク問題
新都心のハイウェイ
B から見える位置すべてにマークをした後、A からいずれかのマークまでの最短経路を求めます。
use std::collections::VecDeque;
const D4: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];
fn main() {
let (N, M) = get!(usize, usize);
let G = get!(String;N)
.into_iter()
.map(|s| s.chars().collect::<Vec<char>>())
.collect::<Vec<_>>();
let mut mark = vec![vec![false; M]; N];
let mut A = (!0, !0);
for i in 0..N {
for j in 0..M {
if G[i][j] == 'A' {
A = (i, j);
}
if G[i][j] == 'B' {
for d in D4 {
let mut i2 = i;
let mut j2 = j;
loop {
if i2 < N && j2 < M && G[i2][j2] != '#' {
mark[i2][j2] = true;
} else {
break;
}
i2 = i2.wrapping_add(d.0);
j2 = j2.wrapping_add(d.1);
}
}
}
}
}
let mut que = VecDeque::new();
que.push_back(A);
let mut dists = vec![vec![!0; M]; N];
dists[A.0][A.1] = 0;
while let Some((i, j)) = que.pop_front() {
if mark[i][j] {
println!("{}", dists[i][j]);
return;
}
for d in D4 {
let i2 = i.wrapping_add(d.0);
let j2 = j.wrapping_add(d.1);
if i2 < N && j2 < M && G[i][j] != '#' && dists[i2][j2] == !0 {
dists[i2][j2] = dists[i][j] + 1;
que.push_back((i2, j2));
}
}
}
println!("{}", -1);
}
S ランク問題
思い出の屋上
任意の空きマスを中心としたときに作ることができる縄張りの最大サイズは「そのマスから既に占有されてる縄張りまでの最小距離 - 1」なので、そのうちの最大値を求めます。
use std::collections::BinaryHeap;
const D4: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];
fn main() {
let (H, W, M) = get!(usize, usize, usize);
let mut que = BinaryHeap::new();
for _i in 0..M {
let (r, c, s) = get!(usize, usize, i32);
que.push((s, r - 1, c - 1));
}
// マスから縄張り延長可能な距離
// 縄張りマスは >= 0、
// 空きマスは < 0 になり、絶対値をとると縄張りまでの最短距離を表します
let mut T = vec![vec![-1e9 as i32; W]; H];
while let Some((s, r, c)) = que.pop() {
if T[r][c] > s {
continue;
}
for d in D4 {
let nr = r.wrapping_add(d.0);
let nc = c.wrapping_add(d.1);
if nr < H && nc < W && T[nr][nc] < s - 1 {
T[nr][nc] = s - 1;
que.push((s - 1, nr, nc));
}
}
}
let mut ans = -1;
for r in 0..H {
for c in 0..W {
ans = ans.max(-T[r][c] - 1);
}
}
println!("{}", ans);
}
(コメントが少ないと怒られるようです…)
おわりに
いかがでしたでしょうか。
C++ や Java が読める方であれば、すんなりと読めると思います。
採用する企業側から見ても、スキルチェックのコードが Rust で書かれていても問題ないのではないでしょうか。
paiza 様、最も愛されているプログラミング言語 Rust をスキルチェック対応言語へ追加することをご検討ください。