📒

RustでAtCoderに挑戦してみて気づいたポイントまとめ

5 min read 1

慣れていないとRustではコンパイルエラーが頻発します。AtCoderの簡単な問題に触れることで、つまづきがちなところをまとめていきたいと思います。

(随時更新していきます)

挑戦した問題

  • ABC
    • ABC195 ~ ABC204の灰色、茶色

input

省略可能な配列サイズ

このように受け取るものは

    input! {
        n: usize,
        arr: [usize; n],
    }

下のように省略できる。

    input! {
        arr: [usize],
    }

ただし、なんだかんだ n が必要な場面は多いので省略しない形で書いた方が良さそう。

文字列をはじめからVec<char>にしておく

use proconio::{input, marker::Chars};
 
fn main() {
    input! {
        s: Chars,
    }

型推論でi32になってしまうことに注意

問題例:

https://atcoder.jp/contests/abc200/tasks/abc200_c

下のコードで vec の型を省略してしまうと、i32で推論されてしまう。その結果 a * (a - 1) / 2 のところで誤った答えになってしまう。(コンパイルエラーではなく計算結果に誤りが生じる)

use proconio::input;
 
fn main() {
    input! {
        n: usize,
        arr: [usize; n],
    }
    let mut vec: Vec<i64> = vec![0; 200usize];
    for a in &arr {
        vec[ a % 200 ] += 1;
    }
    let mut ans: i64 = 0;
    for a in &vec {
        ans += a * (a - 1) / 2;
    }
    println!("{}", ans);
}

usizeで引き算するとオーバーフローが発生するときがある

問題例: https://atcoder.jp/contests/abc203/tasks/abc203_c

下のコードで標準入力をusizeで受け取るとオーバーフローが発生するときがある。

use proconio::input;
 
fn main() {
    input! {
        n: isize,
        k: isize,
        mut arr: [(isize, isize); n],
    }
    arr.sort_by_key(|k| k.0);
    let mut ans = 0;
    let mut money = k;
    for &(a, b) in &arr {
        if a - ans > money {
            ans += money;
            money = 0;
            break;
        } else {
            money += b - (a - ans);
            ans = a;
        }
    }
    if money > 0 {
        ans += money;
    }
    println!("{}", ans);
}

変数

変数の入れ替え

// あらかじめ use std::mem::swap; しておくこと
// x,y = y,x のようなことができる
swap(&mut x, &mut y);

計算

f64での累乗

pow() ではなく powi() を使う。指数部分もf64の場合は powf() を使う。

切り上げ/切り捨て

切り上げはceil()で切り捨てはfloor()

四捨五入は使う機会あまり無いと思うけど round()

ループ

降順の連番ループ

for i in (0..n).rev() で n - 1, n - 2, ... 0 のループになる。

無限ループ

loop {
  // 無限ループ. while true {}の代わりに使える
}

配列

sort()は破壊的メソッド

arr = arr.sort(); のようなことをするのではなく、単に arr.sort(); をやれば良い。

sort_by_key()でソートのアルゴリズムを指定できる

    input! {
        n: usize,
        mut arr: [(String, i64); n],
    }
    arr.sort_by_key(|k| k.1); // -k.1とすれば降順

和を取る

    arr.iter().sum();

min/maxを取る

    let a = arr.iter().min();
    let b = arr.iter().max();
    // 値を使って計算するためにはunwrap()が必要
    a.unwrap() + b.unwrap();

Set

Setの基本的な使い方

ドキュメント: https://doc.rust-lang.org/std/collections/struct.HashSet.html

use std::collections::HashSet;
 
fn main() {
    let mut set = HashSet::new();
    set.insert(1);
    for a in &set {
      // 配列やベクタのようにfor文を回せる
    }
    set.contains(&1);
}

文字列 (String, Vec<char>)

String→Vec<char>の変換

    input! {
        s: String,
    }
    let c: Vec<char> = s.chars().collect();

Vec<char>→Stringの変換

    c.iter().collect::<String>();
    // 逆順にもできる
    c.iter().rev().collect::<String>();

String→数値の変換

// 型の指定が必要
let num = s.parse::<i64>().unwrap();

// 変数部分に指定してもOK
let num: i64 = s.parse::().unwrap();

文字の入れ替え

// あらかじめ use std::mem::swap; しておくこと

    let mut s1: Vec<char> = s[..n].to_vec();
    let mut s2: Vec<char> = s[n..].to_vec();

    // 変数内で文字を入れ替える
    s1.swap(0, 1);

    // 変数間で文字を入れ替える
    swap(&mut s1[0], &mut s2[1]);
}

文字列結合

String + &str の形であればできる。

挿入

Vec<Char>限定で insert というメソッドで好きな位置に文字を入れることができる。

# 先頭に'0'を追加
s.insert(0, '0');

DFS

再帰とwhileによる実装

問題例: https://atcoder.jp/contests/abc204/tasks/abc204_c

再帰

use proconio::input;
 
fn main() {
    input! {
        n: usize,
        m: usize,
        arr: [(usize, usize); m],
    }
    let mut graph = vec![vec![]; n + 1];
    for i in 0..m {
        let (a, b) = arr[i];
        graph[a].push(b);
    }

    let mut ans = 0;
    for i in 1..=n {
        let mut tmp = vec![false; n+1];
        dfs(&graph, &mut tmp, i);
        for b in &tmp {
            if *b {
                ans += 1;
            }
        }
    }
    println!("{}", ans);
}

fn dfs(graph: &Vec<Vec<usize>>, tmp: &mut Vec<bool>, i: usize) {
    if tmp[i] {
        return;
    } else {
        tmp[i] = true;
        for j in &graph[i] {
            dfs(graph, tmp, *j);
        }
    }
}

while

VecDequeを使う。この問題はBFSでも解ける(VecDequeをVecにしてpush(), pop()すれば良い)

use proconio::input;
use std::collections::VecDeque;
 
fn main() {
    input! {
        n: usize,
        m: usize,
        arr: [(usize, usize); m],
    }
    let mut graph = vec![vec![]; n + 1];
    for i in 0..m {
        let (a, b) = arr[i];
        graph[a].push(b);
    }

    let mut ans = 0;
    for i in 1..=n {
        let mut tmp = vec![false; n+1];
        let mut tmp2 = VecDeque::new();
        tmp2.push_back(i);
        while tmp2.len() > 0 {
            let x = tmp2.pop_front().unwrap();
            tmp[x] = true;
            for y in &graph[x] {
                if !tmp[*y] {
                    tmp2.push_back(*y);
                }
            }
        }
        for b in &tmp {
            if *b {
                ans += 1;
            }
        }
    }

    println!("{}", ans);
}

Discussion

ログインするとコメントできます