Rust
競技プログラミング

Rustで競プロするときのプラクティス [2018秋]

競プロで Rust を使い始めて半年が過ぎました。いまの私のプラクティスを羅列的に書いていきます。

筆者

フレームワーク

自作フレームワークはこちら 。いつもこれの main 関数の中に解答を書いて提出しています。

入力のパース

標準機能だけで入力をパースしようとするとだるいです。Qiita にも、すでにこの問題を解決しようという記事がいくつか上がっています。

私は上述のフレームワークに含まれている read! マクロ を使っています。実装が短い (23行) のと、見た目が関数っぽくて好み。

    //! グラフのパースの例
    let (N, M) = read!(usize, usize);
    let weightd_edges = read![[usize, usize, i64]; M];

パフォーマンスは若干悪くて、C++ で std::cin を使うより2倍ぐらい遅いです。それでも 10^6 個の整数を読むのに 100 ms 未満なので問題はないはず。ベンチマーク: scan-bench

デバッグ用のマクロ

LLDB を使うとデバッグ実行できるらしい です。私はやってなくて、いつも print デバッグしています。

debug!: 条件コンパイル

デバッグ出力の消し忘れで WA とかは避けたいです。 条件コンパイル を使って、ローカルではデバッグ出力が出る、ジャッジ時は出ない、というふうにしています。

Debug/Release での分岐は debug_assertions を使えばできる そうです。

// デバッグビルドではこっちの定義が使われる。
#[cfg(debug_assertions)]
macro_rules! debug {
    // 略
}

// リリースビルドではこっちの定義が使われて、 debug!(..) が無になる。
#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($($arg:expr),*) => {};
}

debug!: 定義の省略

ジャッジに不要なコードを提出に含めるのは なんとなく 抵抗があります。そこで、定義はローカルのファイルに書いておき、手元でのデバッグ実行時だけ include! で定義を取り込むという方法があります。

// デバッグ時はローカルのファイルから定義を読み込む
#[cfg(debug_assertions)]
include!{"./procon/debug.rs"}

// リリース時に debug!(..) を消す
#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($($arg:expr),*) => {};
}

これで debug! マクロを高機能化しても提出コードが膨れ上がることはなくなります。

余談: dbg!

ちなみに、将来のバージョンでは公式に dbg! という print デバッグ用途のマクロが入るそうです。参考:rfcs/2361-dbg-macro.md at master · rust-lang/rfcs

数値型

数値型は プリミティブ型 に載っているとおりたくさんありますが、よく使うのは4つ:

i64 10^18 ぐらいまで扱える
usize スライスや Vec の添字に使う
f64 浮動小数点数
char 文字 (厳密には Unicode scalar value)

数値型: usize

usize を int の感覚で書いてると微妙にハマります。マイナスにオーバーフローしたとき、Debug モードでは実行時エラーになります。Release モードではエラーになりませんが、符号なし型なのでマイナスにはならないことに注意です。

例えば次のコード (x, y: usize) はおかしくて、x < y のとき Debug モードではエラーになり、Release モードでも max は機能してません。

    max(0, x - y) // ✘ ダメ

オーバーフローしないようにするか、i64 を経由すれば動きます:

    // monus
    x - min(x, y)

    // または、i64 を経由する
    max(0, x as i64 - y as i64) as usize

文字列

Rust の標準的な文字列型である String (と str) は utf-8 なので、ランダムアクセスできません。そういうときは文字の列 Vec<char> で持つようにします。

    let s: String

    // 文字の列に変換
    let s = s.chars().collect::<Vec<_>>();

これは若干パフォーマンスが悪いです。一時期は Vec<u8> を使っていたんですが、デバッグ出力時に u8 が数字で出るのが不便だったのでやめました……

Vec

イテレータを Vec に変換する .collect::<Vec<_>> は頻出ですが、タイプがつらいので略記を用意してます。

自作トレイトをすべてのイテレータに実装させることで、 C# の拡張メソッドのようなことができます。

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}
// e.g.
let xs = (0..N).map(|i| i + 1).vec();

再帰

ローカル変数を利用する再帰関数について、7月に「 Rustのクロージャで再帰してみた 」という記事を書きました。クロージャは、mut な変数を書き換えないなら簡単に再帰にできるという結論です。

mut な変数を書き換えたいなら RefCell とかを使う、と記事では書きました。struct を定義したほうがいいこともあります。いずれにせよ手間なので、マクロで簡略化を図りたいと思っています。

参考