競プロerのみなさん、こんにちは。
AtCoder にてついに全ユーザー待望のジャッジシステムアップデートが実行され、本日開催される AtCoder Beginner Contest 163 から新システムが公式コンテストで使用できるようになります。
数ある言語のうち、Rust はアップデートが望まれていた度合いで言うと上位に入るのではないかと勝手に思っています。
旧ジャッジシステムでの Rust のバージョンは v1.15.1 でした。これは 2017/02/09 にリリースされたバージョンです。
2020/04/12 現在の最新バージョンであり、AtCoder 新ジャッジシステムで使用可能となる v1.42.0 は 2020/03/12 にリリースされました。およそ3年の時を経ていることになります。
Rust はこの約3年の間に着実に進化を続けてきました。
その進化の中には、競技プログラミングにおいて役立つようなものも数多く存在しています。
このエントリでは、そのような進化の数々をざっと紹介できればと考えています。
紹介の仕方
旧ジャッジシステム (v1.15.1) で使用できず、新ジャッジシステム (v1.42.0) で使用可能となった関数などに対して、独断と偏見で「役立ち度」を5点満点で付けて、導入されたバージョンおよびかんたんなコードサンプルとともに紹介していきたいと思います。
あと、公式ドキュメントへのリンクも付けます。公式ドキュメントは Rustcean の心強い味方です。
コードサンプルはドキュメントのものとほぼ同じになってしまうことがありますが、ご了承ください。
標準ライブラリ
str::repeat ★☆☆☆☆
v1.16.0 〜
&str を指定回数繰り返した結果の文字列を String 型で生成します。
"abc".repeat(3) // String 型の "abcabcabc" ができます
String::insert_str ★☆☆☆☆
v1.16.0 〜
可変な String に、インデックスを指定して文字列を挿入します。
計算量的には $O(n)$ （$n$ は挿入先の文字列の長さ）かかるので、あんまり使わない気がします。
あと、ご存知の通り Rust の String は UTF-8 エンコードされていて、インデックスでアクセスするのは、非 ASCII 文字が含まれるときには想定と異なる挙動となることがほとんどだと思います。（競プロだとまず大丈夫だとは思いますが）
let mut s = String::from("hoge");
s.insert_str(2, "piyo"); // "hopiyoge" になる
std::string::String::insert_str - Rust
BTreeMap::range & BTreeSet::range ★★★★☆
v1.17.0 〜
みんな大好き二分探索ができます。計算量 $O(\log n)$ なので、積極的に使っていけます。
std::collections::btree_map::BTreeMap - Rust
std::collections::BTreeSet - Rust
use std::collections::BTreeSet;
let mut set = BTreeSet::new();
set.insert(3);
set.insert(5);
set.insert(8);
// 「4 以上」を探したときの 【最初】 の要素 「5」 が得られる
assert_eq!(Some(&5), set.range(4..).next());
// 「7 未満」を探したときの 【最後】 の要素 「5」 が得られる。 last より next_back のほうが効率が良い
assert_eq!(Some(&5), set.range(..7).next_back());
// 「8 以下」を探したときの 【最後】 の要素 「8」 が得られる。
assert_eq!(Some(&8), set.range(..=8).next_back());
cmp::Reverse ★★★★★
v1.19.0 〜
降順ソートをしたいときに便利です。
また、デフォルトで max-heap （pop したときに最大の値が出てくる） である Rust の優先度付きキュー BinaryHeap を、 min-heap にするためにも使えます。ダイクストラ法を書くときお世話になりそうです。
std::cmp::Reverse - Rust
Min-Heapの例
// 降順ソート
use std::cmp::Reverse;
let mut v = vec![3, 2, 4, 1, 5, 6];
v.sort_by_key(|&k| Reverse(k)); // v は vec![6, 5, 4, 3, 2, 1] になる
// min-heap
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
heap.push(Reverse(2));
heap.push(Reverse(5));
heap.push(Reverse(1));
let Reverse(first) = heap.pop().unwrap(); // first には １ が入る
let Reverse(second) = heap.pop().unwrap(); // second には 2 が入る
let Reverse(third) = heap.pop().unwrap(); // third には 5 が入る
FromStr トレイトが char に対して実装された ★☆☆☆☆
v1.20.0 〜
以下のようにして str 型から char 型に変換できるようになりました。
入力の読み取りのときに使える………かも？？
let c = "s".parse::<char>().unwrap(); // `char::from_str("c")`が呼ばれる
add FromStr Impl for char by tinaun · Pull Request #42271 · rust-lang/rust
str::get ★★☆☆☆
v1.20.0 〜
部分文字列を得ることができます。基本は Vec<char> にすべきだと思いますが、競プロでは ASCII 文字列以外が出てくることはほぼないと思うので、 str のまま、やっても良いかもしれません。
let s = "hoge";
assert_eq!(s.get(1..2), Some("o"));
assert_eq!(s.get(1..3), Some("og"));
x += &42; のように書けるようになった ★★☆☆☆
v1.22.0 〜
何のことやらわかりにくいと思うので例を見ていただくのが良いと思います。
地味にありがたいかもしれないです。
Allow T op= &T for built-in numeric types T v2 by Eh2406 · Pull Request #44287 · rust-lang/rust
let mut x = 7;
x += &42; // x は 49 になる
閉区間 [n, m] をn..=m で書けるようになった ★★★★★
v1.26.0 〜
$1 \leq i \leq N$ で for を回したい、なんて場合がたまにあると思いますが、v1.15.1 では
for i in 1..(N + 1)
のように書く必要がありました。
今は以下のように書けます。
for i in 1..=N {
println!("{}", i);
}
String::retain ★★☆☆☆
v1.26.0 〜
String の可変借用を受け取り、クロージャで「文字列に残す条件」を指定して、文字のフィルタリングのようなことを行います。
let mut s = String::from("f_o_ob_ar");
s.retain(|c| c != '_'); // s は "foobar" になる
hash_map::Entry::and_modify & btree_map::Entry::and_modify ★☆☆☆☆
v1.26.0 〜
例えば、文字列中の各文字の出現回数を求めたいときに、 文字列を１文字ずつループで舐めながら HashMap を使って以下のような操作すると思います。
文字 $c$ をキーとして、対応する値がすでに入っていれば、その値をインクリメントする。なければ、値に１を入れる。
従来であればこのような操作は次のように行っていました。
use std::collections::HashMap;
let mut map = HashMap::new();
*map.entry('x').or_insert(0) += 1; // キー 'x' に対して値 1 がセットされる
これを、以下のように書くことができるようになりました。文字数は多くなりますが、意味合いは分かりやすくなる気がします。
use std::collections::HashMap;
let mut map = HashMap::new();
map.entry('x').and_modify(|e| *e += 1).or_insert(1); // 上記と同様の状態になる
std::collections::hash_map::Entry - Rust
std::collections::btree_map::Entry - Rust
借用チェッカに怒られにくくなった ★★★★★
v1.31.0 〜 （2018 Edition）
v1.15.1 では、参照のライフタイムの推論をレキシカルスコープに基づいて行っていたため、プログラマからすると「問題ない」ということが分かるような書き方であっても、コンパイラに怒られてしまうといった場合が発生していました。
Non-lexical lifetimes - The Edition Guide
に載っている例から引用し、少し改変した以下のようなコードを考えてみます。
fn main() {
let mut x = "foo".to_string();
// x に対する不変借用をとる。
// レキシカルスコープに基づくと、 y のライフタイムは y がスコープを抜けるまで（= main 関数が終了するまで)となる。
// 借用規則により、 y が生存している間は、 x に対する可変の借用をとることはできない。
let y = &x;
println!("{}", y); // "foo" が出力される (1)
// x に対する可変借用をとろうとする。
// 不変借用 y が生存しているので、コンパイルエラーになる
let z = &mut x; // (2)
z.push_str("bar");
println!("{}", z); // "foobar" が出力される
}
コメントに書いたとおり、レキシカルスコープに基づくライフタイム推論に基づくと、このようなコードは借用規則に反するためコンパイルが通りません。
しかし、v1.31.0 以降（2018 Edition）で導入された Non-lexical lifetimes という仕組みによれば、上記のコードは問題なくコンパイルが通ります。
これは、x の不変借用 y は (1) より後ろでは使われていないので、 y の生存期間は (2) より前に終わると推論しても問題ないからです。
この自然なライフタイム推論が取り入れられたことで、コンパイラに怒られることが減り（また、怒られたときのエラーメッセージも分かりやすくなった）、競プロに限らず Rust のコーディングはとてもやりやすくなったと思います。
slice::chunks_exact など ★★☆☆☆
v1.31.0 〜
従来からあった slice::chunks と少しだけ挙動が異なるメソッドが追加されました。
slice::chunks は、以下のようにチャンクサイズを指定することでスライスを小さな固まりに分割することができました。
let slice = [1, 2, 3, 4, 5];
let mut iter = slice.chunks(2);
assert_eq!(iter.next().unwrap(), &[1, 2]); // 最初の２つ
assert_eq!(iter.next().unwrap(), &[3, 4]); // 次の２つ
assert_eq!(iter.next().unwrap(), &[5]); // 次の２つ...はないので、１つだけ （＊）
assert!(iter.next().is_none());
上の例で （＊）で示した箇所において、「チャンクサイズに満たない分しか残っていないけど、残った分すべてを返す」というような挙動になっています。
これを、「チャンクサイズに満たない分しか残っていない場合には、None を返してしまう」というように変わったものが slice::chunks_exact です。
let slice = [1, 2, 3, 4, 5];
let mut iter = slice.chunks_exact(2);
assert_eq!(iter.next().unwrap(), &[1, 2]); // 最初の２つ
assert_eq!(iter.next().unwrap(), &[3, 4]); // 次の２つ
assert!(iter.next().is_none()); // 次の２つ...はないので、 None を返す
assert_eq!(iter.remainder(), &[5]); // reminder() を呼ぶと、余りが得られる
他にも slice::rchunks も追加されました。名前の通り、スライスの終わり側から開始するバージョンの chunks です。
let slice = [1, 2, 3, 4, 5];
let mut iter = slice.rchunks(2);
assert_eq!(iter.next().unwrap(), &[4, 5]); // （終わり側から見て）最初の２つ
assert_eq!(iter.next().unwrap(), &[2, 3]); // 次の２つ
assert_eq!(iter.next().unwrap(), &[1]); // 次の２つ...はないので、１つだけ
assert!(iter.next().is_none());
slice::chunks_exaxt - Rust
slice::rchunks - Rust
slice::chunks - Rust
dbg! マクロ ★★★★★
v1.32.0 〜
テストケースが通らないとき、DPテーブルの途中経過を出力してどこがバグっているのかを確認したい、みたいなケースはよくあると思います。そういうときに今までだと println!("{:?}", &dp); などと書かなければならなかったと思いますが、dbg! マクロの登場によって飛躍的に楽になりました。
なお、リリースビルドでも普通に動きます。提出時に消し忘れていると TLEの原因になる ので、ご注意ください。
安定化PR
Stabilize dbg!(...) by Centril · Pull Request #56395 · rust-lang/rust
use std::collections::HashMap;
let v = vec![1, 2, 3, 4];
let s = "foo";
let mut map = HashMap::new();
map.insert("hoge", 2);
map.insert("fuga", 7);
dbg!(&v, s, &map);
/* 以下のように標準エラー出力に出力されます
[src/main.rs:9] &v = [
1,
2,
3,
4,
]
[src/main.rs:9] s = "foo"
[src/main.rs:9] &map = {
"fuga": 7,
"hoge": 2,
}
*/
str::trim_start & str::trim_end ★☆☆☆☆
v1.30.0 〜
文字列の先頭、あるいは末尾にある空白文字を取り除いたスライスを返します。
ここでいう空白文字というのは、Unicode で空白文字として定義されているもので、
あたりに細かい定義が書かれているっぽいのですが、執筆時現在、unicode.org に障害か何かが起きているようで、見ることができませんでした。
使えるようになったAPI……というわけではなく、元からあったメソッド trim_left および trim_right が非推奨となり、trim_start、trim_end に置き換えられました。
ドキュメントにある通り、文章が書かれる方向は言語によって異なって、英語や日本語は「左から右へ」書かれるのに対して、アラビア語などは「右から左へ」書かれます。 メソッド名として "start", "end" を使うようにすることで言語によらず意味が明確になる、ということでAPI が変更された形と思います。
str::trim_start - Rust
str::trim_end - Rust
let s = " Hello world ";
println!("{}", s.trim_start()); // "Hello world " が出力される
println!("{}", s.trim_end()); // " Hello world" が出力される
slice::sort_by_cached_key ★★☆☆☆
v1.34.0 〜
slice::sort_by_key というメソッドがあり、例えば以下のようにすると、絶対値の昇順にソートすることができます。
let mut v = [-5i32, 4, 1, -3, 2];
v.sort_by_key(|k| k.abs()); // v は [1, 2, -3, 4, -5] になる
ここではソートに使う値を生成する処理（key function と呼ばれます）が k.abs() となっていて、それほど重い処理ではなさそうですが、key function がそれなりにコストのかかる処理をする必要がある場合、できれば各要素に対して1回だけ行いたいです。
そういうときに slice::sort_by_cached_key を使うと良いです。key function が、各要素に対して1回しか実行されないことが保証されています。
（逆に、 key function が重たい処理でない場合は、 sort_by_key のほうが高速である可能性が高い、とドキュメントにあります）
最悪時間計算量は、$n$ を要素数、$O(m)$ を key function の時間計算量オーダーとして、 $O(mn + n\log n)$ です。
（sort_by_key も同じオーダーです）
slice::sort_by_cached_key - Rust
let mut v = [-5i32, 4, 32, -3, 2];
v.sort_by_cached_key(|k| k.to_string()); // v は [-3, -5, 2, 32, 4] になる
Iterator::copied ★★★☆☆
v1.36.0 〜
参照のイテレータって、要素の型が &T になっていて（それはそう）、値そのものを使いたいときに & や * をつけないといけなくて少し面倒です。
Iterator::copied を使えば、 Copy トレイトを実装している T に対して、参照からコピーを作成して、その後は所有権をもった値として使うことができるようになります。
以下のエントリが分かりやすく、また他のイテレータメソッドについてもまとまっており、おすすめです。
Rustのイテレータの網羅的かつ大雑把な紹介 - Qiita
std::iter::Iterator::copied - Rust
let v = vec![1, 2, 3];
for a in v.iter().copied() {
// a に対する所有権がある
println!("{}", a); // 1 2 3 が改行区切りで出力される
}
todo! マクロ ★★★★☆
v.1.40.0 〜
unimplemented! というマクロがもともとありましたが、それとほぼ同じ機能があります。文字数が減って打ちやすくなりました。
何かの処理を関数に切り出すときに、とりあえず関数の型シグネチャだけ書いておいて、実装はあとでやる！みたいな場合に書いておくと便利です。
fn main() {
println!("{}", foo());
}
fn foo() -> String {
todo!();
}
slice::repeat ★★☆☆☆
v1.40.0 〜
スライスを指定回数だけ繰り返したベクタを生成します。何か使いどころありそう。
let v = [1, 2].repeat(3); // vec![1, 2, 1, 2, 1, 2] と同じものが v に束縛される
matches! マクロ ★★★☆☆
v1.42.0 〜
true, false を返すような match 式のシンタックスシュガーです。
例えば、 foo という Option<i32> 型の変数があって、 Some にくるまれた整数が 2 以上 のときだけ何かしたい、みたいなケースのとき、以下のように書けます。
let foo: Option<i32> = Some(3);
if matches!(foo, Some(x) if x >= 2) {
// 何らかの処理
}
第一引数に変数を、第2引数にパターンを渡す形です。
パターンについては
Rustのパターンマッチを完全に理解した | FrozenLib
にとてもわかりやすくまとめられているため、ぜひご参照ください。
同じく v1.42.0 でスライスに対するパターンマッチが強化され、以下のように書けるようになったため、 matches! と組み合わせると強力…かもしれません。
fn foo(words: &[&str]) {
match words {
["Hello", "World", "!", ..] => println!("Hello World!"),
["Foo", "Bar", ..] => println!("Baz"),
rest => println!("{:?}", rest),
}
}
こちらも参考になります。
Rust 1.42を早めに深掘り - OPTiM TECH BLOG
使えるようになった外部クレートに関して
ここまで、標準ライブラリに追加された機能のうち競プロ的に使いみちのありそうなものを紹介してきましたが、AtCoder の新ジャッジシステム導入に伴って、さまざまな外部クレートを使うことができるようになります。
Rust は言語の方針として「Batteries included (バッテリー同梱)」 になることを避けています。
「バッテリー同梱」は特に Python の特長の1つとしてよく挙げられ、「標準ライブラリがあればなんでもできる」のようなニュアンスです。
Rust がどれほど「バッテリー同梱」を避けているのかというと、標準ライブラリに疑似乱数生成や正規表現を扱う機能すら用意されていないといった徹底具合です。
標準ライブラリがあらゆる処理をカバーしているのは確かに便利ですが、言語のコアに関わらないような機能も言語のリリースと同じサイクルでの開発になってしまうことや、言語そのものに組み込まれてしまうと破壊的変更を伴うアップデートが極めて難しくなることなど、言語の発展という観点からすると喜ばしくない点も多いです。
Rust には Cargo という素晴らしいパッケージマネージャがあり、外部のライブラリをかんたんに使うことができます。
以上のような理由から Rust はバッテリーを同梱しないという方針をとっているわけです。
前置きが長くなりましたが、AtCoder 新ジャッジシステムでは以下のクレートを使うことができるようになりました。Rust エコシステムの充実具合を遺憾なく競技プログラミングに活かせるようになったという感じかと思います。
[dependencies]
num = "0.2.1"
num-bigint = "0.2.6"
num-complex = "0.2.4"
num-integer = "0.1.42"
num-iter = "0.1.40"
num-rational = "0.2.4"
num-traits = "0.2.11"
num-derive = "0.3.0"
ndarray = "0.13.0"
nalgebra = "0.20.0"
alga = "0.9.3"
libm = "0.2.1"
rand = { version = "0.7.3", features = ["small_rng"] }
getrandom = "0.1.14"
rand_chacha = "0.2.2"
rand_core = "0.5.1"
rand_hc = "0.2.0"
rand_pcg = "0.2.1"
rand_distr = "0.2.2"
petgraph = "0.5.0"
indexmap = "1.3.2"
regex = "1.3.6"
lazy_static = "1.4.0"
ordered-float = "1.0.2"
ascii = "1.0.0"
permutohedron = "0.2.4"
superslice = "1.0.0"
itertools = "0.9.0"
itertools-num = "0.1.3"
maplit = "1.0.2"
either = "1.5.3"
im-rc = "14.3.0"
fixedbitset = "0.2.0"
bitset-fixed = "0.1.0"
proconio = { version = "0.3.6", features = ["derive"] }
text_io = "0.1.8"
whiteread = "0.5.0"
rustc-hash = "1.1.0"
smallvec = "1.2.0"
これらのクレートの用途と実際の使い方については、
にとても詳しくまとまっていますので、ぜひご参照ください！
まとめ
- AtCoder ジャッジシステムアップデートで、Rust の標準ライブラリで使える機能が増えて、便利になりました！
- 外部クレートもたくさん使えるようになって、Rust エコシステムの真の力（？）を競プロで発揮できるようになった
抜け漏れ等あると思いますので、何か他に新ジャッジシステムで使えるようになった便利機能をご存知の方いらっしゃいましたら、ぜひコメントください👌
(2020/04/27 追記)
@qryxip さんによる以下のまとめもとてもわかりやすく、そして僕のものよりも網羅性が高いためぜひご覧ください。
競技プログラミングという文脈に限らず、Rust でプログラミングする上で知識として持っておくと良い情報がまとまっており、おすすめです！
@qryxip さんによる Rust1.42.0 まとめ rust-1-42.md