🏃

競技プログラミングの鉄則をRustでやってみた

2022/09/22に公開

Rust

AtCoder

競プロ

tech

2022年9月16日に「競技プログラミングの鉄則」という競プロの本が発売されました。
私は普段PythonやTypeScriptを用いて、業務改善アプリなどをつくったりしているエンジニアです（最近ではエンジニアといえば、プログラミングができるソフトウェア系のエンジニアのことを指すことが多いですが、私はアナログ回路設計などを専門としたハードウェア系エンジニアです笑）。
業務で使用する解析アプリを作成している中で、計算コストが高い箇所をなんとかしたい、処理に時間がかかる箇所を一瞬で処理したい、といった目的でアルゴリズムやRustを学ぶことにしました。そんな中で上述の本が発売されたので、この本をRustで踏破してみようと考え今回の記事を書いています。

altテキスト

環境構築

一般的なRustの環境構築方法については、省略し、本記事では、快適に競プロ(特にAtCoder)を学んだり、参加できるようにする環境を構築することについて記載します。

本記事ではcargo-competeといライブラリを使用します。
これはAtCoderにCLIで参加できる非常に便利なライブラリなのですが、この本は以下のURLにある通り、自動採点システムをAtCoder内に用意してくれているので、このライブラリをそのまま使用できます。
前準備としてAtCoderへの新規登録をしていおいてください。後述しますが、CLI上でAtCoderにログインします。

インストール

以下の通り、cargo-competeをインストールして、プロジェクトディレクトリを作成し、初期化します。初期化の段階でcrateを使うか聞かれるので、2 Yesを選択し、事前に用意したAtCoderのユーザでログインしてください。
crateに関しては、proconioという便利な競プロ用の入出力ライブラリを使用するのがオススメです。

$ cargo install cargo-compete
$ mkdir atcoder
$ cd atcoder
$ cargo compete init atcoder
Do you use crates on AtCoder?
1 No
2 Yes
3 Yes, but I submit base64-encoded programs
1..3: 2
$ cargo compete login atcoder

AtCoderで使用できるRustのバージョンは1.42.0なので、このバージョンがインストールされていなければ、以下のコマンドでインストールしておいてください。

$ rustup install 1.42.0

コンテスト参加

上述URLのcontestsの次にくるエンドポイントがこの本のコンテスト名です。
このコンテスト名をnewの後に指定することで、自動採点システムを快適に使用できます。
通常はabc196などの実際のコンテスト名を指定して競プロに参加することになります。

$ cargo compete new tessoku-book
$ cd tessoku-book
$ code .

問題を解いてみよう！

では、例としてA01 - The First Problemを解いてみましょう。
先ほど作成したコンテストのプロジェクトのファイル構成は以下の通りなっていると思います。
src/binのa01.rsが、今回解答を記述するファイルになります。
testcasesには解答を自動採点システムにかける前に、ローカルな環環でテストするための情報が保存されています。

.
|-- Cargo.lock
|-- Cargo.toml
|-- src
|   `-- bin
|       |-- a01.rs
`-- testcases
    |-- a01
    |   |-- in
    |   `-- out
    |-- a01.yml

解答例

a01.rs

use ::proconio::input;
fn main() {
    input! {
        n: u32
    }
    println!("{:?}", n * n);
}

テスト

以下のコマンドで、テストを実行できます。
入力は自動で行われるので、問題からコピペする必要はありません。
複数のテストが実行され、全てAcceptedになったら自動採点に移行しましょう！

$ cargo compete test a01

今回の問題はかなり簡単なので、特にデバッグすることなくテストをできますが、Rust初学者や問題が難しい場合はコードの途中結果を出力しながらデバッグしたいと思います。その場合は、以下のコマンドを使用します。
この場合は、入力は自動で行われないので、問題ページから入力をコピーして、貼り付けましょう！

$ cargo run --bin tessoku-book-a01

自動採点

いよいよ自動採点です！
以下のコマンドを実行しましょう。
ACと出力されたら問題に正解しているということを意味します。
※実際にAtCoderのページに進み提出結果を見てみると、先ほど記述した解答がアップロードされていることが分かります

$ cargo compete submit a01

まとめ

私自身まだほとんど解き進められていませんが、少しずつ進めていき、いずれAtCoderにも参加したいと思っています。
以下のGithubに解答例をアップしていく予定です（可能な限り、公式解答に近いアルゴリズムを掲載します）。
最後まで読んで頂き大変ありがとうございました。

GitHubで編集を提案

環境構築

問題を解いてみよう！

まとめ

Discussion