「競技プログラミングの鉄則」のレビュー

米田 優峻さん(E869120@ICPC2022 (@e869120) / Twitter)の著書「競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~」をご恵贈いただきました。その感想です。

素晴らしい内容で競技プログラミング初心者への最初の1冊として最もお勧めできる本です。特に、数学も得意というわけではなくプログラミング自体も初めてという方には、ダントツで一番お勧めできる本です。

本書の良い点

1.図が分かりやすい。

最初の48ページが無料公開されているので、百聞は一見にしかずということで見ていただけると良いと思います。i
www.dropbox.com
図自体分かりやすいですし全編カラーで書かれているのも良いです。段階的に説明すべきものについて無理に1枚に納めず多くの小さい図に分けて説明しているのもとても分かりやすいです。先ほどのpdfにある図の1つです。

また、既に理解しているアルゴリズムでも、勘違いしたりケアレスミスしたり書くのに妙に時間かかったりすることは誰にでもあると思います。本書の分かりやすい図は、自分の中での理解をアップデートするのにとても役立ちました。簡単な問題でも「あー、たしかにこういうふうにイメージできれば、すっきり理解できるなぁ」と感じることが多かったです。

2.つまづきにくい。

頭が良いが説明が苦手な人が記事を書くと、説明の段差が大きくなりがち(例: 「自明である」、「定義そのもの」、式の省略等)ですが、この本についてはそういうことはありません。特に、各節最初の例題は「無駄な部分を省き、学んでほしい部分に絞った問題」となっており、その例題まですら図で多く説明しているので、とにかく最初の1歩では絶対につまづかせないという意図を感じます。続く応用問題もほとんどの場合は例題に沿っています(でもコピペではうまくいかないちょうど良い問題)。必要に応じてヒントも書かれています。つまづきにくいです。

3.ヒューリスティックスについて取り上げてある。

できるだけ良い答えを出す系のコンテストAHC(AtCoder Heuristics Contest)についてはネットの記事はあるのですがまとまっているわけではないので、体系的に学びたい初めての人にこの本はとても良いと思います。貪欲法→局所探索法(単純山登り)→焼きなまし法のように、実際のコンテストで徐々にコードを改善していく過程に沿って書かれているので、コード量が増えがちでも分かりやすいと思います。

4.考察テクニックの章

問題のパターンは無数にあり全解法覚えるわけにもいかず自力で考察するほうが本質だと思うのですが、その考察について1章分設ける(6章)*1はとても良いと思いました。考察テクニックはもっとあると思うので、もしこの本の続編がでる場合は、さらにこの部分の分量をふやしてもらえると嬉しいです。

5.コンテンツが充実

まず問題集151問がすべてAtCoder上で利用できます。
atcoder.jp

本に載っていない分についてはgithubが用意されており、C++, Java, Pythonの3言語での解答コードも読むことができます。親切です。
github.com

解説pdfについても、本書程ではないにせよ図を駆使して分かりやすく書かれており、全216ページ(!)もあります。付録コンテンツは誰でも無料で利用できるのですが、正直ここだけでも商品になる気がします…。

本書の賛否両論ありそうな点

コードの書き方

分かりやすさのために一般プログラミングの作法については目をつむる、他の本で勉強してね、という方針は構わないと思いますが、以下の2つは気になりました。

  • 変数の定義がmainの関数内で行われている場合と関数外で行われている場合があり、その理由が特に書かれていない。
    • スタックオーバーフローを避けるために全部外に書きグローバル変数とするというのであればある意味分かりますが、そうでない例もあります。
  • STLに関して、説明無しで登場しているところがある(3.5章 vector)
    • ここまで引っ張るより早めにどこかでSTLについて説明したほうが、生配列よりもvectorのほうが良い部分で素直にvectorを使えたので良かったかもしれません。

親切すぎる

裏を返すと、この本に慣れると

  • コンテストにでる、あまり素直でない問題
  • 一足飛びの解説

などの耐性があまり付かず今後つまづくかもしれません。ただ、終章で次の教材として勧めている「競プロ典型90問」については「解説は原則1ページで簡潔にまとめられているため、分かりづらい部分もあるかもしれません。しかし、解説の行間を読むのも練習です。」と述べられており、この鉄則本については割り切って超親切にしているのかなと思いました。

同じジャンルでまとまっていて、必ずしも難度順にはなっていない。

同じジャンルのものをまとめる方式になっており、他の本では最初の方に来る「深さ優先探索」「幅優先探索」はグラフなので本書では最後のほうの9.2章・9.3章に主に取り上げています。ただ、この本は十分にわかりやすく、勉強の際には飛ばして必要な章から読むことも可能なので、必要なら飛ばし読みして良いと思います。

難度と勉強時間の目安

YouTubeで生放送しながら、本書を全部読み演習問題集の全151問を解いたのですが、33時間46分43秒かかりました。そのときの生放送は全てYouTubeのプレイリストにまとめてあります。
www.youtube.com
喋りながら問題を解くとだいぶ遅くなるのも踏まえると、おそらくAtCoder水色レベルの人なら20~25時間で全部読んで全問解けるのではないでしょうか?勉強する際の時間の目安として参考にしていただければと思います。

また著書の最終章にも書かれているのですが、米田優峻さんが本書の次にお勧めしている「競プロ典型90問」について現在解いていっています。こちらも良問が多くこれらも全て解説スライドがあり、とても親切です。
atcoder.jp

おわりに

そういうわけで自信を持ってお勧めできる本なので、みなさん購入しましょう!また、個人的な話ですが、この本がきっかけで毎朝7:00からの競プロ学習習慣がついた気がするので、このまま続けていきたいと思っています。

*1:10章の最初にも考察テクニックが書かれてあります