【競プロ】Python使いがRustを「完全に理解する」までのTips

<font color='red'>**2023年AtCoder言語アップデートにより、Rustの環境は大きく変化しました。そのため、本記事はフリーズさせ、後日、2023年版に対応した記事を新規作成したいと思います。**</font>

筆者は、競プロのアルゴはPythonを使いつつ、マラソンはRustを使っております。前者は発想を短時間にコードにすることを重視し、後者はコーディングに時間をかけてでも高速性を確保したいからです。

その際、Pythonでできたアレを、Rustでどう書くんだっけ、と悩むことが多く、悩んだ結果を自分メモを兼ねてTipsにすることにしました。競プロに出てくるパターンを多く収録していますが、競プロ目的以外でも参考になるかと思います。とりありず、ざっと記述してみましたが、そのうち増やしたり、章立てを変えたりするかも知れません。

なお、参照がーとかトレイトがーとか、Rustそのものの入門には言及していませんので、適宜、別の記事や[本家TRPL](https://doc.rust-jp.rs/book-ja/)を参照ください。

コードの前提となるRustやクレートの種類、版数は、2022年2月時点でのAtCoderジャッジ採用版に準じます。

> rustcのVersion: 1.42.0; edition: 2018 など

# 0. Rustバージョン指定

Rustの外部クレートはCargo.tomlファイルでバージョン指定が可能ですが、Rust本体はeditionしか指定できません。AtCoderでの動作をローカル確認するために、Rust本体のバージョンを指定できる必要があります。

それには、Cargo.tomlと同じフォルダに、rust-toolchainという名前のファイルを作成して、中身を以下のようにします。

```
1.42.0
```

これだけで、Rustのバージョンが最新ではない1.42.0に固定されます。

> `rustup run 1.42.0 cargo コマンド` として、動的にバージョン指定することも可能です。競技プログラミング用ツールである`cargo compete`は、このコマンドを自動的に発行してくれます。

# 1. 入出力

## 1.1. 通常入力

`proconio::input` を使いましょう。

## 1.2. コマンドライン引数入力

コマンドライン引数を、文字列として認識するだけであれば普通に扱えばよいです。しかし、数値やリストとして扱いたい場合は、`proconio::input`をうまく使うと、入力値の変数割り当てが非常にスムーズです。

```Rust
use proconio::input;
use proconio::source::auto::AutoSource;
use itertools::Itertools;

fn main() {
    let args = std::env::args().collect_vec();
    let args_str = args[1..].join(" ");     // 実行プログラム名を省くため1..とする
    let source = AutoSource::from(&args_str[..]);

    input! {
        from source,
        arg1: usize,   // 引数1（型は適切なものを当てはめる）
        arg2: f64,     // 引数2（型は適切なものを当てはめる）
        args_ex: [usize; args.len() - 3],  // 残りの可変長（0個以上）の引数
    }

    println!("{} {} ..{:?}", arg1, arg2, args_ex);
}
```

## 1.3. インタラクティブ入力

インタラクティブ入力問題を、通常と同様に実装すると、入力が止まってしまう場合があります。inputマクロはデバッグモードでは1行ずつ、リリースモードでは一気に全て入力を読み込みます。また、inputマクロを複数回に分けて記述できるように、入力内容を保持し、2回目以降のinputマクロは保持した内容を処理します。そのため、リリースモードでは追加の入力を受け付けることができずに、止まってしまうのです。

これについては、リンク集でも示しているAtCoderの2020年言語アップテートの説明内にある[APC001-Cのサンプル](https://github.com/rust-lang-ja/atcoder-rust-base/blob/ja-all-enabled/examples/apc001-c-proconio.rs)にあるように、強制的に1行単位で入力させることで、回避可能です。提供されているサンプルのinput!マクロを少し改造してみました。

> 一度のinput!マクロで、行の終わりまで読み出すことが必要です。複数行読むことはかまいません。

```Rust
use proconio::input;

/* 入力サンプル
  以下で3と4、4と5は、input!が分かれるため入力行を変えること
  1 2
  3
  4
  5
*/

macro_rules! input(($($tt:tt)*) => (
    let stdin = std::io::stdin();  // Rust1.60までは分けて記述必要
    let mut stdin = proconio::source::line::LineSource::new(stdin.lock());
    proconio::input!(from &mut stdin, $($tt)*);
));

fn main() {
    let (n, m, t) = {
        input! { _n: usize, _m: usize, _t: usize, }
        (_n, _m, _t)
    };   // sub1での追加入力を可能にするため、ブロックで囲んで入力ロックを解放させる
    println!("n:{} m:{} t:{}", n, m, t);  // 一旦出力（インタラクティブ風に）
    sub1();
    sub2();
}

fn sub1() {
    input! { k: usize, }  // 関数がブロックになるため、新たなブロックは作らなくて良い
    println!("k:{}", k);  // 一旦出力
}

fn sub2() {
    input! { l: usize, }
    println!("l:{}", l);  // 最終出力
}
```

## 1.4. 出力

競プロでの典型的なリスト出力（空白区切りでの横出力、縦出力、二重リストの縦横出力）は、以下のように実装します。

> インタラクティブ出力の際には`fastout`は使ってはいけません。

```Rust
use proconio::fastout;
use itertools::Itertools;

#[fastout]
fn main() {
    let x = vec![1, 2, 3, 4, 5];
    println!("{}", x.iter().join(" "));   // リストの横出力
    println!("{}", x.iter().join("\n"));  // リストの縦出力
    let y = vec![vec![1, 2, 3, 4, 5], vec![6, 7, 8, 9, 10], vec![11, 12, 13, 14, 15]];
    println!("{}", y.iter().map(|x| x.iter().join(" ")).join("\n"));   // 二重リストの縦横出力
}
```

# 2. グローバル定数とグローバル変数

## 2.1. グローバル定数

Rustでのグローバル定数は普通に定義できます。

```Rust
const INF: usize = 1 << 60;    // グローバル定数
const DEBUG_LEVEL: usize = 2;  // グローバル定数

// DEBUUG_LEVEL以下なら標準エラー出力するマクロ
macro_rules! debug(($level:expr, $($tt:tt)*) => (if ($level) <= DEBUG_LEVEL { eprintln!($($tt)*); }));

fn main() {
    debug!(1, "{}", INF);
}
```

## 2.2. グローバル変数

一方、グローバル変数は単純には利用できません。例えば、上記の`const`を`static mut`に置き換えて、その変数にアクセスしようとすると、`use of mutable static is unsafe and requires unsafe function or block`というエラーが発生します。そのため、unsafeブロックを使ってアクセスするという、面倒なことになります。Rustではグローバル変数は利用できないものとする、と考えると簡便です。

しかしながら、グローバル変数を利用すると便利な場面が時々発生します。**特に、競技プログラミングのマラソン問題では、多数のクラス・メソッドで参照するが、入力データごとに値が変更される、`N`などの基本的な出題パラメータを、（入力データで1回だけ初期化する）グローバル変数として管理したくなります**。

これに対処するのが、lazy_staticや、once_cellといった外部クレートです。最近はonce_cellが主流となり、RustのNightly版でも取り込みされてきています。具体的な実装は次項を参照してください。

> グローバル変数を使わずに実装すると、`N`または`N`を含むクラスを`main()`で定義して、それを多数のクラス・メソッドの共通引数にする必要があり、煩雑です。また、`Display`といった標準ライブラリのトレイトについての自作クラスの実装を定義する時などは`N`を引数として指定できないため、標準ライブラリトレイトを使わない実装にしたり、あるいは、わざわざ自作クラスに`N`をコピーしたり、などと複雑化します。

## 2.3. 入力の一部をグローバル変数にする

インタラクティブ入力のところで紹介したマクロとlazy_staticとを組み合わせて、競技プログラミングの一部の入力を、グローバル変数にする例を紹介します。**マラソン問題において、非常に実用的な例**になっています。もちろん、インタラクティブ入力にも対応可能です。

> AtCoderで使えるlazy_staticでの実装にしていますが、once_cellにも簡単に修正可能です。

> 使用上の注意は、インタラクティブ入力での説明を参照ください。

```Rust
use proconio::input;
use lazy_static::lazy_static;

/* 入力サンプル
  以下すべて入力行を変えること
  1 2
  3
  4
  5
*/

macro_rules! input(($($tt:tt)*) => (
    let stdin = std::io::stdin();  // Rust1.60までは分けて記述必要
    let mut stdin = proconio::source::line::LineSource::new(stdin.lock());
    proconio::input!(from &mut stdin, $($tt)*);
));

lazy_static! {
    static ref _INPUT: (usize, usize) = {
        input! { n: usize, m: usize, } (n, m)
    };
    static ref N: usize = _INPUT.0;
    static ref M: usize = _INPUT.1;
}

fn main() {
    lazy_static::initialize(&_INPUT);  // lazy_staticの入力順を制御する命令
    let t = {
        input! { _t: usize, } _t
    };   // sub1での追加入力を可能にするため、ブロックで囲んで入力ロックを解放させる
    println!("N:{} M:{} t:{}", *N, *M, t);  // 一旦出力（インタラクティブ風に）
    sub1();
    sub2();
}

fn sub1() {
    input! { k: usize, }  // 関数がブロックになるため、新たなブロックは作らなくて良い
    println!("N:{} M:{} k:{}", *N, *M, k);  // 一旦出力（グローバル変数含む）
}

fn sub2() {
    input! { l: usize, }
    println!("N:{} M:{} l:{}", *N, *M, l);  // 最終出力（グローバル変数含む）
}
```

# 3. type

Rustは型システムが複雑であるため、この型は何だっけ？という問いが頻繁に発生します。そのため、Pythonのtype関数に相当する型名取得関数が欲しくなります。[非IT企業に勤める中年サラリーマンのIT日記](http://pineplanter.moo.jp/non-it-salaryman/2020/01/16/rust-typeof/)に記載があります。

```Rust
fn type_of<T>(_: T) -> String { std::any::type_name::<T>().to_string() }
```

なお、Rustでは`type`は型エイリアスを定義する予約語、`typeof`は使われていない予約語になっています。

> VSCodeを使うと、エディタにタイプヒントが表示されます。

# 4. list

Pythonのlistに相当するRustの型としては、Vecが一般的です。ただし、VecとIteratorとは簡単に相互変換できます。また、AtCoderでは、Iteratorの拡張として、機能豊富なitertoolsクレートもサポートしています。よって、Pythonのようにlistを扱いたい場合は、この3種を使い分けられると良いでしょう。

> その他に類似の型として、array、sliceがあります。

> Vecにはmutableすなわち自分自身に変更をかけて結果は()である関数（Pythonでの`x.sort()`のようなもの）が、sliceにはimmutableすなわち自分自身には変更をかけずに結果を返す関数（Pythonでの`sorted(x)のようなのも`）が、用意されているようです。sliceにある関数は、ほぼ、iteratorとitertoolsでカバーされています。

関数を一覧してみました。<font color='red'>**赤太字**</font>のところが注意です。

|Python list|Rust Vec|Rust Iterator|Rust itertools|
|---|---|---|---|
|append|<font color='red'>**push**</font>|#N/A|#N/A|
|extend|<font color='red'>**append**</font>|#N/A|#N/A|
|insert|insert|#N/A|#N/A|
|<font color='red'>**remove**</font>|#N/A|#N/A|#N/A|
|del|<font color='red'>**remove**</font>|#N/A|#N/A|
|pop|pop|#N/A|#N/A|
|clear|clear|#N/A|#N/A|
|index|#N/A|<font color='red'>**position**</font>|<font color='red'>**position**</font>|
|sort|sort|#N/A|sorted|
|reverse|reverse|rev|rev|
|copy|clone|cloned|cloned|
|len|len|<font color='red'>**count**</font>|#N/A|
|max/min|#N/A|max/min|max/min|
|all/any|#N/A|all/any|all/any|
|sum|#N/A|sum|#N/A|

<font color='red'>@horyu さんのコメントでposition関数を教えていただきました。</font>

Pythonのremoveに相当するrustの関数はありません。Rustのremoveはインデックスを指定するPythonのdelに相当します。Pythonのremoveを実現するには、Rustではpositionとremoveを組み合わせる必要があります。なお、Vec::retainは値指定ですが一致する全ての値を削除するため、Pythonのremoveとは動作が異なります。

# 5. max/min

## 5.1. 整数

整数や整数Vecのmax/minは、組み込み関数で算出可能です。

```Rust
use std::cmp::{min, max};

fn main() {
    assert_eq!(max(1, 2), 2);
    assert_eq!(min(1, -2), -2);
    let x = vec![1, 2, 3];
    assert_eq!(x.iter().max(), Some(&3));  // Vecのiterは参照であることに注意
    assert_eq!(x.iter().min(), Some(&1));
}
```

## 5.2. 浮動小数点数

同じような考えで浮動小数点数を扱おうとすると、``the trait `std::cmp::Ord` is not implemented for `{float}` ``というエラーが出るため驚きます。

これは、Rustでは、PartialOrd（一部の要素が比較可能）、Ord（すべての要素が比較可能）を厳密に区別しており、max/min/sortなどはOrdを要求しているにもかかわらず、floatはNaNがあるためOrdを実装していないためです。ちなみに、Eqも実装されていません。

このことは、かなりの宗教論争になっており、代替手段も大量に提案されています。しかしながら、競プロerとしては、**「浮動小数点の比較はWAの原因になるので、出来ないものとする」** と割り切りましょう。

なお、比較演算子（<, >など）は機能します。

<font color='Red'>max_by/min_by/sort_byといった関数をうまく使うことで、PartialOrdでも最大最小ソートを作ることは可能です。
またAtCoderでは、ordered-floatクレートの利用も可能です。</font>

## 5.3. float('inf')との比較

初期値をfloat('inf')にしてループの中で最小値を更新していく、というのは、Pythonで競プロをする際の基本的な打ち手の1つです。Rustのfloatにもinfに相当するものがありますが、比較に制約が出てしまうのと、そもそもintとfloatの比較ができません。

よって、c++と同様に適切な巨大整数をあてはめるのが得策です。0を並べる記法でもよいですが、以下の記法が簡便です。

```Rust
const INF: usize = 1e18 as usize;     // 1_000_000_000_000_000_000
const INF2: usize = 1 << 60;          // 1_152_921_504_606_846_976
```

なお、最大数を与える組み込み関数が存在しますが、+1するとオーバーフローしてしまうため、使い勝手は悪いです。

# 6. 主要なコレクション型

競プロで頻出の主要なコレクション型に対応する、PythonとRustの対応表を示します。

|Python|Rust|
|---|---|
|list|Vec|
|tuple|tuple|
|set|HashSet|
|dict|HashMap|
|deque|VecDeque|
|heapq|BinaryHeap|
|#N/A|BTreeSet|
|#N/A|BTreeMap|

なお、Rustには、Pythonには無いBTreeがあり、嬉しいです。以下では、Python慣れした人にとって、使い方にひと工夫がいるものを解説します。

## 6.1. defaultdict

Pythonにおけるdictは、RustではHashMapで実現します。競プロでは、存在しないキーのデフォルト値を自動的に与えるcollections.defaultdictが重宝されるのですが、同様の動作はentry関数とor_default関数で実現可能です。

```Rust
use std::collections::HashMap;

fn main() {
    let mut int2int: HashMap<usize, usize> = HashMap::new();
    *int2int.entry(1).or_default() += 2;
    assert_eq!(int2int[&1], 2);

    let mut int2vec: HashMap<usize, Vec<usize>> = HashMap::new();
    int2vec.entry(1).or_default().push(2);
    assert_eq!(int2vec[&1], vec![2]);
}
```

## 6.2. VecDequeと二次元盤面探索のコツ

Pythonにおけるdequeは、RustではVecDequeで実現します。

応用例として、二次元盤面における最短距離探索をbfsで実装します。しかしながら、以下の理由により、普通に実装すると`isize`型と`usize`型との変換が各所で登場し、見通しが悪くなってしまいます。

+ 隣接座標を求めるために加減算をする必要があり、`isize`型での計算が必要。
+ 座標を添字として盤面の状況を管理する必要があり、添字として`usize`型が必要。

ここで、オーバーフローを無視する`wrapping_add`を使うテクニックで、`usize`のままで、`!0`（最大数）を加算する=1減算する、という操作が可能になり、見通しが良くなります。

> リリースモード限定では、デフォルト動作でオーバーフローを無視しますので、通常の計算式で記述することも可能です。

実際に、[アルゴリズムと数学　演習問題集046-幅優先探索](https://atcoder.jp/contests/math-and-algorithm/tasks/abc007_3)を解いてみましょう。

```Rust
use proconio::input;
use proconio::marker::{Usize1, Chars};
use std::collections::VecDeque;

const DIJ: [(usize, usize); 4] = [(!0, 0), (0, !0), (1, 0), (0, 1)];

fn main() {
    input! {
        r: usize, c: usize,
        s: (Usize1, Usize1),
        g: (Usize1, Usize1),
        a: [Chars; r],
    }

    let mut todo: VecDeque<(usize, (usize, usize))> = VecDeque::new();
    todo.push_back((0, s));
    let mut seen = vec![vec![false; c]; r];

    while let Some((d, pos)) = todo.pop_front() { // Bfsで全頂点を巡る
        if seen[pos.0][pos.1] { continue; }
        if pos == g {   // 頂点gに到達したら終了
            println!("{}", d);
            break;
        }
        seen[pos.0][pos.1] = true;
        for &dij in &DIJ {   // 隣接頂点を全てチェック
            let next = (pos.0.wrapping_add(dij.0), pos.1.wrapping_add(dij.1));
            if next.0 < r && next.1 < c && a[next.0][next.1] == '.' {
                todo.push_back((d + 1, next))
            }
        }
    }
}
```

## 6.3. heapq

Pythonにおけるheapqは、RustではBinaryHeapで実現します。ところがRustのBinaryHeapは最大値を優先するキューになっており、Pythonとは動作が逆ですので、std::cmp::Reverseと組み合わせて利用します。

これまでの応用も兼ねて、[競プロ典型90問013-Passing](https://atcoder.jp/contests/typical90/tasks/typical90_m)を解いてみましょう。

```Rust
use proconio::{input, fastout};
use proconio::marker::Usize1;
use std::collections::{HashMap, BinaryHeap};
use std::cmp::Reverse;

const INF: usize = 1e18 as usize;     // 1_000_000_000_000_000_000

#[fastout]
fn main () {
    let graph = Graph::new();
    let d1 = graph.dijkstra(0);
    let d2 = graph.dijkstra(graph.n - 1);
    for k in 0..graph.n {
        println!("{}", d1[k] + d2[k]);
    }
}

struct Graph {
    n: usize,
    adj: HashMap<usize, Vec<(usize, usize)>>,
}

impl Graph {
    fn new() -> Self {
        input! { n: usize, m: usize, }
        input! { e: [(Usize1, Usize1, usize); m], }     // Usize1で入力時に0-indexedに補正

        let mut adj: HashMap<usize, Vec<(usize, usize)>> = HashMap::new();
        for &(a, b, c) in &e {
            adj.entry(a).or_default().push((b, c));     // defaultdictっぽい記法
            adj.entry(b).or_default().push((a, c));     // 同上
        }
        Self { n: n, adj: adj, }
    }

    fn dijkstra(&self, start: usize) -> Vec<usize> {
        let mut dist = vec![INF; self.n];
        dist[start] = 0;
        let mut heapq = BinaryHeap::new();
        heapq.push((Reverse(0), start));              // 初期値をReverseして入れる
        while let Some((Reverse(d), pos)) = heapq.pop() { // Rustっぽい記法でheapqからReverseして取り出す
            if d != dist[pos] { continue; }
            for &(next, cost) in &self.adj[&pos] {
                let next_d = d + cost;
                if next_d < dist[next] {
                    heapq.push((Reverse(next_d), next));  // heqpqにはReverseして入れる
                    dist[next] = next_d;
                }
            }
        }
        dist
    }
}
```

## 6.4. BTreeSet/BTreeMap

BTreeは、順序を維持したまま挿入削除しつつ、高速に2分探索できる型です。Pythonの標準ライブラリでは手が出ない問題に対応できます。

使い方の例として、[ABC241-D:Sequence Query](https://atcoder.jp/contests/abc241/tasks/abc241_d)を解いてみましょう。

```Rust
use proconio::{input, fastout};
use std::collections::BTreeSet;
use std::ops::Bound::*;

#[fastout]
fn main() {
    input! { q: usize, }
    let mut bset = BTreeSet::<(isize, usize)>::new();
    for i in 0..q {
        input! { query: usize, x: isize, }
        if query == 1 {
            bset.insert((x, i));       // ユニークにするためiをつけてタプルして登録
        } else {
            input! { k: usize, }
            let ans = if query == 2 {  // x以下=(x+1)未満の逆順、k番目
                bset.range((Unbounded, Excluded(&(x + 1, 0)))).rev().nth(k - 1)
            } else {                   // x以上、k番目
                bset.range((Included(&(x, 0)), Unbounded)).nth(k - 1)
            };
            println!("{}", ans.unwrap_or(&(-1, 0)).0);
        }
    }
}
```

# 7. bisect

順序を維持したまま挿入削除の途中段階での処理が必要な場合はBTreeを使いますが、途中段階での処理が不要であれば、与えられた数列をソートして2分探索をするのが効率的です。Pythonには、このためのbisectライブラリ（C++でのlower_bound、upper_boundに相当するもの）が用意されています。

ところが、Rustには残念ながらPythonのbisect相当するライブラリがありませんので、自分で作る必要があります。

<font color='Red'>@magicant さんから slice::partition_point を紹介いただきました。C++11で導入されたlower_bound / upper_boundの上位互換ですね。残念ながらAtCoder採用のRust版数では使えませんが、将来、版数upしたら、使えると思います。</font>

<font color='Red'>筆者にて実験をしてみたところ、現在のAtCoderで利用できる外部クレートのitertools::partitionなら、動作としては満足します。しかしながら計算量が$O(n)$であるため使えませんでした。lower_bound / upper_boundは、$O(\log n)$である必要があります。なお、slice::partition_pointは$O(\log n)$でした。</font>

<font color='Red'>AtCoderでは、supersliceクレートの利用が可能です。これを使うと、今回作成したlower_bound / upper_boundと全く同一の使い方で、さらに高速な結果を得られることがわかりました。</font>

なお、浮動小数点の比較は出来ないものとする、と言いましたが、PartialOrdを前提にするだけで実装できますので、結果的に浮動小数点数でも使えるトレイトになっています。

```Rust
fn main() {
    let x = vec![1, 1, 2, 2, 4, 4, 4];
    assert_eq!((0..=5).map(|i| x.lower_bound(&i)).collect::<Vec::<usize>>(),
        vec![0, 0, 2, 4, 4, 7]);
    assert_eq!((0..=5).map(|i| x.upper_bound(&i)).collect::<Vec::<usize>>(),
        vec![0, 2, 4, 4, 7, 7]);
}

trait Bound<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: PartialOrd> Bound<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let (mut low, mut high) = (0, self.len());
        while low + 1 < high {
            let mid = (low + high) / 2;
            if self[mid] < *x { low = mid; } else { high = mid; }
        }
        if self[low] < *x { low + 1 } else { low }
    }

    fn upper_bound(&self, x: &T) -> usize {
        let (mut low, mut high) = (0, self.len());
        while low + 1 < high {
            let mid = (low + high) / 2;
            if self[mid] <= *x { low = mid; } else { high = mid; }
        }
        if self[low] <= *x { low + 1 } else { low }
    }
}
```

# 8. argmax/argmin/argsort

Pythonでもargmax/argmin/argsortは、Numpyを必要とする、かなり応用に属する関数です。しかしながら、競プロで使いたくなる場面が多いため、Rustでの実装をしておきます。

```Rust
use itertools::Itertools;
use std::cmp::Reverse;

fn main() {
    let x = vec![4, 0, 1, 6, 5];
    assert_eq!(x.argmax(), Some(3));
    assert_eq!(x.argmin(), Some(1));
    assert_eq!(x.argsort(), vec![1, 2, 0, 4, 3]);
    assert_eq!(x.argsort_reverse(), vec![3, 4, 0, 2, 1]);
}

trait ArgOrd<T> {
    fn argmax(&self) -> Option<usize>;
    fn argmin(&self) -> Option<usize>;
    fn argsort(&self) -> Vec<usize>;
    fn argsort_reverse(&self) -> Vec<usize>;
}

impl<T: Ord> ArgOrd<T> for [T] {
    fn argmax(&self) -> Option<usize> {
        (0..self.len()).max_by_key(|&i| &self[i])
    }

    fn argmin(&self) -> Option<usize> {
        (0..self.len()).min_by_key(|&i| &self[i])
    }

    fn argsort(&self) -> Vec<usize> {
        (0..self.len()).sorted_by_key(|&i| &self[i]).collect_vec()
    }

    fn argsort_reverse(&self) -> Vec<usize> {
        (0..self.len()).sorted_by_key(|&i| Reverse(&self[i])).collect_vec()
    }
}
```

> `argsort`と`argsort_reverse`を別関数で記述しているように、Rustの関数には「デフォルト引数」という概念がありません。

# 9. 有理数

`num-rational`を使いましょう。

# 10. 乱数

Rustのrandクレートはクセがあるため、慣れが必要です。なお、バージョン間の非互換が結構ありますので注意してください。AtCoder採用バージョンでの実装例を示します。

> NumPyのGenarator記述方式（最新の推奨方式）による乱数と同様の記法になっています。

```Rust
use rand::prelude::*;
use itertools::Itertools;

fn main() {
    let mut rng = rand::thread_rng();
    let x1: f64 = rng.gen();             // random.random()
    let x2 = rng.gen::<usize>() % 10;    // random.randint(0, 9)
    let x3 = rng.gen_range(15, 31);      // random.randint(15, 30)
    let mut v = vec![1, 2, 3, 4, 5];
    let x4 = v.choose(&mut rng).cloned().unwrap();  // raodom.choice(v)
    let v1 = v.choose_multiple(&mut rng, 3).cloned().collect_vec();  // random.sample(v, 3)
    v.shuffle(&mut rng);                 // random.shuffle(v)
}
```

# 11. タイマー

Rustのタイマーは、慣れるとPythonより使いやすいです。

```Rust
use std::time::Instant;

fn main() {
    let timer = Instant::now();  // タイマーセット
    sub(&timer, 1.9);
}

fn sub(timer: &Instant, limit: f64) {
    while timer.elapsed().as_secs_f64() < limit {
        // 山登りなど、時間ギリギリまで最適化する操作
    }
}
```

# 12. リンク集

- [AtCoder 2020年言語アップデート以降の環境](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update)
- [Jan 2023 Language Update ライブラリ案](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/Jan-2023-Language-Update-%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA%E6%A1%88)