【自分用 | 初心者向け】Rustの競技プログラミングメモ

短め

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

考え方編

競プロとして編

計算量一覧

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 程度

問題の解き方を知るために

わからない時

• ABCのB問題程度
  • 全探索
  • 数学問題(式変形)

TLEになる時

• 前処理
  • 累積和の差(区間の総和 $S_i-S_{j-1}=S_j+\cdots+S_i$)
• Vecの.containsをHashSetの.insertに
  • もし追加できるなら追加し、trueを返す
  • そうでなければfalseを返す
• $O(N)$の処理$Q$個は$O(QN)$になる
  • 全探索を二分探索にするなど

文字列編

StringをVec<char>にして戻す

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

（別途sの定義が必要）

&strの中に特定の文字列以外が存在するか

let s = "aaaab";
let target = 'a';

if s.chars().any(|c| c != target) {
    println!("'a' 以外の文字が含まれています");
}

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

重複あり

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で関数自体を抜けられます。