競技プログラミングの鉄則の演習問題を Rust で解き終えた感想

はじめに

• 競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ (Compass Booksシリーズ) | 米田 優峻 |本 | 通販 | Amazon
• E869120/kyopro-tessoku: 拙著『競技プログラミングの鉄則』（2022/9/16 発売）の GitHub ページです。演習問題の解答や、C++ 以外のソースコードなどが掲載されています。ぜひご活用ください。

@e869120 さんの本「競技プログラミングの鉄則」の演習問題 全 151 問を解き終えました。2か月ほどかかりました。本を読んで分かったつもりになっても、演習問題を解こうとすると全然分かっていないことが分かりました。

本を入手した方は、読むだけではなく演習問題で手を動かしてみるのをおすすめします。 演習問題 B, C のとても丁寧な解説 PDF 216 ページが GitHub で公開されています。

本記事はまとまりのない、AtCoder 緑コーダーの感想ポエムです。タイトルに Rust とありますが、Rust に特有の話は少しだけです。

Rust でこれから演習問題を解こうとする方に

@muumu さんの記事がとてもおすすめです。Rust の最新環境構築方法や、採点環境の Rust 1.42 で通るコードにする注意点がまとまっています ¹ 。演習問題だけでなく競技プログラミング本番でも有用です。

取り組み方

2022-11 本の流し読み

1か月ほどかけて読みました。演習問題は解いていません。この時点での感想です。

• とても分かりやすい本
  • 各アルゴリズムの導入部が図示を含めてとても丁寧。入り口でつまりにくい。 ²
  • 導入部の手厚さに対して、応用部分は駆け足気味。これどういう意味だろう？ と考えるところもありました。
• だいたい見たことのある内容っぽい
• 見たことがあるなら、演習問題は方針だけ考えれば十分？ コードを書くと時間がかかりそうですし

2023-01 ABC285-F に挑んで心を入れ替える

• ABC285 F - Substring of Sorted String

AtCoder Beginner Contest 285-F を本番中に 1時間以上試行錯誤してぎりぎり通しました。それは嬉しいのですけれど、こう運が良くても 5問正解だと水色に手が届く気がしません。もっと試行錯誤せずに解けるようにならないと。

その直後に感想戦で Twitter を眺めていると、 @e869120 さんがこの問題は文字列ハッシュの考え方を使うと書かれていました。

• https://twitter.com/e869120/status/1611987605796847623

鉄則本を読んだはずなのに、コンテスト中に全然気づきませんでした。

そしてこの文字列ハッシュの説明に対応した A 問題を解こうとしたら、あれ、解けない。

分かりやすすぎる本って、見ただけで力が付いたと錯覚してしまうのが怖いです。心を入れ替えて問題を解こうとしました。

演習問題と提出方法

• 競技プログラミングの鉄則　演習問題集 - AtCoder

種類	本文中のヒント	解説	解くために必要なこと
A問題	解答まで丁寧にあり	本文	本文理解
B問題 (応用)	使用するアルゴリズムのみ	GitHub	本文理解・アルゴリズムの実装
C問題 (力試し)	なし	GitHub	アルゴリズムの選択と実装

3種類の演習問題が用意されています。AtCoder サイトに提出すると、無料で自動採点してくれます。

このページ内の「自分の得点状況」で、どれだけ解き進めているかを確認できます。全解答のモチベーションになります。

• AtCoder Problems

鉄則本の解答状況は、AtCoder Problems の "Other Contests" からも分かります。過去問を解く際にお世話になっている方も多いと思います。

2023-01 A問題埋め

さて、テキストの図の通り実装しようとして、詰まったものがいくつか。たとえば、

• bit DP, 区間 DP
• grundy 数
• 文字列ハッシュ
• ダブリング
• 最小フロー, 二部マッチング

……はい、全然分かっていないです

テキストと C++ のコードを参考に、Rust で書き進めて提出しました。これで無事「一回は典型アルゴリズムを書いたことがある」となりました。

問題提出ページの気になるところ

演習問題の提出ページは、ふだん参加している AtCoder ABC に比べるとちょっと気になるところもありました。

• テストケースの形式が揃っていなくて、手元でテストしづらいものがある (@muumu さんの記事に対応方法あり)
• 問題ページ内のテストケースが少な目で、これらのテストが通っても本番テストで引っかかることがよくある
  • ABC だと D 問題以降でタイムアウトするかもくらいで、だいたい追加テストも通るウイニングランを期待みたいな感じがあります ³。でも鉄則本では追加テストも不正解が頻発という感じです。

まあでも、だから ABC 過去問を解きましょうというのは敷居が高いです。本編にかっちり対応している演習問題は、効率よく進められます。

2023-01 B問題埋め

A 問題と同じアルゴリズムを使った演習問題です。同じアルゴリズムが適用できると分かっていれば、同じように解けるように見えます。

しかし罠があります。たまに ★6以上の難しい応用問題が混ざっています。最初本を読んでいたときに、なんだかこの B 問題は危ないかもと気になりながらも手を動かしていなかったところが、やっぱり危なかったという。危なさに気づいていないものもありました。解くのは大事です。

セグメント木は苦手です。先に時間をかけて別解で解いて、あとからセグメント木で書き直すということもありました。以前書いたこんな感じで。あれ、ABC285-F の反省をあまり活かせていません。

2023-02 C問題埋め

最後のボスラッシュ、C問題。問題文だけが与えられて、どのアルゴリズムを適用すればよいかというヒントはありません。

• 019 - Pick Two（★6）

競プロ典型 90 問 - 019 が C 問題の中に入っていました。以前は以前手も足も出ませんでしたが、鉄則本を進めていくと解けるようになっていて、少し嬉しかったです。

ただ、どのアルゴリズムが当てはまるかを見切る練習としては、20 問では全然足りない感じです。鉄則本の「この本の内容を身に付ければ緑から水色の実力になる」はきっとそうなのですけれど、全部解き終えても身に付いたと言える気がしません。

「緑から水色で使いたいアルゴリズムの使用例を含む一覧はこのあたり」くらいで、道具を使い分けられるようにするにはほかにもいろいろな問題に触れていきましょう、という感じでしょうか。

最後に

良い本をありがとうございました。演習問題で手を動かすとより理解が深まりました。と言うか、手を動かさずに分かったつもりになっていたことに、なんだか。

• atcoder-solutions/compete/tessoku-book/src/bin at main · hossy3/atcoder-solutions

こんな感じで解きました。ヒューリスティック系はビルドを通したくらいの入り口で止めています。別途取り組むつもりです。

もし本記事をきっかけに鉄則本の演習問題を解く方がいましたら幸いです。頑張って & 楽しんでください。

1. Rust 1.42.0 環境で rust-analyzer を動作させる のように環境構築する方法もあります。私はこの方法で 1.42 を使い続けていました。 Rust 1.47 で実行時エラーが分かりやすくなったことに気づき、最新派に乗り換えました。 ↩

2. いきなりハイペースで飛ばす技術書を読むと、入り口で置いてきぼりになることがあります。 ……ありますよね ↩

3. や、そう思っても意図しない不正解やランタイムエラーが現れて、デバッグしているうちにすぐに 1時間とか溶けていくのですが ↩