【Rust】競技プログラミングでよく使うものまとめ
目的
競技プログラミングをRustで解いているが、よく使うものを忘れてしまうのでまとめる (随時更新)
言語機能
数学
絶対値: abs
x.abs()
差の絶対値: abs_diff
x.abs_diff(y)
べき乗: pow
let result = x.pow(2) // 2乗
平方根: sqrt
x.sqrt()
float系にしか生えてないメソッド
イテレーター
skip
vec.iter().skip(2)
イテレーターをskipできる。
何が嬉しいかというと、vec
から i
以降の サブセットを作ることができる
max_by_key / min_by_key
関数で計算した結果を元に最大/最小の要素を Option<T>
で返す。mapした結果の最大/最小を求めるという処理をショートハンドで書ける。
// max
vec.iter().max_by_key(|x| (x-100).abs())
// min
vec.iter().min_by_key(|x| (x-100).abs())
zip
二つの iter を一つの iter に結合できる。 注意点としては、長さが違う iter を zip すると短い方に合わせた長さになる。
let o = [1, 3, 5, 7];
let e = [2, 4, 6];
let mut iter = o.iter().zip(e.iter()); // [(1,2), (3,4), (5,6)]
String
find / rfind
find は 頭から、rfindは末尾から char を探索
let s = "abcdefg|gfedcba";
let index_a = s.find('a') // Some(0)
let index_a = s.rfind('a') // Some(14)
ライブラリ系
TBD
コードスニペット
作ったのもので使いまわせそうなものがあればメモしていく
2点間の距離
fn distance(x: &Vec<i32>, y: &Vec<i32>) -> f32 {
let sum = x
.iter()
.zip(y.iter())
.map(|(x, y)| x.abs_diff(*y).pow(2))
.sum::<u32>() as f32;
sum.sqrt()
}
エラトステネスの篩
素数を求めるためのエラトステネスの篩(ふるい) 個人的には、エイヤフィヤトラの櫛(くし)みたいなやつなんだっけ...となって毎回名前が思い出せない
fn sieve_of_eratosthenes(x: usize) -> Vec<usize> {
let mut num_list = vec![true; x + 1];
num_list[0] = false;
num_list[1] = false;
for i in 2..=(x as f64).sqrt() as usize {
if !num_list[i] {
continue;
}
for j in (i * 2..=x).step_by(i) {
num_list[j] = false;
}
}
num_list
.iter()
.enumerate()
.filter(|(_, &flag)| flag)
.map(|(i, _)| i)
.collect::<Vec<usize>>()
}