【自分用】Rust - つい忘れがちな競技プログラミングメモ

この記事を閲覧する人のために

• 文章が雑です
• 自分のMarkdownをコピペして一部修正しただけです

短め

• String.repeat(usize)で文字列を繰り返した値を得ることができます

考え方編

Rustは型推論が強力なので…

• ターボフィッシュ(::<usize>など)が使える場合はそれだけで型を指定したほうがいい
  • そうでないなら変数で指定する
  • なぜ？
    • ターボフィッシュに慣れるため
    • .sum()などで忘れないようにするため

競プロとして編

計算量一覧

2sec制限のとき

計算量	実行できる規模（ざっくり）
O(N)	1〜2 × 10⁸（1〜2億）
O(N log N)	2〜3 × 10⁷（2千万〜3千万）
O(N√N)	1〜3 × 10⁶（100万〜300万）
O(N²)	2〜5 × 10⁴（2万〜5万）
O(N³)	300〜500 程度
O(2^N)	N ≤ 22〜25 程度
O(N!)	N ≤ 10 程度

文字列編

StringをVec<char>にして戻す

let v: Vec<char> = s.chars().collect();
let s2: String = v.iter().collect();

（別途sの定義が必要）

文字列の中に特定のパターンが存在するか

重複あり

fn count_pattern_overlapping(haystack: &str, needle: &str) -> usize {
    if needle.is_empty() {
        return 0;
    }

    let mut count = 0;
    let mut pos = 0;

    while let Some(found) = haystack[pos..].find(needle) {
        count += 1;
        pos += found + 1; // 1文字だけ進める → オーバーラップを検出
    }

    count
}

重複なし

fn count_pattern(haystack: &str, needle: &str) -> usize {
    haystack.matches(needle).count()
}

Vec編

Vecの中に存在しているか

let v = vec![1, 2, 3, 4, 5];

if v.contains(&3) {
	println!("3 は存在します！");
} else {
	println!("3 は存在しません…");
}

Vecの.contains()は、参照を渡すとその参照元が存在するかを判定してくれます。

便利機能編

for文、while文、loop文の「ラベル」

'label: for i in 0..5 {
    for j in 0..5 {
        if j == 3 {
            break 'label;   // 外側のループを抜ける
        }
    }
}

ループする文の前にシングルクォーテーション(')、ラベル名、コロン(:)をつけることで、breakやcontinueするfor文を指定できます。
関数の定義の場合は、returnで関数自体を抜けられます。