Rust 初心者が Rust で AtCoder にチャレンジする
yuこのスクラップでは Rust 未経験な僕が Rust で AtCoder に挑戦する際に学んだことをつらつらとまとめていきます。
自分について
Rust もアルゴリズムも多少調べたことがある程度でほぼ素人です。
目的
- Rust の勉強
- アルゴリズムの勉強
目標
一旦、緑色を目指す
yuRust のセットアップ
Rust のインストール
公式の方法 でインストール
以下の3つのツールが使えるようになっているはずなので確認
rustup --version # Rust のバージョン管理
rustc --version # Rust のコンパイラ
cargo --version # Rust のパッケージマネージャー
参考：https://zenn.dev/toga/books/rust-atcoder/viewer/setup
AtCoder のローカル環境を整備する
一応、必須ではないです。僕自身最初のうちはサイト側でやってたんですが、エラーの確認とかテストケースの確認が大変なのでやっぱりローカルでの環境はあった方がいい気がしたので設定しました。
基本はこれをなぞっただっただけ（感謝）
cargo-compete というツールを使う
これを使うとローカルにテストケースとかが落とせて、コマンド一つでコーディングがはじめられる状態が構築できて、他にもテストの実行ができたり提出などもここから実行できる
何より VSCode の補完などが効く状態でコーディングできるのが嬉しい
準備
cargo install cargo-compete # インストール
cargo compete init atcoder # セットアップ
cargo compete login atcoder # ログイン
使い方
仮にコンテストが abc300 だとした場合
cargo compete new abc300 # コンテストに関するディレクトリが作られてテストケースなどが配置される
cd abc300 # 以下のテストや提出コマンドを叩くために作られたコンテストディレクトリまで移動する
cargo compete test a # abc300/a 問題を実装した後このコマンドでテストを実行できる
cargo compete submit a # abc300/a 問題が問題なさそうなので提出
テストケースを全部ダウンロードして全て実行する
new しただけだと3つくらいしかテストされないが、全部のテストケースを落としたい場合は以下の手順で対応できる
-
Dropbox から該当の問題の
inoutを落としてくる - ローカルの該当の問題の
testcasesにダウンロードしたファイルを配置する
これだけでテスト実施時に全てのテストが回る
もし特定のテストケースだけ実行したい場合は cargo compete test a --testcases 000 のようにテストケース番号を指定して実行もできる。
逆にテストをスキップしたい場合は cargo compete submit a --no-test とするとテストがスキップされる
yu保存時にフォーマットをかける方法
yuRust で AtCoder を始める人向けの記事
本当に Rust が初めてならこれがとても参考になる（感謝）
yuここからは Rust でよく使いそうな処理をメモしていく
🔰 = Rust の理解をするためのメモ
✍️ = AtCoder で使いそうな tip
yu✍️ 標準入力を受け取る
proconio::input! {
n: i32,
}
✍️ 多次元配列を受け取る
入力が以下のような形で多次元配列として受け取りたい場合
1 0 1
2 1 2
1 0 1
以下のような形で受け取れる
fn main() {
proconio::input! {
c: [[i32; 3]; 3],
}
println!("{:?}", c); // [[1, 0, 1], [2, 1, 2], [1, 0, 1]]
}
✍️ char の多次元配列を受け取る
# や . などの char 型で構成された多次元配列を受け取る時は proconio::marker::Chars が使える
fn main() {
proconio::input! {
h: i32, // 何行あるかが渡ってくるイメージ
board: [proconio::marker::Chars; h],
}
println!("{:?}", board); // [['#', '.', '#'], ['.', '#', '.'], ['#', '.', '#']]
}
✍️ フォーマットで10進数を2進数に変換する
下の 010 は桁数を指定してゼロ埋めする
let n = 10;
println!("{:b}", n); // 1010
println!("{:010b}", n); // 0000001010
✍️ 文字列を数値に変換
let tmp = "100";
tmp.parse::<i32>().unwrap(); // 100
char型の場合は to_digit() も使える。基本 parse でよさそうな気がするが、こっちは変換できない時に None を返すらしい
let tmp = "1";
tmp.to_digit(10).unwrap(); // 1
✍️ 数値を文字列に変換
let tmp = 100;
tmp.to_string(); // "100"
✍️ 余りを切り上げる
Rust とか関係なくよく使う tip 的なもの
(割られる数 + 割る数 - 1) / 割る数 という公式で余りを切り上げることができる
let target = 10; // 割られる数
let base = 3; // 割る数
let ans = (target + base - 1) / base; // (10 + 3 - 1) / 3 → 4
✍️ 文字列を一文字ずつ分解して扱う
JS とかだと添え字で該当の文字を参照できるがそれができないっぽい
一回 char 型に分解してベクター型とかにして参照する必要がありそう
let word = "Hello world!";
let word_chars: Vec<char> = word.chars().collect();
println!("{}", word_chars[1]); // "e"
ブラケットで存在しない添字にアクセスするとエラーになるが .get() を使うと存在しない添え字のときに None を返すので場合によってはこっちの方が良いかも
println!("{}", word_chars.get(1)); // "e"
１文字ずつループを回したりもできる
for c in word_chars {
// c に一文字ずつ渡されて使う
}🔰 ベクタについて
いくつか問題を解いたけど、意味もわからず .iter(), .collect() , .enumerate() などを使っているので理解したい。
参考
そもそもベクタとは
可変長配列。配列は固定長なのでそこが違う。
push() 、pop() などが使えて後からデータの追加、削除が行える。
Java でいうところの ArrayList と Array のような関係っぽい。
そもそも C++ では同じようなベクタと Array があるっぽいのでそれと同じような感じなんだと思う。
使い所
標準入力から数が決まって配列のような操作をする時は基本的にベクタになるはず。（そもそも標準入力を受け取って [i32; n] みたいにしたらベクタになるらしい）
他にも文字列を分解して一文字ずつの char型の配列を作ろうとした時とかに使った。
イテレータとは
関数の理解の前にここら辺を知る必要がありそう。
イテレータとは、オブジェクトを順番に扱うためのオブジェクトとのこと。
コレクションの要素を逐次的にアクセスするための概念で next() などで各要素一つ一つにアクセスできるようなもので、map や filter などの関数を使ったり、ループを回す時に作ったりする。
コレクションとは
複数のオブジェクトを管理するデータ構造のこと。
Vec や HashMap などがこれに該当するらしい。
.iter() とは
コレクションに対して呼び出して、コレクションの値に対する不変（読み取り専用）のイテレータを生成する。
こんな感じとか。
読み取り専用なので、ここでの value は値を変更することができない。
let v = vec![1, 2, 3, 4];
for value in v.iter() {
// value
}
ここで iter() を使わずに for value in v { のように書いても動くが、v の所有権が失われるのでループ以降で v が使えなくなる。
変更もさせず、所有権も渡さずループをしたり、 map や filter などを実行する時に使うんだと思う。
.collect() とは
イテレータをコレクションに変換する。
イメージ的には元々ベクタのものから iter() で一旦イテレータを生成して、map とかで値の操作をして、その結果が反映されたベクタを返すようなイメージっぽい。
let list = vec![1, 2, 3];
let list2 = a.iter() // イテレータを生成
.map(|&x| x * 2) // 値を操作（全てを二倍にする）
.collect(); // イテレータをコレクション（ベクタ）に変換
.enumerate() とは
インデックスと各要素のタプルに変換する
ループとかでそれぞれの要素とその添え字が欲しいときに使う
let list = vec["aaa", "bbb", "ccc"];
for (index, value) in list.iter().enumerate() {
// (0, "aaa"), (1, "bbb"), (2, "ccc") みたいな感じになる
}
✍️ map メソッドで値に処理を実行した新しいコレクションを作る
let a = [1, 2, 3];
let b: Vec<i32> = a.iter().map(|&x| x * 2).collect(); // [2, 4, 6];
✍️ filter メソッドで値を絞り込んで新しいコレクションを作る
let a = [1, 2, 3, 4, 5, 6];
let b: Vec<i32> = a.iter().filter(|&x| x % 2 == 0).collect(); // [2, 4, 6];
✍️ fold メソッドで js の reduce のような計算をする
let a = [1, 2, 3];
let sum = a.iter(). fold(0, |acc, x| acc + x); // 6
🔰 無限ループは loop が使える
while true { とかではなく loop がそのまま使える
loop {
// 脱出条件を作って `break` する
}
🔰 累乗
pow 関数が使える。
第二引数は u32 じゃないといけないので注意
2_i32.pow(3_u32);
num_traits::pow; もある
use num_traits::pow;
fn main() {
let num = 3;
println!("{}", pow(num, num); // 27
}
✍️ 文字列の長さを比較して差分が -1〜1 文字までのものを絞り込む
対象の文字列の長さと配列に入っている文字列の長さを比べて１文字小さい、同じ、１文字大きいのだけを絞り込みたい時に書いた
let target = "aaaa";
let a = ["bbbb", "ccc", "ddddd", "eeeeeeeeeee"];
let items = a.iter().filter(|&x| {
let s_len = x.len();
let t_len = t.len();
let diff = (s_len - t_ren).abs();
diff <= 1
}).collect(); // ["bbbb", "ccc", "ddddd"];
✍️ 配列の反転
a.reverse(); // こっちは破壊的
// or
let b = a.iter().rev().collect(); // こっちは新たに生成
✍️ 降順にソート
a.sort_by(|a, b| b.cmp(a));
もしくはソートして反転させるでも良い
a.sort();
a.reverse();
🔰 .unwrap() とは
メソッドチェーンの最後によくつけるやつ
以下のような時に使っているイメージ
"100".parse::<i32>().unwrap(); // 100
何をしているのか
Option<T> や Result<T, E> などのラッパータイプの値を取り出すものらしい。
名前的にも un + wrap だから直感的な気がする。
Rust には null や 例外 が存在しないため、値の存在確認を Option 型、処理の成功、失敗を Result 型で扱うらしい。
Option<T> とは
値が存在するかどうかの表現する列挙型（enum）
値がない時に None、値がある時に Some(T) を示す
T はジャネリック型で使う時に型を決めることができる
ちなみにここでの None と Some(T) を バリアント といい
列挙型の具体的な値のことを指す
以下のような構造
pub enum Option<T> {
None,
Some(T),
}
以下のような形で、match 式や if let などを使って値と取り扱える
let optional: Option<i32> = Some(5); // Option<i32> のインスタンスが optional に入る
match optional {
Some(v) => println!("{}", v), // 5
None => println!("None"), // None
}
let value: Option<i32> = Some(5);
if let Some(v) = value {
println!("{}", v); // 5
}
Result<T, E> とは
処理が成功したか失敗したかを表現する列挙型（enum）
定義はこちら
pub enum Result<T, E> {
Ok(T),
Err(E),
}
処理が成功していれば Ok(T) となり、失敗していれば Err(E) となる
ファイルアクセスの時とかにこんな感じで使えるらしい
ファイルアクセスして失敗したらファイルを生成して、それも失敗したらパニックという流れ
use std::{fs::File, io::ErrorKind};
fn main() {
let f = File::open("sample.txt");
let f = match f {
Ok(file) => file,
Err(ref error) if error.kind() == ErrorKind::NotFound => {
match File::create("sample.txt") {
OK(fc) => fc,
Err(e) => panic!("error: {:?}", e);
}
},
Err(error) => {
panic!("error: {:?}", error)
}
}
}
.unwrap() の挙動について
Option 型、 Result 型 から値を取り出すのがこのメソッド
それぞれ値を取り扱うためにラップされているオブジェクトなので、それを剥がして値を取り出すようなイメージ
もし値が None や Err だった時は panic! マクロを呼び出すらしいので、実際にはちゃんとエラーハンドリングをするのが良いみたい。（競技プログラミングだと入力のルールもがっちりしていて例外があまりない前提なので、結構使われてるのかな？）
それぞれ、以下のようなイメージっぽい
option.unwrap();
// ↓
match option {
Some(v) => v,
None => panic!(),
}
result.unwrap();
// ↓
match result {
Ok(v) => v,
Err(e) => panic!(),
}
unwrap_or とは
大体としては unwrap_or() とかが良いらしい
Ok(T) や Some(T) の時はその値を返して、 None や Err(E) の時は指定したデフォルト値を返すらしい
let optional1 = Some(5);
let value1 = optional1.unwrap_or(10); // 5
let optional2 = None;
let value2 = optional2.unwrap_or(10); // 10
unwrap_or_else とは
上記と同じ条件で、None や Err(E) の時にクロージャーを実行して返すことができる
let optional = Some(5);
let value = optional.unwrap_or_else(|| {
println!("値がありませんでした");
0 // こんな感じで何か処理をした後に値を返すことができる
});
参考
yu🔰 例外について
unwrap のところでも触れたけど Rust に例外はなく、代わりに Result 型を使うらしい。
yu✍️ 配列の重複削除
HashSet を使う
HashSet はデータ型的に重複が許されないので、一旦 HashSet に変換するだけで重複が削除される。
ただ、 HashSet は順序を持たないのでもう一度ベクタ型に戻して扱いやすくする。
use std::collections::HashSet;
let tmp: HashSet<i32> = data.into_iter().collect();
let items: Vec<_> = tmp.into_iter().collect();
// ソートとかループとかできるので扱いやすい
この時 into_iter() を使っているが、これは配列の値の参照を渡すことを意味している。
なので、以下の例でいくと data は使えなくなり、次に tmp も使えなくなる。
.dedup() を使う
.dedup() は連続した重複する値を１つにまとめることができる。
例えば [1, 2, 2, 3, 2] があれば [1, 2, 3, 2] となる。後ろの 2 は連続していないので弾かれない。
.sort() してからこの処理を使えば重複が削除できる
let mut a = [1, 2, 2, 3, 2];
a.sort(); // [1, 2, 2, 2, 3];
a.dedup(); // [1, 2, 3];
🔰 for について
範囲を指定する場合に 0..n のように指定していたがこれだと n が含まれない。
そのため、今までは 0..n+1 のように指定していたが 0..=n で最後の数字を含むようになるらしい。
ちなみにこの (start..end) という書き方は Range 構造体 と呼ぶらしい
for i in 0..10 {
// 0から9まで
}
for i in 0..=10 {
// 0から10まで
}
反転して大きい数字から扱う
rev() を使うと良いらしい。10..0 みたいには書けないっぽい。
for i in (0..=10).rev() {
// 10から0
}
🔰 配列の中身の比較は == で判定できる
二つの配列の値が全く同じかどうかの判定が == で良いらしい。
配列の長さ、値などを比較するので完全に同じ中身同士だと true になる。
多次元配列でも問題なくできる。
yu✍️ 最大の数を取得する
値が小さいものを探す時などに、初期値が最大だと嬉しい時があったので以下の方法で対応した。
let mut ans = !0;
ビット反転演算子で 0 すべてのビットが反転するので２進数の全ての値が 1 になり、その型で表現できる最大の整数となります。これができるのは u64 や usize などの負の数がない型だけで i32 とか i64 とかでやると -1 となります。
最大値はそれぞれの型で i64::MAX などの定数が用意されているみたいなのでそれを使うのが可読性的にも良いのかもしれない。
yu✍️ 文字列に特定の文字が含まれているか確認する
contains() を使う
let s = "sample";
if s.contains("test") {
println!("Yes");
} else {
println!("No");
}