競プロ備忘録

競プロerの備忘録

競プロ用Rust環境構築

記事で載せてる実装例とかほぼ全部Rustのコードなことからわかるように、私はRust使いです。(私の記事読んだことある人なんでほぼいないでしょうが)

たまに、Rustで競プロやりたいけど環境構築の方法がよくわからん、みたいな人もいるので、お手軽環境構築していきましょう。

リッチな環境じゃないですが、私はこの環境で出ててあんまり不便感じてないので、まあ大丈夫なはずです。

WSLをインストールする

のっけからこれかよって感じですが、WSLを入れていきましょう。
別にWindowsでも当然Rustは使えるんですが、私はWindowsでのプログラミングのことをよく知らないので、WSL入れていきます。

当たり前ですが、生のLinux使ってるならこの手順は不要です。

手順は簡単で、管理者としてPowershellを立ち上げてwsl.exe --installすればよいです。

必要に応じて以下を参照しましょう。ここに書いてある通り、よっぽど古い環境使ってるとかでなければwsl.exe --installで入るはずです。
WSL のインストール | Microsoft Learn

インストールされるのはUbuntuなので、Ubuntuが嫌いな人は別のディストロ入れればいいと思います。
wsl.exe --list --onlineすればわかりますが、Debian, Oracle Linux, Kali Linux, Open SUSE, SLESとか使えます。

build-essentialを入れる

sudo apt install build-essentialとすれば入ります。ほかのディストロにも似たようなのがあると思います。

なんでこんなの入れるの？って話ですが、後で導入するRust Analyzerがerror: linker 'cc' not foundなどというエラーで死ぬことがあるからです。

gcc入れるだけで十分な気もするのですが、なんかトラブっても嫌なのでとりあえず入れときます。

rustupする

LinuxでのRust環境の導入は超簡単で、rustupというツールを実行すれば勝手に入ります。

Rust をインストール - Rustプログラミング言語

たぶんcurl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | shとかいうコマンドが書いてあると思うので、これをそのまま黒窓にコピペして実行します。
今はこれが書いてありますが、将来もそうかはわからないので、ちゃんと公式ページからコマンドを拾ってきてください。

curlがないよって怒られたら、sudo apt updateして、sudo apt install curlでインストールしてから実行しましょう。

実行すると1回だけ入力を求められると思いますが、これはそのままEnterを叩けばdefaultでインストールを進められます。

インストール後、シェルを再起動するか、あるいは出力の末尾に出てくるsource "$HOME/.cargo/env"をそのままコピペして実行すれば、パスが通ります。

これで、cargo, rustc, rustfmt, rustupあたりのツールが入っているはずなので、確認してみましょう。command -vかwhichで、それぞれのツールのインストール場所のパスが見えればOKです。
私は今dockerでテキトーに立てたコンテナで試しているので、/root配下に置かれています。わざわざsudoでrustupしたりしてなければ、ホームディレクトリ配下にインストールされることになるでしょう。

$ command -v cargo
/root/.cargo/bin/cargo
$ command -v rustc
/root/.cargo/bin/rustc
$ command -v rustup
/root/.cargo/bin/rustup
$ command -v rustfmt
/root/.cargo/bin/rustfmt

手間でなければ一応バージョンも見ておきます。

$ cargo --version
cargo 1.75.0 (1d8b05cdd 2023-11-20)
$ rustc --version
rustc 1.75.0 (82e1608df 2023-12-21)
$ rustup --version
rustup 1.26.0 (5af9b9484 2023-04-05)
info: This is the version for the rustup toolchain manager, not the rustc compiler.
info: The currently active `rustc` version is `rustc 1.75.0 (82e1608df 2023-12-21)`
$ rustfmt --version
rustfmt 1.7.0-stable (82e1608 2023-12-21)

補完の設定をする

オプションです。おそらく現時点ではcargoを入力した後、タブ補完とか試しても何も反応しないでしょう。
これでは不便なので、シェルの補完をやっていきます。

もしbash-completionがインストールされていない場合は、sudo apt install bash-completionなどでインストールしておきましょう。
たしかWSLでは必要なかったと思いますが、念のためです。

rustup completionsコマンドを叩くとめっちゃ長いヘルプが出てきますが、その中にシェルごとの補完の設定の仕方が書いてあります。
WSLを何もカスタムしていなければbashを使っているでしょうから、BASH:と書いてあるところを読みながらコマンドを打ち込みましょう。

今時点では、以下のようなコマンドを打ち込めと書いてあります。

$ mkdir -p ~/.local/share/bash-completion/completions
$ rustup completions bash >> ~/.local/share/bash-completion/completions/rustup
$ rustup completions bash cargo >> ~/.local/share/bash-completion/completions/cargo

このあと1回ログアウトせよ、と書いてあるので、シェルを立ち上げ直します。
ちなみにdockerで試しているとき、ログアウトせずに補完を試したらbash: _get_comp_words_by_ref: command not foundなるエラーが出ていました。
これはsource /etc/bash_completionで治ります。 kubectl bash completion doesn't work in ubuntu docker container - Stack Overflow

シェルを立ち上げ直したら、補完を試しましょう。rustupコマンドも同様に補完が効くようになっているはずなので、手間でなければ試してください。

$ cargo <TAB>
~出力例は省略。上手くいっていればadd, check, clean, buildなど多数のコマンドが並んでいるはず~

エディタを入れる

なんでもいいです。VimでもEmacsでも好きなものを使うと良いでしょう。
私はVisual Studio Codeしか知らないので、その前提で話を進めます。

Visual Studio Code - Code Editing. Redefined

Visual Studio Codeをインストールすると、WSLからcodeコマンドが使えるようになるはずです。
Windowsから起動するのではなくWSLのシェルからcode <target directory>で起動することで、勝手にVisual Studio CodeがWSLに接続するようになります。

拡張機能を入れる

もちろん好きなものを自己責任で入れればよいですが、とりあえずRust Analyzerというやつは入れましょう。
一応リンクは貼りましたが、Visual Studio Codeの左端にある、右上の欠けた田のマークからインストールするのが楽です。

rust-analyzer - Visual Studio Marketplace

私は毎回環境立てるときは以下のRust Extension Packを入れてますが、特にどっかが公式で出してるわけではないので、入れる場合は自己責任で入れてください。
Rust Analyzerもここに入ってます。

Rust Extension Pack - Visual Studio Marketplace

コンテスト用のクレートを作る

Rustではクレートという単位でプロジェクトを分けます。依存モジュールもクレート単位で解決されます。
大きくバイナリクレートとライブラリクレートがありますが、混在できます。また、1つのクレートに複数のバイナリを持たせることもできます。

競プロやるにあたっては、例えば1つだけバイナリクレートを作って毎回上書きして書き捨てるとか、問題1つにつき1クレートとか(さすがにいないかな…)、色々やり方はあると思います。
私は1クレートで1コンテストにしているので、その方法でやります。

まずcargo newで新規クレートを作りましょう。例えば、

$ cargo new abc300

で、abc300というディレクトリが作られます。あるいは、mkdir abc300; cd abc300; cargo initでも同じことになります。
作成されたabc300は、以下のような構造になっているはずです。(もしかしたら.gitignoreがあるかもしれませんが、些細な差です)

$ tree abc300/
abc300/
|-- Cargo.toml
`-- src
    `-- main.rs

1 directory, 2 files

コンテスト用クレートが出来たら、これをcode abc300で開いてみましょう。

開いたウィンドウで、ターミナル > 新しいターミナル　としてターミナルを開いておきます。
そして、

$ mkdir src/bin -p
$ cd src/bin
$ touch {a..g}.rs
$ code *

として、コンテストで使うソースファイルを作ります。

src/main.rsはどうしたんだって話ですが、私は使いません。なので、別に消してもいいですし、残しておいても無害なのでそのままでも良いです。

外部クレートを入れる

RustでもAtCoderであれば外部ライブラリがたくさん使えるので、以下を参照しながら好きなものを入れていきましょう。
（スプレッドシートが真と書いてあるので、スプレッドシートを見たほうが良いかもしれない…）

https://img.atcoder.jp/file/language-update/language-list.html

外部ライブラリのダウンロードにはcargo addコマンドを使うと良いです。
例えばRust競プロer御用達のproconioをインストールするには、カレントディレクトリがabc300配下であるのを確認して

$ cargo add proconio@=0.4.5 --features "derive"

とすることで依存クレートに加えることができます。
--featuresは外部クレートのオプションの機能を指定するのに使います。proconioには出力高速化のためにfastoutというマクロが用意されていますが、これは--features "derive"を指定したときのみ使えます。

デフォルトではcrates.ioと呼ばれるレジストリからクレートはダウンロードされますが、ローカルフォルダやGithubのリポジトリからダウンロードすることも可能です。
詳しくはドキュメントを読んでみてください。
cargo add - The Cargo Book

ちなみに、cargo addの操作は、さっきクレートのディレクトリ構造を見たときにチラッと出てきたCargo.tomlの[dependencies]という項目にエントリを加えるのと同じです。 なので、手書きでCargo.tomlを書き換えることでも外部クレートの追加は可能です。

コードの実行

あとはコードを書いて実行するだけです。

例えば、src/bin/a.rsを実行するときには、以下のようにすれば実行できます。

$ cargo run --bin a

また、cargoにはreleaseビルドとdebugビルドがあります。デフォルトではdebugビルドで、--releaseを指定することでreleaseビルドになります。

$ cargo run --bin a --release

だいたいdebugビルドでも困りませんが、AtCoderの環境はreleaseビルドであるということだけ覚えておいたほうが良いでしょう。

また、cargo newで作成されるsrc/main.rsを実行する場合には、クレート名を--binの引数にする必要があります。

$ cargo run --bin abc300

src/bin配下のバイナリがない場合には、--binがなくてもsrc/main.rsが実行されます。

$ cargo run

ここまででコンテストに出るには十分な環境が整いました！あとの章はオマケです。読まなくても支障はないです。

自作のライブラリを使う

C++とかだとライブラリを展開してバンドルするツールを使ってるのをよく見ます。Rustにもそういうツールはあります。

いくつか種類はあるのですが、私はcargo-equipというツールを使っています。

GitHub - qryxip/cargo-equip: A Cargo subcommand to bundle your code into one `.rs` file for competitive programming

crates.ioに公開されているので、cargo install cargo-equipで入手することができます。

使い方は簡単で、cargo equip --bin a > run.rsとして対象のバイナリが依存するライブラリを上手いことバンドルしたコードを標準出力に吐き出させ、リダイレクトで別のファイルに流せば、提出できる形になります。

ただ、何もオプションを付けないと森羅万象がバンドルされて大変なことになります。私が使うときは以下のオプションを付けて、AtCoderで使えるクレートを除外したり、cargo checkをパスしたり、minifyするオプションを付けてコード量を減らしたりといったことをしてもらっています。

cargo equip --exclude-atcoder-crates --remove docs --remove comments --exclude-atcoder-202301-crates --minify libs --no-rustfmt --no-check

長すぎるわ！って話ですが、cargo-equipは仕様上いっぺんビルドが走るので、ちょっとでも処理を減らさないとバンドルに許容できない時間がかかります。(Rustのビルドは遅いことで有名)

なので、.bashrcにequipというエイリアスで、上記のオプションを全部ひっくるめて登録しています。

$ alias equip
alias equip='cargo equip --exclude-atcoder-crates --remove docs --remove comments --exclude-atcoder-202301-crates --minify libs --no-rustfmt --no-check'

これでequip --bin a > run.rsのように、楽にオプションもりもりコマンドを実行できます。

コンテスト用クレートをworkspaceにまとめる

（追記）しばらくこれを使っていて、いろいろ不便なことが出てきたので、使うのをやめました。(たとえば、cargo checkやビルドの時間が長くなる、rust-analyzerがworkspace配下の他所のクレートのエラーを大量に拾って固まる、マラソンのテスターが上手く動かない、などなど…)
バイナリをどこかのディレクトリにまとめて容量を減らしたいだけであれば、後述の.cargo/config.tomlを使う方法が良いです。

一応、元の文章は残しておきます。

cargoにはworkspaceという機能があって、いくつかのクレートを1つの仮想的なクレート（？）の配下にまとめておくことができます。

workspace配下のクレートはバイナリを1か所に吐き出させることができるので、これでバイナリの容量を削減できます。
別にそんなことしなくて良くない？って思ってしまいそうですが、Rustはバイナリがデカいので、300回分のコンテストクレートを別々に作ってそれぞれビルドとかすると、数十GBとか下手すると100GB近い容量を消費することもザラです。（えぇ…）

workspaceを作るには、コンテスト用クレートをまとめるディレクトリを作り、そこでcargo initします。生成されたCargo.tomlを以下のような内容に書き換えれば完成です。

[workspace]
members = [
    "abc100", "abc101", ....(その他多数のクレート)
]
exclude = []
resolver = "2"

[workspace.dependencies]
ac-library-rs = "=0.1.1"
segtree = { git = "https://github.com/tayu0110/tayu-procon.git", package = "segtree" }
....(その他多数の依存クレート)

excludeとかresolverは明に指定しなくても動きます（確かresolverは指定しないとwarningが出た気がするが覚えていない…）。

workspace配下のクレートでは、今までのように依存クレートを宣言する以外に、以下のような宣言の仕方ができるようになります。

[dependencies]
ac-library-rs.workspace = true
segtree.workspace = true
.....

従来通りに指定した場合は依存クレートのバイナリがそのクレートのtarget/配下に配置され、workspaceのdependenciesを引き継ぐように指定した場合はworkspace内でバイナリが共有されます。このおかげで、各クレート配下に存在するバイナリの量を最低限にできます。

aとかbとか雑な名前つけてたけど、そんなバイナリをごったまぜにして一か所に吐かせて大丈夫なんか？っていう点ですが、cargoは賢いので、これを適切に処理してくれます。ただ、cargo-equipはこれを処理してくれないので、私は若干改造して使っています。

バイナリをまとめて容量を減らす

cargoの動作を制御するconfig.tomlをいうのを作ることで、バイナリを吐く宛先のディレクトリを変えることができます。
Configuration - The Cargo Book

コンテスト用クレート配下に.cargo/config.tomlを作成し、build.target-dirを書き込めばよいです。
私はコンテスト用クレートをまとめたatcoderというディレクトリの直下にtargetディレクトリを作り、そこにバイナリをまとめて吐かせたいので、

[build]
target-dir = "../target"

という設定ファイルを書き込んでいます。(Cargo.tomlからの相対パスなので、../targetとなります)

コンテスト用クレート作成スクリプト

ここまでで思ってる人多いと思いますが、めんどいですね。というわけでShellscriptで一発でコンテストごとのクレートを作れるようにしていきましょう。

私は以下のようなShellscriptを使っています。

#!/bin/bash -l

if [ -z "$1" ]; then
    echo "Usage: ./make_contest.sh [CONTEST_NAME]"
    exit
fi

DIR="$1"

if ls "$DIR" >/dev/null 2>&1; then
    echo "$DIR already exists."
    exit
fi

cargo new "$DIR"
cd "$DIR" || exit

mkdir .vscode -p
cat <<EOF >.vscode/settings.json
{
    "rust-analyzer.check.command": "check"
}
EOF

mkdir .cargo -p
cat <<EOF >.cargo/config.toml
[build]
target-dir = "../target"
EOF

cargo add ac-library-rs@=0.1.1
cargo add num@=0.4.1
cargo add rand@=0.8.5
cargo add regex@=1.9.1
cargo add permutohedron@=0.2.4
cargo add superslice@=1.0.0
cargo add itertools@=0.11.0
cargo add proconio@=0.4.5 --features derive

cargo add bitset --git https://github.com/tayu0110/tayu-procon.git
cargo add complex --git https://github.com/tayu0110/tayu-procon.git
cargo add convolution --git https://github.com/tayu0110/tayu-procon.git
cargo add ds --git https://github.com/tayu0110/tayu-procon.git --features "full"
cargo add fenwick-tree --git https://github.com/tayu0110/tayu-procon.git
cargo add flow --git https://github.com/tayu0110/tayu-procon.git
cargo add geometry --git https://github.com/tayu0110/tayu-procon.git
cargo add graph --git https://github.com/tayu0110/tayu-procon.git
cargo add math --git https://github.com/tayu0110/tayu-procon.git
cargo add matrix --git https://github.com/tayu0110/tayu-procon.git
cargo add mincost-flow --git https://github.com/tayu0110/tayu-procon.git
cargo add montgomery-modint --git https://github.com/tayu0110/tayu-procon.git
cargo add polynomial --git https://github.com/tayu0110/tayu-procon.git
cargo add rational --git https://github.com/tayu0110/tayu-procon.git
cargo add segtree --git https://github.com/tayu0110/tayu-procon.git
cargo add static-modint --git https://github.com/tayu0110/tayu-procon.git
cargo add string --git https://github.com/tayu0110/tayu-procon.git
cargo add suffix-array --git https://github.com/tayu0110/tayu-procon.git
cargo add unionfind --git https://github.com/tayu0110/tayu-procon.git
cargo add utility --git https://github.com/tayu0110/tayu-procon.git
cargo add wavelet-matrix --git https://github.com/tayu0110/tayu-procon.git

mkdir -p src/bin
for prefix in {a..g}; do
    SRC=src/bin/$prefix.rs
    {
        printf "use proconio::*;\n\n"
        printf "fn main() {\n"
        printf "    \n"
        printf "}\n"
    } >>"$SRC"
    cargo equip --exclude-atcoder-crates --exclude-atcoder-202301-crates --minify libs --no-rustfmt --no-check --remove docs --remove comments --bin "$prefix" >/dev/null
done

cargo build
cargo build --release

code .

.vscode/settings.jsonに打ち込んでいるのはRust Analyzerがリントを行うコマンドを指定するオプションです。
ライブラリや趣味プロではclippyという強力でアグレッシブなリントツールを使っていますが、コンテスト中だと鬱陶しいので、コンテスト用クレート内ではマイルドなcargo checkを使います。

最後の方ではcargo buildとcargo equipを回しています。1回目のビルドは外部クレートのビルドも走るので、めちゃくちゃ遅いです。
下手するとABCのA問題のコードを書き切るより時間がかかりますので、1回空回ししておくとストレスが減ります。