Cover Image for 【Rust】競技プログラミングでよく使うものまとめ

【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>>()
}

参考