RustでAtCoderに挑戦してみて気づいたポイントまとめ
慣れていないとRustではコンパイルエラーが頻発します。AtCoderの簡単な問題に触れることで、つまづきがちなところをまとめていきたいと思います。
（随時更新していきます）
挑戦した問題
- ABC
- ABC195 ~ ABC204の灰色、茶色
input
省略可能な配列サイズ
このように受け取るものは
input! {
n: usize,
arr: [usize; n],
}
下のように省略できる。
input! {
arr: [usize],
}
ただし、なんだかんだ n が必要な場面は多いので省略しない形で書いた方が良さそう。
文字列をはじめからVec<char>にしておく
use proconio::{input, marker::Chars};
fn main() {
input! {
s: Chars,
}
型
型推論でi32になってしまうことに注意
問題例:
下のコードで vec の型を省略してしまうと、i32で推論されてしまう。その結果 a * (a - 1) / 2 のところで誤った答えになってしまう。（コンパイルエラーではなく計算結果に誤りが生じる）
use proconio::input;
fn main() {
input! {
n: usize,
arr: [usize; n],
}
let mut vec: Vec<i64> = vec![0; 200usize];
for a in &arr {
vec[ a % 200 ] += 1;
}
let mut ans: i64 = 0;
for a in &vec {
ans += a * (a - 1) / 2;
}
println!("{}", ans);
}
usizeで引き算するとオーバーフローが発生するときがある
問題例: https://atcoder.jp/contests/abc203/tasks/abc203_c
下のコードで標準入力をusizeで受け取るとオーバーフローが発生するときがある。
use proconio::input;
fn main() {
input! {
n: isize,
k: isize,
mut arr: [(isize, isize); n],
}
arr.sort_by_key(|k| k.0);
let mut ans = 0;
let mut money = k;
for &(a, b) in &arr {
if a - ans > money {
ans += money;
money = 0;
break;
} else {
money += b - (a - ans);
ans = a;
}
}
if money > 0 {
ans += money;
}
println!("{}", ans);
}
変数
変数の入れ替え
// あらかじめ use std::mem::swap; しておくこと
// x,y = y,x のようなことができる
swap(&mut x, &mut y);
計算
f64での累乗
pow() ではなく powi() を使う。指数部分もf64の場合は powf() を使う。
切り上げ/切り捨て
切り上げはceil()で切り捨てはfloor()。
四捨五入は使う機会あまり無いと思うけど round()。
ループ
降順の連番ループ
for i in (0..n).rev() で n - 1, n - 2, ... 0 のループになる。
無限ループ
loop {
// 無限ループ. while true {}の代わりに使える
}
配列
sort()は破壊的メソッド
arr = arr.sort(); のようなことをするのではなく、単に arr.sort(); をやれば良い。
sort_by_key()でソートのアルゴリズムを指定できる
input! {
n: usize,
mut arr: [(String, i64); n],
}
arr.sort_by_key(|k| k.1); // -k.1とすれば降順
和を取る
arr.iter().sum();
min/maxを取る
let a = arr.iter().min();
let b = arr.iter().max();
// 値を使って計算するためにはunwrap()が必要
a.unwrap() + b.unwrap();
Set
Setの基本的な使い方
ドキュメント: https://doc.rust-lang.org/std/collections/struct.HashSet.html
use std::collections::HashSet;
fn main() {
let mut set = HashSet::new();
set.insert(1);
for a in &set {
// 配列やベクタのようにfor文を回せる
}
set.contains(&1);
}
文字列 (String, Vec<char>)
String→Vec<char>の変換
input! {
s: String,
}
let c: Vec<char> = s.chars().collect();
Vec<char>→Stringの変換
c.iter().collect::<String>();
// 逆順にもできる
c.iter().rev().collect::<String>();
String→数値の変換
// 型の指定が必要
let num = s.parse::<i64>().unwrap();
// 変数部分に指定してもOK
let num: i64 = s.parse::().unwrap();
文字の入れ替え
// あらかじめ use std::mem::swap; しておくこと
let mut s1: Vec<char> = s[..n].to_vec();
let mut s2: Vec<char> = s[n..].to_vec();
// 変数内で文字を入れ替える
s1.swap(0, 1);
// 変数間で文字を入れ替える
swap(&mut s1[0], &mut s2[1]);
}
文字列結合
String + &str の形であればできる。
挿入
Vec<Char>限定で insert というメソッドで好きな位置に文字を入れることができる。
# 先頭に'0'を追加
s.insert(0, '0');
DFS
再帰とwhileによる実装
問題例: https://atcoder.jp/contests/abc204/tasks/abc204_c
再帰
use proconio::input;
fn main() {
input! {
n: usize,
m: usize,
arr: [(usize, usize); m],
}
let mut graph = vec![vec![]; n + 1];
for i in 0..m {
let (a, b) = arr[i];
graph[a].push(b);
}
let mut ans = 0;
for i in 1..=n {
let mut tmp = vec![false; n+1];
dfs(&graph, &mut tmp, i);
for b in &tmp {
if *b {
ans += 1;
}
}
}
println!("{}", ans);
}
fn dfs(graph: &Vec<Vec<usize>>, tmp: &mut Vec<bool>, i: usize) {
if tmp[i] {
return;
} else {
tmp[i] = true;
for j in &graph[i] {
dfs(graph, tmp, *j);
}
}
}
while
VecDequeを使う。この問題はBFSでも解ける（VecDequeをVecにしてpush(), pop()すれば良い）
use proconio::input;
use std::collections::VecDeque;
fn main() {
input! {
n: usize,
m: usize,
arr: [(usize, usize); m],
}
let mut graph = vec![vec![]; n + 1];
for i in 0..m {
let (a, b) = arr[i];
graph[a].push(b);
}
let mut ans = 0;
for i in 1..=n {
let mut tmp = vec![false; n+1];
let mut tmp2 = VecDeque::new();
tmp2.push_back(i);
while tmp2.len() > 0 {
let x = tmp2.pop_front().unwrap();
tmp[x] = true;
for y in &graph[x] {
if !tmp[*y] {
tmp2.push_back(*y);
}
}
}
for b in &tmp {
if *b {
ans += 1;
}
}
}
println!("{}", ans);
}
Discussion
この問題にとても苦戦してしまいました。
文字列操作が難しい…