Zenn
🏃

RustでAtCoderに挑戦してみた -設定・チートシート・ノウハウを添えて-

2022/11/02に公開
Rust
AtCoder
#
競プロ
tech

以下の記事の続編です。
https://zenn.dev/tipstar0125/articles/4589f2d49b065f

競技プログラミングの鉄則を約半分（前から順番ではなく、★の数が小さい問題をピックアップして解いています。）ぐらい解いた段階で、そろそろAtCoderのレーティングに潜ってみるか、と思って、abc274, 275に挑戦してみました。結果としては、どちらも3完でした。コンテスト後にD問題は自力で解くことができたので、慣れてきて解くスピードを上げれば、4完まではいけそうな気がしてきました。
競プロerとしてはまだまだ未熟ですが、これまでに得られた競プロ用設定やチートシート、ノウハウを共有したいと思います。

設定

真の競プロ強者には不要な設定かもしれませんが、私は補助輪として静的解析ツールを、コードを読みやすくするためにフォーマッタを導入しています。

  • Clippy

Clippyは以下のコマンドでインストールします。

$ rustup component add clippy
  • Rustfmt

Rustfmtは以下のコマンドでインストールします。

$ rustup component add rustfmt
  • VSCode設定

プロジェクトのルートディレクトリに.vscodeディレクトリを作成し、その中にsettings.jsonを作成します。
※拡張機能rust-analyzerを事前にインストールしておいてください

設定の内容は以下の通りです。

  1. 保存時に自動フォーマット
  2. ヒント表示をオフ（うっとおしいので。。。）
  3. Clippyで無視したいワーニングを設定（好みに応じて設定、後述のチートシートでも設定可）
settings.json
{
    "editor.formatOnSave": true,
    "editor.defaultFormatter": "rust-lang.rust-analyzer",
    "editor.inlayHints.enabled": "off",
    "rust-analyzer.checkOnSave.command": "clippy",
    "rust-analyzer.checkOnSave.extraArgs": ["--", "-A", "clippy::needless_range_loop"],
}

事前チートシート

毎回使用するコードのチートシートです。スニペットとして登録する、または、コピペして使用します。

  1. 入力変数に大文字を使用してもワーニングが出ないようにする
  2. proconioの事前import
  3. 高速出力設定
  4. マクロ設定
  5. 再帰関数などでスタックオーバーフローにならないようにスタック領域増やして、solver関数を使用
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[macro_export]
macro_rules! max {
        ($x: expr) => ($x);
        ($x: expr, $( $y: expr ),+) => {
            std::cmp::max($x, max!($( $y ),+))
        }
    }
#[macro_export]
macro_rules! min {
        ($x: expr) => ($x);
        ($x: expr, $( $y: expr ),+) => {
            std::cmp::min($x, min!($( $y ),+))
        }
    }
#[macro_export]
macro_rules! abs {
    ($x: expr) => {
        if $x < 0_isize {
            $x * (-1)
        } else {
            $x
        }
    };
}
#[macro_export]
macro_rules! absf {
    ($x: expr) => {
        if $x < 0.0 {
            $x * (-1.0)
        } else {
            $x
        }
    };
}

#[derive(Debug, Clone)]
struct UnionFind {
    parent: Vec<isize>,
    size: usize,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: vec![-1; n + 1],
            size: n,
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] < 0 {
            return x;
        }
        let root = self.find(self.parent[x] as usize);
        self.parent[x] = root as isize;
        root
    }

    fn unite(&mut self, x: usize, y: usize) {
        let root_x = self.find(x);
        let root_y = self.find(y);
        if root_x == root_y {
            return;
        }
        let size_x = -self.parent[root_x];
        let size_y = -self.parent[root_y];
        if size_x >= size_y {
            self.parent[root_x] -= size_y;
            self.parent[root_y] = root_x as isize;
        } else {
            self.parent[root_y] -= size_x;
            self.parent[root_x] = root_y as isize;
        }
        self.size -= 1;
    }

    fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    fn is_root(&mut self, x: usize) -> bool {
        self.find(x) == x
    }

    fn get_union_size(&mut self, x: usize) -> usize {
        let root = self.find(x);
        -self.parent[root] as usize
    }

    fn get_size(&self) -> usize {
        self.size
    }
}

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        // ここに処理を書く
        input! {
        }
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024)
        .spawn(|| Solver::default().solve())
        .unwrap()
        .join()
        .unwrap();
}

入出力

入出力にはproconioというCrateを使用します。

入力

1. 単一入力

N M S

input! {
    N: usize,
    M: isize,
    S: String
}

2. Usize1, Isize1

Usize1やIsize1で1始まりで与えられた整数を、0始まりに変換することができます。
※好みです。私は逆にややこしいと思ったので、あまり使っていません。

N M

use proconio::{fastout, input, marker::{Usize1, Isize1}};
input! {
    N: Usize1
    M: Isize1
}

3. 配列(Vec)

N
A1 A2 A3 ... AN

input! {
    N: usize,
    A: [usize; N]
}

4. タプル配列

N
L1 R1
L2 R2
L3 R3
...
LN RN

input! {
    N: usize,
    LR: [(usize, String); N]
}

// forでは以下のようにパターンマッチによる分割代入ができます
for &(l, r) in &LR {
    todo!();
}

5. 2次元配列

H W
X(1, 1) X(1, 2) ... X(1, W)
...
X(H, 1) X(H, 2) ... X(H, W)

input! {
    H: usize,
    W: usize,
    X: [[usize; W]; H]
}

6. Chars

以下のような文字列が与えられて、この文字列を配列として扱いたい場合はCharsを使用します。型はVec<char>です。matchやifを使用する場合は、シングルクォーテーションを使うことに注意してください。

(())()

input! {
    S: Chars
}

for c in &S {
    match c {
        '(' => /* something */,
        ')' => /* something */,
        _ => unreachable!(),
    }
}

7. 可変

入力した変数の値を変更する処理をする場合は、mutをつけます。

N
A1 A2 A3 ... AN

input! {
    mut N: usize,
    mut A: [usize; N]
}

入力配列はVec型（スタック）なので、VecDeque型（両端キュー）に変換する場合は、後述の変換処理が必要になります。

use std::collections::VecDeque;

let mut A: VecDeque<_> = A.iter().cloned().collect();

8. 複雑な入力

inputマクロは複数回、いつでも使用することができます。例えば、以下のように、配列の長さがランダムで指定されている場合は、inputマクロを分けて、for文の中で、1つずつ入力します。

N
L1 a(1, 1) ... a(1, L1)
LN a(N, 1) ... a(N, LN)

input! {
    N: usize,
}

let mut a = vec![];
for _ in 0..N {
    input! {
        L_i: usize,
        a_i: [usize; L_i]
    }
    a.push(a_i)
}

出力

1. 高速出力

単にprintlnで出力すると遅いので、事前チートシートで示しているようにfastoutを設定することで、高速出力することができます。

2. {}出力

{}を出力したい場合は、2重括弧{{}}にします。

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

3. join

配列を指定の区切りで出力する場合は、joinを使用します。iterを忘れやすいので注意。

let ans = A.iter().join(", ");
println!("{}", ans);

嵌りがちなエラー

  • subtract with overflow

型がusizeのとき、引き算を使用した結果、負の値になるとエラーが発生します。isizeを使用するか、移項して引き算を使用しないように工夫する必要があります。

input! {
    N: usize,
    A: [usize; N]
}

for i in 0..N {
    // 負の値になるような計算をさせない
    if a - b > 0 {} // NG
    if a > b {} // OK
    
    // 負にならないことを確認してからindex指定する
    if A[a-b] > c {}  //NG
    if a > b && A[a-b] > c {}  //OK
    
    // 配列のindexを指定する変数の型がisizeの場合は、asでusizeに変更
    A[d as usize]
}
  • 型推論で、型がi32とかになる場合、オーバーフローにより、WAになるので、型を指定

i32が扱える数の上限を超えてしまう場合、アルゴリズムは正しくでもWAになってしまい、何が原因でWAが出ているのか分からなくなるのを防ぐために、意識して置いた方が良いでしょう。また、なぜWAになったのか原因不明な場合は、変数にホバーして、意図していない型になっていないか確認しましょう。

// これだけだと型推論でi32になる場合がある
let mut ans = 0; // NG(厳密にはこれで問題ない場合もある)
let mut ans: usize = 0; // OK
let mut ans = 0_usize; // OK

個人的によく使うRustな記法

タプル分割代入

input! {
    N: usize,
    LR: [(usize, usize); N]
}

for i in 0..N {
    let l = LR[i].0;
    let r = LR[i].1;
    // 上述でも良いが、以下のように分割代入可能
    let (l, r) = LR[i];
    let (mut l, mut r) = LR[i]; // 値を変更する場合
}

パターンマッチ

以下はタプルのパターンマッチですが、他にも比較を使ったり、色々なパターンマッチができます。

// queryの第一要素でクエリのパターン(1 or 2 or 3)を指定し、その他の要素（引数）で処理
for &q in &query {
    match q {
        (1, x, y) => {
            // something
        }
        (2, _, _) => {
            // something
        }
        (3, x, _) => {
            // something
        }
        (_, _, _) => unreachable!(),
    }
}

ソート

  • 昇順、降順
let mut A = vec![3, 1, 2];
A.sort(); // 昇順
A.reverse();  // 降順
A.sort_by(|a, b| a.cmp(b)); // 昇順
A.sort_by(|a, b| b.cmp(a)); // 降順
  • キーを指定してソート
let mut A = vec![(1, 3), (2, 1), (3, 2)];
A.sort_by(|(_, a), (_, b)| b.cmp(a)); // 第2要素で降順

再帰メモ

再帰メモする場合、他の言語では通常はグローバル変数を使うと思いますが、Rustの場合は、引数として指定するのが現状ではすっきりする書き方かなと思います。工夫すれば書けるかもしれませんが、かえって複雑になりそう。。。クロージャも試してみましたが、微妙。。。

let mut memo = vec![false; N];
dfs(1, &mut memo);

fn dfs(x: usize, memo: &mut Vec<bool>) {
    // something
}

集合の二分探索

RustのHashSetではlower_boundが使用できません。そのため、集合で二分探索をしたい場合、基本的に昇順に並べられた集合のBTreeSetを使用することをオススメします。

let mut set = BTreeSet::new();
let value = set.range(x..).next().unwrap(); // lower_bound相当
let value = set.range(..x).next_back().unwrap();  // xより小さい要素の中で最大の要素

まとめ

最後まで読んで頂きありがとうございます。
まだ半分しか進められていませんが、初めて競プロに挑戦する人にとって、「競技プログラミングの鉄則」は個人的に良い本だな、と思いながら解き進められています。おかげでコンテストでは3完することができました。残りの問題は個人的にはまだまだ難しい問題ばかりなので、ここからは牛歩になりそうすが、着実に解き進めていければなと思っています。

競技プログラミングの鉄則の解答に関しては以下のGithubに載せていますので、参照ください。
https://github.com/TatsuyaYoke/atcoder/tree/master/tessoku-book

AtCoderコンテストの解答に関しては、以下のAtCoder ProblemsからIDをtipstar0125に設定すると、私が既に解いた問題が緑色になるので、AtCoderで検索してみてください。

https://kenkoooo.com/atcoder/#/table/

もしくは、以下のGithubにもコンテスト終了後に解答をアップしています。気が向いたら他の人の解答や公式解答をみて別解を加えたりしています。
https://github.com/TatsuyaYoke/atcoder

GitHubで編集を提案

Discussion