Rust で競プロ

Rust で競プロする話について書こうと思います。ちなみにこの記事は競プロアドベントカレンダーの7日目の記事です。

Rust とは何だったか

Rustは速度、安全性、並行性の3つのゴールにフォーカスしたシステムプログラミング言語です。 (公式サイトより引用)

Mozilla が開発しているコンパイル型のプログラミング言語です。 ムーブセマンティクスや変数の寿命といった独特な機能によってメモリの安全性やデータ競合の安全性をコンパイラが保証している点や、プログラミングする上で便利な構文が用意されているのが特徴的です。 言語の機能としては例えば imos さんの記事とかが詳しいです。

開発の世界では最近注目が集まってきているような気がしますが競プロではまだまだ使われている場面が少ないので、布教も兼ねてどういう感じか紹介したいと思います。

競プロで C++ 使ってるけど、Rust 使う利点/欠点は何？

利点としては、後述するような優れた構文やツールチェーンのおかげでプログラミングが柔軟にできる点は大きいのではないでしょうか。標準ライブラリも結構充実しているため少なくとも C++ と同等のことは出来るのではないかと思います。実行速度に関しても C++ に引けを取らない速さを達成しており安心できます。

欠点としてはマイナー言語にありがちなことですが、競プロでは使ってる人がそこまで多くないので競プロ用の便利ライブラリや問題の正解コードなどを探すのは難しくなるでしょう。また、日々コンパイラがバージョンアップしていくせいで最新の機能を使いたくてもオンラインジャッジが対応していないせいで使えないといった状況は覚悟したほうが良いです。 残念ながら日本語の情報はそこまで多くなく詰まった時にググって出て来る情報は大抵が英語なので、技術英語を読めるレベルの語学力は必須になるでしょう。

というわけなので、初心者の人は普通に C++ 使ったほうが良いと思います。逆に C++ をある程度使いこなせるけど C++ に飽きてきたから他の言語試してみたいみたいな場合には、使ってみると楽しいかもしれません。

どういうオンラインジャッジ/コンテストサイトで使えるの？

ちょっと調べました。意外にも結構対応してるところが多いですね。ちなみに現時点(2017/12/9)での最新バージョンは1.22.1です。

• AtCoder : 1.15.1
• Codeforces : 1.21
• Aizu Online Judge : (バージョン不明？)
• Sphere Online Judge : 1.14.0
• HackerRank : 1.21.0 + いくつかの外部ライブラリが付属

以下は未対応のようです。…頑張れ！

• ACM/ICPC
• CS Academy
• topcoder

どういった環境で使うべき？

Rust はクロスプラットフォームな言語なので Windows でも MacOS でも Linux でも使えます。インストールは容易です。

エディタについては、IDE はできればあった方が良いと思います。Rust and IDEs · The Rust Forge を見ると Vim, Emacs, Sublime, IntelliJ Idea, VSCode などの主要なエディタにプラグインが揃っているので、普段使用しているエディタにプラグインを入れれば快適な環境が整いそうです。

どうやって勉強したら良いの？

公式チュートリアルの Rust Book を読むのが良いです。

特徴的な言語機能

色々ありますがここでは競プロで役立ちそうな Rust の言語機能を C++ と比較しつつ紹介したいと思います。

for 文

とても基本的ですが、単に n 回ループを回したい時に REP マクロのような怪しいものに頼らずに済みます。

let n = 10;
for i in 0..n {
    solve(i);
}

型推論

型推論が強力で、宣言時に型を指定していなくても途中で型が決まるようなコードをコンパイルできます。

以下のコードだと、1行目では Vec<T> (C++ でいう std::vector<T> 相当のもの。vec![] は要素が空の Vec<T> を宣言するためのマクロ) を宣言しており、1行目の段階では T が何か決まっていません。 2行目を見ると要素に i32 (32ビット整数) を追加しているので、ここで T=i32 が決定されます。

let mut v = vec![];
v.push(1i32);

少ないタイプ数で書けるので便利。

タプル

C++ の std::pair などに比べ、値の組(タプル)についてかなり自然に扱うことができます。

以下のコードでは、値の組を返す some_function という関数に対し、その返り値を別々の変数で受け取る方法を示しています。C++ で std::tie などを使うより自然に受け取れるのが見て取れます。

fn some_function() -> (i32, i32) {
    (123, 456)
}

fn main() {
    let (x, y) = some_function();
    println!("x={}, y={}", x, y);  // => "x=123, y=456"
}

構造体

構造体のコンストラクタは key: value の形で行います。タイプ数が若干増えますが意味はより明示的になります。以下は円を表す構造体の定義とそのインスタンスを作るコードです。

struct Circle {
    x: f64,
    y: f64,
    r: f64,
}

fn main() {
    let my_circle = Circle {
        x: 1.23,
        y: 4.56,
        r: 7.89,
    };
}

毎回 key: value の形で書くのは冗長ですが、もし value が変数で、その変数名が key と一致しているなら、"key: " 部分の記述を省略することができます。(ただしコンパイラのバージョンがある程度新しくないと使えない模様…。)

    let x = 1.23;
    let y = 4.56;
    let r = 7.89;
    let my_circle = Circle { x, y, z, };

便利機能として、構造体の宣言時に #[derive(Debug)] というアノテーションを付けておくと、println! などで変数のインスタンスを指定した時にそのインスタンスの内容をそのまま出力できるようになります。 この機能はデバッグ時にかなり便利です。

#[derive(Debug)]
struct Circle {
    x: f64,
    y: f64,
    r: f64,
}

fn main() {
    let my_circle = Circle {
        x: 1.23,
        y: 4.56,
        r: 7.89,
    };
    println!("{:?}", my_circle);  // => "Circle { x: 1.23, y: 4.56, r: 7.89 }"
}

配列のスライス

部分列への参照に簡単にアクセスできます。以下は v という可変長配列の1番目から2番目までの部分列への参照を取っています。

let v = vec![0, 100, 200, 300, 400];
let subseq = &v[1..3];
println!("{:?}", subseq);  // => "[100, 200]"

列挙型

C++ やその他の多くの言語の列挙型 (enum) は単に定数を並べて定義するものに過ぎませんが、それに比べて Rust の列挙型は強力なものになっています。列挙型の項はそれぞれ独自の値の組を持つことができます。

以下はよく使われる Option<T> 型です。何か値を指定したいときには Some(T) を持つ(T はその値の型)けど、何も指定したくないときには None にしておくといった使い方をします。

enum Option<T> {
    None,
    Some(T),
}

競プロの文脈で使うなら、例えばメモ化計算の際に、メモ配列に上記の Option<T> 型を用いて、計算済みの要素は Some(T) を割り当て、まだ計算が済んでいない要素には None を割り当てると言った用途がありえそうです。

パターンマッチ

列挙型の項の値 (T) は if let や match といった構文で取り出せます。以下は Option<T> 型を用いてフィボナッチ数をメモ化再帰で計算する例。

fn fib(i: usize, memo: &mut Vec<Option<i64>>) -> i64 {
    if i <= 1 {
        return 1;
    }
    if let Some(x) = memo[i] {  // もし memo[i] が Some(T) だったら、
                                // x に T を代入して if ステートメント内を実行する
        return x;
    }
    let retval = fib(i - 1, memo) + fib(i - 2, memo);
    memo[i] = Some(retval);
    retval
}

変数名の再利用

同じスコープ内であっても変数名の上書きができます。これにより、似たような機能の変数だけど名前が被っているせいで別の名前を付けないといけない、みたいなことがなくなります。

let mut data;  // 何かのデータを表す変数 data
data.push(100);
// ...
let data = convert(data); // data に変換をかけたものを data という名前にする

代入文での if

代入文で if が使えます。三項演算子と違って、if ステートメントの内部で処理を行えるのが特徴的です。 以下では変数 some_important_flag が真のときには1つ目の if ステートメントの返り値(12345)がxに代入され、そうでないときは2つ目のものが代入されます。

let x = if some_important_flag {
    12345
} else {
  let mut val = 0;
  for i in 0..10 { val += i; }
  val
}

使用頻度は多くないですがいざというときに便利かもしれない。

ツールチェーン

言語の機能だけでなく、どういうツールが使えるのかもプログラミング言語の重要な要素です。

外部ライブラリのインストール

ローカル実行のできるコンテスト(Google Code Jam, Facebook Hacker Cup 等)に限られますが、Cargo というインストール時に標準で入ってくるバイナリを使うと外部ライブラリを簡単にインストールできます。python 使っている人なら pip のようなものだと思うとわかりやすいです。

例えば多倍長整数ライブラリである num をインストールするには、Cargo.toml というプロジェクトファイルに以下のような文字列を1行追加して cargo build のようなコマンドを叩くだけで良いです。

num = "0.1.41"

コードのフォーマット

Rust にはコードを自動で整形するツールが標準で入っています。rustfmt や cargo fmt がそれに相当します。例えば以下のようなコードがあったとして、

let x=3 as f64;
let y=4 as f64;
let r=(x*x+y*y).sqrt();
println!("{}",r);

整形すると以下のようになってくれます。

let x = 3 as f64;
let y = 4 as f64;
let r = (x * x + y * y).sqrt();
println!("{}", r);

こういった標準の整形ツールが存在することで、スペースの空け方や改行位置の調整といったような表面的なことにあまり拘らなくて済むようになるのはありがたいかもしれない。

入力処理

Rust には C++ と違って scanf や std::cin のような手軽に競プロっぽいフォーマットの入力を標準入力で受け取る関数が無いため、ある程度自分でスキャナー相当のものを書いておいたほうが便利になります。

ここでは自分が使っているものを紹介します。read を呼び出すとトークンを文字列から所望の型に変換して返して暮れます。トークンの前後に余分なスペースや改行などがあっても使えます。

use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}
 
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }
 
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }
 
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

以下のような感じで使えます。

fn main(){
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);  // スキャナの定義

    let n: i32 = sc.read();  // 普通にトークンを1つ読みたいとき
    while let Some(n) = sc.read1() {  // こっちはICPC形式などでEOFで入力が終わるとき用
        // ...
    }
}

もしかすると他にももっと効率の良い実装方法があるかもしれません。

標準ライブラリ

入力が取れれば後はなんでもできます。C++の標準関数やSTLで代表的なものと Rust の標準ライブラリとの対応を貼っておきます。

ライブラリ	C++	Rust
入出力関数	cstdio	std::io
数学関数	cmath	std::f64 など
可変長配列	std::vector	Vec
キュー	std::queue	VecDeque
優先度付きキュー	std::priority_queue	BinaryHeap
文字列	std::string	String から Vec<char> などに変換して扱うのが無難そう
連想配列	std::map	std::collections::BTreeMap
集合	std::set	std::collections::BTreeSet
ペア、タプル	std::pair, std::tuple	タプル
アルゴリズム	std::algorithm	色んな所に散らばっている(next_permutation, lower_bound など一部関数は未実装)
関数オブジェクト	std::functional	クロージャ
ビットセット	std::bitset	BitSet, BitVec (ただし Unstable)
乱数	rand, std::random	標準では未実装、外部ライブラリの rand が有名
複素数	std::complex	標準では未実装、外部ライブラリの num が有名

このように、主要なものはだいたい標準ライブラリでカバーしているものの、一部は未実装だったり外部ライブラリが必要だったりするのは注意が必要かもしれません。

その他

let mut とか毎回書くのは面倒そう

競プロでもコードを書いてると変数が実は定数でいい(let だけでよい)ことは結構あるので、毎回 let mut と書かないといけないわけではないです。

コンパイラが厳格で大変そう

所有権まわりの制約は結構厳しそうに見えますが、理不尽なコンパイルエラーに遭遇することはそこまで多くない印象です。 もちろん、コードを書いてて何度か意味を理解するのが難しいコンパイルエラーに遭遇したことはあります。ただ、ちょっとややこしい状況でややこしいコンパイルエラーが出るのは C++ でも同じなので、Rust だけ理不尽かというとあまりそんなことはない気がします。

とはいえもちろん Rust もまだまだ開発中の言語なので、かなりトリッキーな例は存在するようです。例えば Rust Book の最後の章ではそういった例が紹介されています。注意をするに越したことはありません。

Rust で書かれた競プロのライブラリとかって無いの？

ちょっと調べた感じだと EbTech 氏のライブラリはとてもまとまっている印象を受けました。 ただ、これもまだまだ実装は部分的で、例えば Spaghetti source ほどの充実性は無いように見えます。

逆に言えば、今なら Rust で充実したライブラリ集を出せば大いに注目を浴びる可能性はあります。

まとめ

Rust で競プロする話について書きました。面白い言語だと思うので競プロでも普及すると良いですね。