Rustで競技プログラミング スターターキット

# はじめに

自分の経験から、Rustで競技プログラミングをやるときに役に立ちそうなことをまとめました

Rustで競技プログラミングを始めた方がRust特有の引っかかりどころに引っかかることなく、
より問題の本質に集中できるようになれば幸いです:muscle:

# 対象

[プログラミング言語Rust](https://doc.rust-jp.rs/book-ja/)をだいたい理解したけど競技プログラミングでRustを使うのは不安な人

# 環境構築

とりあえず

* RUST_BACKTRACE=1

を環境変数に設定しておく

エディタはなんでも良いですが

* 入力補完 (rust-analyzer)
* 保存時か任意のタイミングで自動整形 (Rustfmt)
* 自動コンパイル & エラー箇所の表示

を導入しておくのをおすすめします。導入方法はググれば大丈夫だと思います

## rustup override

`rustup override`を使うことでカレントディレクトリ以下で使うRustのバージョンを指定できます。
詳細は`rustup override help`で確認してください。

```bash
$ rustup install 1.42.0
# カレントディレクトリ以下でRust 1.42.0を使う
$ rustup override set 1.42.0
```

# サイトごとの注意

## Atcoder

* ~~Rustのバージョンが古い(執筆時現在1.15.1)~~
    * ~~いくつかの新しい機能が使えない~~
* Rust1.42にアップデートされた:tada:
    * いくつかのクレートが使える https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update

## Codeforces

* Rustのバージョンは比較的新しい
* **32bit**環境で動いている
    * usizeが32bitの大きさなので要注意

## AOJ

* Rustのバージョンは1.41.1
    * 対応言語の一覧は[こちら](http://judge.u-aizu.ac.jp/onlinejudge/status_note.jsp)

## yukicoder

* とくになし

# 入出力

## 入力

`scanf()`のようなものはありません。
AtCoderの場合は[proconio](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update#proconio)が使えます。

特に工夫せずにやる場合は、[read_to_string](https://doc.rust-lang.org/std/io/trait.Read.html#method.read_to_string)や[read_line](https://doc.rust-lang.org/std/io/struct.Stdin.html#method.read_line)で標準入力からStringを受け取り、[str::split_whitespace](https://doc.rust-lang.org/std/primitive.str.html#method.split_whitespace)で分解して[str::parse](https://doc.rust-lang.org/std/primitive.str.html#method.parse)でパースしていきます。

### 例

ABC037 B - 編集
https://beta.atcoder.jp/contests/abc037/tasks/abc037_b
の入力を行うコード
$N$ $Q$
$L_1$ $R_1$ $T_1$
$:$
$L_Q$ $R_Q$ $T_Q$

#### 一度に全部読み込むパターン

エラー処理はてきとうです

```rust
use std::io::Read;

fn main() {
    let mut buf = String::new();

    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();

    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();

    let n: usize = iter.next().unwrap().parse().unwrap();
    let q: usize = iter.next().unwrap().parse().unwrap();

    let lrt: Vec<(usize, usize, u64)> = (0..q)
        .map(|_| {
            (
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
            )
        })
        .collect();
}
```

#### マクロを使ってみる

毎回上のようなコードを書くのはしんどいので、自分はこんな感じのマクロで入力を処理しています。
こちらは一行ごとに入力を処理しています。

```rust
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

fn main() {
    // 一行読み込み、空白で分解してusize２つパースする
    let (n, q) = get!(usize, usize);
    // usize usize u64 をq行読む Vec<(usize, usize,u64)> 
    let lrt = get!(usize, usize, u64; q);
}
```

マクロを使った例は上のパターンに比べてかなり遅いですが
$10^5$程度までの入力であればそれが原因でTLE (Time Limit Exceeded)になることはまずないのではないかと思います。

### ベンチマーク

最後にそれぞれのやり方で入力を処理したときの実行時間を計測したので載せておきます。環境はWSL上のDebianです。


#### 計測方法

```
yes 1 | head -n [行数] | time ./[実行ファイル]
```

#### ベンチマークに使ったコード

一度に全部読み込むコード

```rust
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    // 条件を同じにするため一度Vecに貯める
    let v = buf.split_whitespace()
        .map(|x| x.parse::<u32>().unwrap())
        .collect::<Vec<_>>();

    // 合計を出力
    println!("{}", v.into_iter().sum::<u32>());
}
```

マクロを使ったコード

```rust
// マクロの定義は省略
fn main() {
    println!("{}", get!(u32; 10000000).into_iter().sum::<u32>());
}
```

#### 結果

一回計測しただけなのでおおまかな参考程度に

|入力行数|一度に全部読み込む(秒)|上のマクロを使う(秒)|
|---|---|---|
|$10^5$|0.01|0.02|
|$10^6$|0.04|0.11|
|$10^7$|0.29|1.08|

参考: [Rust の標準入出力は(何も考えないで使うと)遅い - Qiita](https://qiita.com/tubo28/items/41eeb0dfa1ebbccb1ddc)

## 出力

基本的に`println!()`で良いですが出力の行数が多い場合は [BufWriter](https://doc.rust-lang.org/std/io/struct.BufWriter.html) を使いましょう。使い方はベンチマークを参照。
浮動小数点を出力する場合も桁数を気にせずに`println!("{}", x)`のように書いて**大丈夫**です。

### ベンチマーク

今回はオンライン上で実行しました。
`10^5`行"yes"と出力したときの実行時間を計測しました。

#### println!

```rust
fn main() {
    for _ in 0..100_000 {
        println!("yes");
    }
}
```

#### BufWriter

```rust
use std::io::{stdout, BufWriter, Write};

fn main() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    for _ in 0..100_000 {
        writeln!(out, "yes").unwrap();
    }
}
```
#### 結果

一回計測しただけなのでおおまかな参考程度に

||Atcoder(ms)|Codeforces(ms)|Yukicoder(ms)|
|---|---|---|---|
|`println!`|160|421|164|
|`BufWriter`|4|15|4|

理由はわからないですがCodeforcesだと特に差が大きいですね。
Codeforcesは最後にシステムテストがあるので、出力行数が多いときはとりあえずBufWriterを使うのが良いと思います。

参考: [Rustで高速な標準出力 | κeenのHappy Hacκing Blog](http://keens.github.io/blog/2017/10/05/rustdekousokunahyoujunshutsuryoku/)

### おまけ

```rust
fn with_bufwriter<F: FnOnce(BufWriter<StdoutLock>) -> ()>(f: F) {
        let out = stdout();
        let writer = BufWriter::new(out.lock());
        f(writer)
}
```

みたいなのをスニペットに登録しておけば便利かもしれません。

## デバッグ出力

追記: 2019/01/18
Rust 1.32で[dbgマクロ](https://doc.rust-lang.org/std/macro.dbg.html)がstableに入りましたのでそちらを使うのもよいです

printデバッグをする場合、以下のようなスニペットがあると便利かもしれません

```rust
macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
  }
```

```rust
fn main() {
    let x = vec![1, 2, 3];
    let y = vec![4, 5, 6];
    // x = [1, 2, 3], y = [4, 5, 6], と出力する
    debug!(x, y);
}

```

# Entry API

[HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html)や[BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html)には[Entry API](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.entry)というのが実装されていています。
連想配列の操作をするときに重要なので、聞いたことがない方は軽く予習しておくと良いと思います。

# 逆順で〇〇するには？？

逆順でソートしたかったり、小さい順に値が出てくる[BinaryHeap](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html)が欲しいときがあります。
そういうときは[std::cmp::Reverse](https://doc.rust-lang.org/std/cmp/struct.Reverse.html)で比較を逆転させます。

```rust
use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut v = vec![5, 2, 1, 4, 3];

    // 通常は昇順でソートされるが、Reverseで比較が逆になるので降順にソートされる。
    v.sort_by_key(|&x| Reverse(x));
    assert_eq!(&v, &[5, 4, 3, 2, 1]);

    // BinaryHeapは値が大きい順で出てくるmax-heapだがReverseを使ってmin-heapにできる。
    let mut min_heap: BinaryHeap<Reverse<usize>> = v.into_iter().map(Reverse).collect();

    assert_eq!(min_heap.pop(), Some(Reverse(1)));
    assert_eq!(min_heap.pop(), Some(Reverse(2)));
    assert_eq!(min_heap.pop(), Some(Reverse(3)));
    assert_eq!(min_heap.pop(), Some(Reverse(4)));
    assert_eq!(min_heap.pop(), Some(Reverse(5)));
}
```

# 浮動小数点の比較

例えば
以下のコードのようにf64の配列をソートしようとするとコンパイルが出来ません。

```rust
let mut v: Vec<f64> = vec![0.1, 1.0, 2.0];
// コンパイルできない！！
// error[E0277]: the trait bound `f64: std::cmp::Ord` is not satisfied
v.sort();
```

同じ理由でBinaryHeap<f64>も作ることが出来ません。

```rust
use std::collections::BinaryHeap;
// これもだめ
let heap: BinaryHeap<f64> = BinaryHeap::new();
```

エラーメッセージの通り、f64, f32は[Ord](https://doc.rust-lang.org/std/cmp/trait.Ord.html)トレイトを実装していないためエラーになります。

## なぜ浮動小数点型に[Ord](https://doc.rust-lang.org/std/cmp/trait.Ord.html)トレイトを実装できないのか？

浮動小数点には[NAN](https://doc.rust-lang.org/std/f64/constant.NAN.html)というのがありますが、NANとの比較はすべて`false`になります

```rust
assert_eq!(std::f64::NAN > 0.0, false);
assert_eq!(std::f64::NAN == 0.0, false);
assert_eq!(std::f64::NAN < 0.0, false);
```

ところで、Ordトレイトは[cmp](https://doc.rust-lang.org/std/cmp/trait.Ord.html#tymethod.cmp)メソッドを実装することを要求しています。

```rust
pub trait Ord: Eq + PartialOrd<Self> {
    fn cmp(&self, other: &Self) -> Ordering;
    // .. 省略
}
```

```rust
pub enum Ordering {
    Less,
    Equal,
    Greater,
}
```

ここで例えば`Ord::cmp(&std::f64::NAN, &0.0)`がなにを返せばよいのか考えると

`Ordering::Less`を返す  => `(NAN < 0.0) == false`なので矛盾する
`Ordering::Equal`を返す => `(NAN == 0.0) == false`なので矛盾する
`Ordering::Greater`    => `(NAN > 0.0) == false`なので矛盾する

となって何を返しても矛盾してしまいます。よって浮動小数点にOrdトレイトを実装することは出来ません。

## じゃあどうするの？

浮動小数点型も[PartialOrd](https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html)トレイトは実装しているので、PartialOrdトレイトを実装している型に無理やりOrdトレイトを実装するラッパstructを作ります。NANを比較しようとした場合はパニックを起こします。

```rust
// Partial orderなものをTotal orderにする
#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}
```

つかいかた

```rust
let mut v: Vec<f64> = vec![0.1, 1.0, 2.0];
// ソートできる！
v.sort_by_key(|&x| Total(x));

// f64のBinaryHeapもできる！
let heap: BinaryHeap<Total<f64>> = BinaryHeap::new();

```

# 整数のオーバーフロー

RustではDebugビルド時のみオーバーフロー、負のオーバーフローを**実行時に検出**します。
オンライン上で実行されるときはReleaseビルドで実行されるのでオーバーフローは検出されないので注意しましょう。

# デフォルトの整数型

型を指定しなかった場合や推論できないとき、整数は`i32`になります。
オーバーフローしないように注意しましょう。
個人的には、型名を毎回明示的につけるのがおすすめです。

```rust
fn main() {
    let x = 0; // <= i32
}
```

# スタック領域を増やす

深めの再帰関数を呼び出すとスタックオーバーフローを起こすことがあります。(Codeforcesで一回経験しました)
そういうときは[std::thread::Builder](https://doc.rust-lang.org/std/thread/struct.Builder.html)を使ってスタックサイズを指定しつつ別のスレッドを作ることで解決できます。

```rust
fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(32 * 1024 * 1024) // 32 MBのスタックサイズ
        .spawn(|| {
            // ここで深い再帰を実行
        })
        .unwrap()
        .join()
        .unwrap();
}
```

参考1: https://stackoverflow.com/a/44042122
参考2: [rust - How to set the thread stack size during compile time? - Stack Overflow](https://stackoverflow.com/questions/29937697/how-to-set-the-thread-stack-size-during-compile-time/29980945)

# 二分探索について

[slice::binary_search](https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search)というメソッドがありますが、

> containing the index where a matching element could be inserted while maintaining sorted order

とあるように、そのインデックスに挿入したときにソート済みの状態になるように保証されているだけなので、
C++のlower_boundやupper_boundとは**全然違います**

例えば、同じ値が並んでいる場合どのインデックスが帰ってくるかは**バージョンによっても違います**

```rust
fn main() {
    let v = vec![4,4,4];
    // Rust 1.21.0         -> Ok(1)
    // Rust 1.26.0-nightly -> Ok(2)
    println!("{:?}", v.binary_search(&4) );
}
```

しょうがないので、lower_bound, upper_bound相当がほしいときは自分で実装しましょう
自分が実装した例はこちら
https://github.com/hatoo/competitive-rust-snippets/blob/master/src/binary_search.rs
`#[snippet = ".."]`みたいな行は外部ツール用なので無視してください

# next_permutation

ありません。
自分は[bluss/permutohedron](https://github.com/bluss/permutohedron/blob/master/src/lexical.rs)からコピペしています。

# bitset

ありません。
自分が実装した例はこちら
https://github.com/hatoo/competitive-rust-snippets/blob/master/src/bitset.rs

# なんかうまいスニペットの管理方法ある？

こちらに記事を書きましたのでよければ参考にしてください:bow:
[Rustで競技プログラミングをするときの"スニペット管理"をまじめに考える(cargo-snippetの紹介)](https://qiita.com/hatoo@github/items/5c6814e72ddd2ecaf48f)