競プロ初心者がRustで『競技プログラミングの鉄則』に取り組むコツ

概要

この記事では、競技プログラミング未経験の私が『競技プログラミングの鉄則』にRustで取り組んで感じたことをまとめるとともに、こうすれば快適に問題に取り組めると分かったことをガイドやTIPSとしてまとめています。
書籍内には例題に相当するA問題、その演習問題に相当するB問題、そして総合演習に相当するC問題があるのですが、今回はA問題77問に取り組んで気づいたことを書いています。（B問題・C問題については取り組みが終わり次第、別途記事更新したいと思ってます。）
※あくまで私の個人的な（拙い）解答例かつネタバレになるので必要な方のみに向けたものとなりますが、参考までにA問題のAC（Accepted）判定されたRustで書いたソースコードもアップしています。

実際にRustで取り組んだ感想

『競技プログラミングの鉄則』はAtCoderに登録することで自分が書いたコードを提出して正解か不正解かが分かるようになっていて、これが素晴らしい特徴だと思いました。
というのも、全ての問題に対して書籍内とGitHub上のサポートページに正解コードが書かれているのですが、C++/Java/Python以外の言語は用意されていないですし、実際に自分でコードを書いてみると完全な写経でも無い限りは正解コードとかなり多くの箇所で違った書き方になるので、自分が書いたコードが正解判定されることがとても心強いです。
業務の感覚でたとえると、既に自動リグレッションテストが整備されていて安心してリファクタリングに集中できるような心地よさです。
そういうわけでこの本に取り組むためだけにAtCoderに登録する価値が十分にありますし、自分もこの本に取り組む際に初めてAtCoderに登録しました。（登録はすぐ完了できます。）
AtCoderのオンラインジャッジシステムは非常に多くの言語をサポートしており、C++/Java/Python以外を使いたい人でも取り組みやすいと思います。

『競技プログラミングの鉄則』に取り組むための前提知識

この本の著者は「本書の進め方」において「高校1～2年程度の数学の知識を有していること」を想定しているとしたうえで、数学の知識に不安のある人は問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本に事前に取り組むことを推奨しています。
私はおこがましくもその本を読まないまま取り組んでいるのですが（近日読んでみたいと思ってます）、もう少し具体的には（私個人の感覚ですが）以下に挙げる高校数学のほんの一部の知識を持っていれば十分に『競技プログラミングの鉄則』に取り組めると思いました。

1. n進法、特に2進法（書籍内にも序盤で説明はあるものの、ほぼ全章に渡って前提知識として頻出）
2. 数列の初歩と和の公式（配列の添字や要素数の計算などに）
3. 漸化式の考え方（一般項を求めることは不要で、漸化式を立てるところまで）
4. 2を底とする指数関数・対数関数（二分探索や二分木で頻出）
5. 剰余（mod）の基本性質（書籍内で説明はあるものの証明は無く当たり前の感覚を得にくい）
6. 場合の数、特に組み合わせ数の定義と考え方
7. 数学的帰納法（アルゴリズムの正当性を示す時に頻出）

他にもユークリッドの互除法や集合の包除原理などいろいろ数学要素は出てくるものの、書籍中の解説で十分理解できると感じたので省略しています。
たとえば上記の項目1と2の理解が足りない場合、セグメント木という完全二分木の一種を一次元配列で扱うときに各要素が配列中の何番目に格納されているか（添字の算出）が分かりづらくなると思います。
というのも書籍中に具体例となる図と正解が書かれているのでそこから添字を算出すること自体は可能なのですが、特に初心者だとなぜその計算式で良いのかが分からず詰まりやすくなると思います。
たとえば高さ$n$の完全二分木の最大要素数は$2^n - 1$ですが、これは等比数列の和の公式から$1 + 2 + ... + 2^{n-1} = 2^n - 1$と導出するか、完全二分木の$n$番目の高さの要素数が$n$桁目のビットに対応することから(1が$n$個並んだビット列) $= 2^n - 1$と考えれば分かる、といった感覚があると書籍中の解説も理解しやすいです。
ただ、いずれも高校数学としては非常に局所的な知識なので、わざわざ高校数学を総復習するなどの遠回りをする必要はなく、本を読んでいて分からないと思った知識だけ補えばいいと思いました。
そういう意味で『競技プログラミングの鉄則』は前提知識の要求が少ない初心者でも取り組みやすい本だと思います。

なお、注意点として書籍では扱っている種々のアルゴリズムの正しさの証明は大胆に省かれているので、アルゴリズムの正当性を丁寧に学びたい場合はたとえばアルゴリズムイントロダクションのような網羅的な本を別途参照する必要があります。

Rustでの標準入力への対処（競プロ初心者にとっての最初の関門）

競技プログラミングに初めて挑戦する時にまずつまずくのが問題データの読み込みだと思います。
特にRustは素のままだと問題読み込みだけで長いコードを書く必要があって大変です。
それを解決するのがproconioというクレートです。
これはAtCoder上でも使用可能なクレートの1つで、後述するcargo-competeで生成されるCargo.tomlでもデフォルトで入り、すぐに使えます。
使い方はマニュアルのサンプルコードから簡単に分かると思いますが、もしA問題を解いていく中でつまずくことがあったら私の書いたA問題の解答コードも参考にしてみてください。
少なくともA問題ではproconioの機能だけで困ることはありませんでした。

Rustで快適に問題を解いて提出する環境の構築

最初はAtCoder上で提供されているページから直接コードをコピーペーストして提出してもいいのですが、慣れないと初歩的なバグを見逃すなどで何度も実行時エラーが出て、しかもそのエラー内容が分からないので困ることが多いです。
そこでおすすめなのがcargo-competeというツールです。
このツールを使うと主に以下の恩恵を受けられます。

• コンテスト名（今回はtessoku-book）を指定するだけで自動的に問題毎の.rsファイルを生成し、すぐに全ての問題に取り組める
• 生成されるCargo.tomlで全ての.rsファイルが実行可能な設定にされるため、VSCodeなどのエディタで問題毎の.rsをすぐに実行・デバッグができるようになる
• Dropboxにアップロードされているテストデータを用いてローカルでジャッジできる（AtCoderのシステム上に提出する前にACになるか確認できる）
• コマンドラインでAtCoderにログイン・解答提出ができるため、エディタとターミナルで解答作成、テスト、提出までの全てを完結できる

初見だとproconioやらcargo-competeやら準備に手間がかかる印象があるかもしれませんが、競プロ初心者の場合A問題77問だけでも数十時間程度かかる長い取り組みになるかと思いますので、どこかのタイミングでこれらを導入しておくと良いと思います。

実際にcargo-competeで問題を解けるようにする

導入はとても簡単です。ただし、以下の作業は事前に各自で行っておく必要があります。

• AtCoderへのユーザー登録
• Rustの開発環境の用意（Rustのインストールやエディタ・ターミナルの用意）

※以下の手順はWindows 10環境で行いましたが、MacやLinuxでもほとんど変わらないかと思います。

インストール

$ cargo install cargo-compete

cargo-competeを使用するディレクトリで初期化処理を実行（今後はそのディレクトリ配下にtessoku-bookを含む各コンテスト用のディレクトリをcargo-competeで生成していくことになります。）

$ cargo compete init atcoder

その際に以下の選択肢の入力が促されますが、意味がわかる人以外は2を選択しておいて問題ありません。

1 No
2 Yes
3 Yes, but I submit base64-encoded programs
1..3: 2

するとcompete.tomlが生成されるのでエディタで開き、以下のように1.42.0が指定されている行をコメントアウトします。

# toolchain = "1.42.0"

この行は本来AtCoderの実行環境で使われている1.42.0のバージョンに合わせることが目的で、以前はAtCoderのためにローカルでもRust 1.42.0を使用するのが常套手段だったようです。
しかし残念ながら現在このバージョンではrust-analyzer（VSCodeなどのエディタでRustコードの様々な入力支援をしてくれる機能）が使えないため、自分はローカルではRustの最新バージョンをインストールして、上記の行をコメントアウトするようにしました。
こうするとローカルでは実行できるのにAtCoder上ではコンパイルエラーになるケースが出てくるのですが、今のところそのパターンは限られているのでrust-analyzerを使用した書き心地を優先しています。
なお、cargo-competeにある「バイナリ提出」という機能を使うと最新バージョンのRustと任意のクレートを使用してAtCoder上で実行できるという裏技もあるのですが、AtCoder側で公式に推奨されている方法では無いので今回は控えました。
さて、少し説明が長くなってしまいましたが、準備ができたのでAtCoderにログインします。（ここで事前に登録したAtCoderのユーザー名とパスワードの入力が必要です。）

$ cargo compete login atcoder

そして解答ファイル一式とテストケースの生成を行います。
AtCoderでは『競技プログラミングの鉄則』用にtessoku-bookというコンテストが用意されているので、それをcompete newの引数に渡します。

$ cargo compete new tessoku-book

これだけで問題に取り組めるようになります。

なお、この時に以下のようなwarningが出ると思いますが、気にする必要はありません。

warning: A50: Could not extract the sample cases

これは第7章のヒューリスティックの問題A50のサンプルテストケースの読み込みに失敗したという内容なのですが、そもそも問題ページにサンプルケースが提供されていないのです。（後述するDropbox上のテストケースをダウンロードして使用することはできます。）

さて、a01.rsに早速解答コードを書き終えたとしましょう。
作成したコードが正しく動作するか確かめるためにテストを実行します。

$ cargo compete test a01

そして最後に解答をAtCoderのオンラインジャッジシステムに提出します。（自動でテストが走って全てACだった時に限りAtCoder上に提出されます。）

$ cargo compete submit a01

cargo-competeでテストを実行しないで提出したいとき

何らかの理由でテストが通らなくても提出したい場合は、以下のように--no-testを付与して強制提出もできます。

$ cargo compete submit a01 --no-test

たとえばA61では頂点の順番がソート済みでないとcargo-competeでのテストが通らないのですが、問題ではソート済みであることを課していないので--no-testを使用して提出してACを得ることも可能です。
また、A46～A50のヒューリスティックは問題の特性上解答が一致することはほぼあり得ないので、これらの問題も基本的に--no-testを指定して提出することになります。

全てのテストケースをローカルで実行できるようにする

AtCoderのテストケースはDropbox上に公開されています。
その中に『競技プログラミングの鉄則』のテストケースもあります。
本来はcargo-competeでDropboxのAPIを用いたテストケース自動ダウンロード機能があるのですが、私が試したところ以下のエラーが発生してできませんでした。

error: unexpected format (path-prefix: "/tessoku-book/", files: ["/tessoku-book/A10/e8", "/tessoku-book/A10/gen", "/tessoku-book/A10/main"], folders: ["/tessoku-book/A10/test"])

これはテストケースが.txtで提供されていない場合に起こるようなので、ここではDropboxから直接データをダウンロードする迂回策を取ります。
「ダウンロード」ボタンを押すと、容量が大きく時間がかかりますがzipファイルとしてダウンロードできます。
これを展開すると全てのテストケースが得られます。
さて、cargo-competeが使用しているテストケースは（cargo-competeが生成した）Cargo.tomlが存在するディレクトリ配下のtestcasesディレクトリにあります。
たとえばA問題全てのテストケースを使用したい場合は、A01～A77ディレクトリを全てtestcases以下にコピーしましょう。
その後に再び以下のテストコマンドを発行すると、A01の場合は106個のテストケースが実行され、確かにローカルでジャッジが行われていることが分かります。

$ cargo compete test a01

ローカルで実行するメリットは、例えば実行時エラーが発生した場合にRustが丁寧にエラーの原因箇所を示してくれることです。
初心者であれば以下のエラーによく遭遇すると思います。

thread 'main' panicked at 'attempt to subtract with overflow', src/bin/a01.rs:9:20

thread 'main' panicked at 'index out of bounds: the len is 1 but the index is 2', src/bin/b01.rs:10:31

1番目のエラーはusizeの変数で負数が生じる引き算をしてしまったとき、2番目のエラーは配列の容量を超えた添字にアクセスした場合に生じる実行時エラーで、親切にも該当する行番号と列番号まで示してくれています。
また、特定のテストケースだけWA（Wrong Answer）になったときなどデバッグしたい際には--testcasesオプションを付与して実行すると指定したテストケースだけ実行されるので便利です。

$ cargo compete test a01 --testcases sample_01

ローカルでジャッジできない一部のテストケースたち

私が試していたところ、A問題のうちA07～A09、A27、A51～A55、A71～A76はそのままだとローカルでテストケースを実行できませんでした。
これはテストケースが.txt形式で提供されていないことによります。
しかしそのうちの多くがローカルの（cargo-competeが生成した）testcasesディレクトリ内の.ymlファイルを編集することで対処できます。
たとえばA51はテストファイルの拡張子が.inと.outになっているので、testcases/a51.ymlファイルをテキストエディタで開き、以下のように（*.txtでなく）*.inと*.outを指定するようにします。

extend:
  - type: Text
    path: "./a51"
    in: /in/*.in
    out: /out/*.out

他のA問題についても以下のように対処できます。

• A09はtests.zip内にテストケースが入っているため、解凍してinディレクトリとoutディレクトリをローカルのtestcases/a09ディレクトリ内にコピー
• A27はテストケースファイルに拡張子が無いため、a27.ymlでin/*、out/*を指定
• A51～A55、A71～A76では拡張子が.inと.outになっているため、それぞれの.ymlにin/*.in、out/*.outを指定

ただ、A07、A08はテストケース生成コードのみが公開されていて、しかも生成コード内でincludeされているヘッダーファイルが同梱されていないためローカルにテストケースを用意することは難しそうでした。

※B問題・C問題はまだ取り組んでいないので未確認です。

cargo-competeでのトラブルシューティング

fastout

A56のように解答で大量の出力をする問題ではproconioの機能であるfastoutを使わないとローカルでのテストが実行時間制限オーバーで失敗することがあります。
使い方は簡単で、解答を出力する関数に以下の記述を足すだけです。

use proconio::fastout;
#[fastout]
fn main() {
    // ここにたくさんのprintln!
}

fastoutを使用するとAtCoder上でもA56は361msから53msに実行時間が短縮されました。
なお、cargo-competeでのテスト実行時間制限はtestcases/a56.ymlファイルで調整できるので、必要に応じてそちらを増やすのもありです。
※もしマルチスレッド環境下でfastoutを使う場合は注意点を読んでおく必要があります。

SplitWhitespace

A65でテストを実行すると以下のようなエラーが出てしまいます。

12/12 ("sample01") Wrong Answer (21 ms)
stdin:
15
1 2 1 1 1 6 2 6 9 10 6 12 13 12
expected:
14 2 0 0 0 8 0 0 2 1 0 3 1 0 0 
actual:
14 2 0 0 0 8 0 0 2 1 0 3 1 0 0
note: 
whitespace-separated words matched. try setting `match` to `SplitWhitespace`

これはcargo-competeのAC判定の方式が原因なので、testcases/a65.ymlを編集して以下の設定に変えるとAC判定されるようになります。

match: SplitWhitespace

Rustで問題に取り組む際のTIPS

ここからはRustで『競技プログラミングの鉄則』の解答コードを書く際のTIPSを列挙します。

Rustのバージョン固有の問題

reduceを使えない（Rust 1.51.0以降の機能）

Rust 1.42.0ではreduceを使えないので、適切な初期値を与えてfoldを使う必要があります。

let xorA = A.into_iter().reduce(|a, b| a ^ b).unwrap(); // 1.42.0ではコンパイルエラー
let xorA = A.into_iter().fold(0, |a, b| a ^ b); // 1.42.0でもOK

各数値型のMINとMAXの書き方

i64::MINやusize::MAXはRust 1.43.0以降でないと使えないので、deprecatedであるもののstd::i64::MINやstd::usize::MAXを使う必要があります。

for文での配列にはiter()をつける

Rust 1.53.0以降では配列を直接for文で使えて便利ですが、1.42.0ではiter()をつける必要があります。

for i in [1, 2, 3] { // Rust 1.42.0ではコンパイルエラー
    println!("{}", i);
}
for i in [1, 2, 3].iter() { // Rust 1.42.0でもOK
    println!("{}", i);
}

Rust・競プロ初心者向けのTIPS

ここでは初心者がつまずきやすいと思ったポイントを列挙します。
問題の本質には触れていないものの厳密に言うとネタバレに該当するかもしれないので、気になる方はRustで書いてて詰まってしまった時に見てみてください。

大文字変数に対するwarningの抑制

Rustでは大文字で始まる変数に対してwarningを出すのですが、以下のように#[allow(non_snake_case)]をmain関数に足すことで、main関数内で自由に大文字変数を使用することができます。

#[allow(non_snake_case)]
fn main() {
    // ここでAなどの大文字変数を自由に使える
}

競技プログラミングの問題では多くの変数が大文字で与えられるのですが、解く際には（少なくとも入力値を読み込むタイミングでは）問題の変数名をそのままコード中で使ったほうが分かりやすいと思い、このような設定をしています。

最小要素を取得する優先度付きキューの実装

RustではA53の優先度付きキューとしてBinaryHeapを使うと便利なのですが、残念ながら最大ヒープしか対応しておらず、問題で求められている最小ヒープとして使うにはstd::cmp::Reverseを使うなどの工夫が必要です。

Reverseの使用例

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut heap = BinaryHeap::new();
heap.push(Reverse(a));
if let Some(Reverse(a)) = heap.peek() {
    println!("{}", a);
}

文字単位で処理するときはStringでなくVec<char>を使う

問題データで文字列を受け取る時にString sのi文字目を取得するのにs.chars().nth(i)とするのは（文字列長Nに対してO(N)かかるため）低速で、場合によっては実行時間制限に引っかかってしまいます。
問題データとして受け取る文字列に文字単位でアクセスしたい場合はVec<char>を使うのがよく、proconioではそれ用にproconio::marker::Charsという型が用意されています。

Charsの使用例

use proconio::input;
use proconio::marker::Chars;
#[allow(non_snake_case)]
fn main() {
    input! {
        S: Chars,
        T: Chars
    }
    for i in 0..S.len() {
        for j in 0..T.len() {
            if S[i] == T[j] {
                // 以降省略

usizeを使用するときの注意点

基本的に正の整数を扱う変数はusizeにしておくと、配列の添字としてもそのまま使用できるので便利です。
しかしusize変数同士の減算で結果が-1のように負の数になるとオーバーフローで実行時エラーになってしまいます。
そのような場合は負の数にならないようにするか、isizeとしたうえで、配列の添字に使用するときだけas usizeを書き足す必要があります。
このas usize指定は競技プログラミングでRustを使用するときには面倒に感じますが、Rustの特徴である安全性を活かすためにもうまく付き合っていく必要があります。

Rustでよく使うイテレーター処理や変換操作

Rustで競技プログラミングに取り組むときはイテレータでVecを操作することが多いと思います。
その際に用途から逆引きしたりアイデアを得たりするのに、以下のページが助けになりました。
Rustでよく使うイテレーター処理や変換操作

最後に

私は今までに一部のアルゴリズムは断片的に業務や個人開発で触れてきましたが、競技プログラミングの世界はほとんど知らなかったので、あくまで入門とはいえ『競技プログラミングの鉄則』でその独特の世界を垣間見えたのが面白かったです。
自分は競技としてのプログラミングに強い興味を持っているわけではないのですが、特に個人開発をする際にはもっといいアルゴリズムがあるのに気づかないまま機能追加を諦めたり下手な実装をしてしまう可能性があるのは怖いと思っていて、その目的でも競技プログラミングの勉強を通してアルゴリズムによる問題解決能力を高めていきたいと思いました。
同じようにふと思い立って『競技プログラミングの鉄則』に取り組むことを通してRustで競技プログラミングの世界に触れてみたいという人に、この記事が少しでも参考になれば幸いです。