こんにちは、今年は一念発起して、Rustで競プロに取り組みました。

きっかけ

Rustはもともと興味があって勉強していました。
カニ本やRust By Exampleは終えていて、基本はおさえたつもりですが、そのあと特に書きたい題材もなくどうしようかと思っていました。

そんなとき、競プロから始めるといいというLTがあり、競プロにも興味があったので取り組むことにしました。

競プロ、というよりもアルゴリズム基礎

とはいえ、直接AtCoderなどに参加したわけでもなく、アルゴリズムを一度基礎から学んでみたかったので、問題解決力を鍛える！アルゴリズムとデータ構造を進めることにしました。

ググればRustでAtCoderに挑戦する記事はたくさん出てくるので、実際のコンペなどが知りたい方はそちらを参照してください。

学び

変数で、値をもらうのか、参照をもらうのか、可変にするのか

単一のi32やf64なら、コピーが渡されるので、そのまま引数で受け取っても大丈夫ですが、

fn some(x: i32, y: f64) -> i32 { 1i32 }

文字列やベクターを受け取る場合は、大体の場合、変数自体ではなく、変数が持つ値を知りたいので、参照型で渡すだけで十分ですね。
逆に可変にしたいときは、ちゃんとmutを指定する必要があります。
Rustはここらへんの使い方が厳しいので、最初は大変でしたが、慣れてくるとメモリをどう扱っているのか意識できるので、便利&安全だと思います。

fn q04_6(i: usize, w: i32, a: &[i32], mem: &mut Vec<bool>) -> bool {
    /* do something */
    return true
}

計算時間

雑に下記のコードで時間を算出できて便利でした

use std::time::Instant;

let start = Instant::now();
// some calculations
let duration = start.elapsed();
println!("{:?}", duration);

Vectorとイテレータ

ベクターを受け取ってループ処理したり、ベクターを一括で処理したり、割とモダンに書けるのでやりやすいです。

fn do_some(a: &Vec<i32>) {
    for x in a.iter() {
        println!("{}", x);
    }
}

let b: Vec<i32> = vec![1, 2, 3];
let c = b.iter().map(|x| x / 2).collect();

アルゴリズムに関する理解

今のところ5章の動的計画法までしかすすんでいませんが、
再帰だったり、分割統治法だったり、なんとなくの理解だったものを自分で実装すると、理解がすすんでよかったです。

リポジトリ

取り組んでいるコードなどはこちらです。
https://github.com/ieiriyuki/algo_datastr/tree/dev

正解のコード例もC++ですが公開されているので、参考にしつつRustで実装しなおすのも勉強になります。
https://github.com/drken1215/book_algorithm_solution

今後やりたいこと

今のところ、文字列操作ができていないので、文字列も扱えるようになりたいですね。
Rustの文字列はString型とstr型となれるまで使い方がわかりにくいのと、
スライスしても日本語のようにマルチバイト文字だとうまくスライスできないのがやっかいですね。

外部クレートも使いこなせていないので、可能な限り使ってみたいです。
データ分析のクレートはばんくしさんがまとめてくれていますね。

終わり

現場からは以上です。
みなさんもRust&競プロやりましょう!

Rustで競プロに挑戦