競技プログラミングの鉄則をRustでやってみた
2022年9月16日に「競技プログラミングの鉄則」という競プロの本が発売されました。
私は普段PythonやTypeScriptを用いて、業務改善アプリなどをつくったりしているエンジニアです(最近ではエンジニアといえば、プログラミングができるソフトウェア系のエンジニアのことを指すことが多いですが、私はアナログ回路設計などを専門としたハードウェア系エンジニアです笑)。
業務で使用する解析アプリを作成している中で、計算コストが高い箇所をなんとかしたい、処理に時間がかかる箇所を一瞬で処理したい、といった目的でアルゴリズムやRustを学ぶことにしました。そんな中で上述の本が発売されたので、この本をRustで踏破してみようと考え今回の記事を書いています。
環境構築
一般的な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
- 解答例
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に解答例をアップしていく予定です。
最後まで読んで頂き大変ありがとうございました。
Author And Source
この問題について(競技プログラミングの鉄則をRustでやってみた), 我々は、より多くの情報をここで見つけました https://zenn.dev/tipstar0125/articles/4589f2d49b065f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol