競技プログラミングにおススメの本を紹介!!②

こんにちは、くしらっちょです。

今回は『競技プログラミングの鉄則 アルゴリズム力と思考力を高める77の技術』(米田 優峻 著)を紹介します。

この本は前回紹介した本の続編に値する位置づけとなっており、本著はかなり専門的な内容を扱っているので、競技プログラミングを本気で勉強したい方向けの本となっています。

前回の記事は競技プログラミングにおススメの本を紹介!!②をお読みください。

この記事はこんな人におすすめ!

  • プログラミングの参考書に迷っている方
  • 書籍で競技プログラミングの勉強をしたい方
  • Atcoderのレーティングを上げたい方
  • この本は、競技プログラミング界隈の中でもバイブルとよばれるような名著です。

私も競技プログラマーとして本著を購入し勉強しています。

目次

  • この本の特色
  • この本の難易度
  • 本著の内容
  • まとめ

今回の記事で難易度はAtcoderの色(ランク)と比較して評価しています。

今回の記事で使う色のレベル感をAtcoder社長のブログから引用すると、

  • 茶色: 派遣で来たプログラマがAtCoder茶色だったら結構安心する
  • 緑色: エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう
  • 水色: 水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになる
  • 青色: 8割以上のIT企業において、アルゴリズム力はカンストです。

難易度の詳細は以下のブログを参考にしてください。

AtCoder(競技プログラミング)の色・ランクと実力評価、問題例

この本の特色

この本は競技プログラマー向けということで、プログラミングに対する全体的な知識というよりも、競技プログラミングのプログラミングの問題に特化した内容となっています。

しかし、競技プログラミングで必要となるアルゴリズムや考察のテクニックなどのコンテンツは充実しており、これらを理解するだけでも多くの知識が身に付きます。

この本には150問の演習問題があり、Atcoder上のジャッジシステムで正誤判定が出来るので、演習量という観点でも申し分ないと思います。

また、回答例のコードも、C++, Python, Java の3言語があるので、それぞれの言語で回答を確認することが出来ます。

もちろん、広い難易度の幅を1冊でカバーしているのでこれらを解いたからと言ってAtcoderの問題に困らないということはないと思いますが、A・B・C・D問題には対応出来るようになると思います。

私の好みではあるんですが、本著内に入出力例も乗っているので問題を解く手間は減ったかなと思います。

この本の難易度

本書の例題の難易度は灰色~水色、演習問題は灰色~青色という印象でした。

多くの典型アルゴリズムの問題を扱っているので、難易度にはかなりばらつきがあると思います。実際、緑色の難易度の問題では見かけることがないような問題も例題にあります。(例:区間DP、最大流問題など)

本書を一通り理解出来るようになれば、Atcoderの色は緑~水色、 きちんと理解したらそれ以上も達成できるらしいです。

Atcoder茶色以下の問題であれば、典型アルゴリズムを少し工夫する程度の難易度なので、本書の例題を一通り解いたならば、 茶色の難易度の問題では考察をすんなり出来るようになると思います。

Atcoderのコンテストでは問題セットによっては早く問題を解くという力も求められるので、考察を素早くできてコードを書くという能力は非常に大事になってきます。

本書の内容

各章では、競技プログラミングで用いられるアルゴリズムの説明や数学的思考について紹介されています。

同じ名前のアルゴリズムであっても様々な種類があるので、各種類ごとに例題と演習がついています。

また、本書で掲載されている問題は競技プログラミングでも頻出のアルゴリズムが網羅されており、アルゴリズムを体系的に学ぶことが出来ます。

Atcoder上の問題の解説でも学ぶことが出来ますが、全体的なアルゴリズムを俯瞰してみることは難しいのでカテゴリごとに勉強することをおススメします。

各問題は独立ではありますが、「〇〇というアルゴリズムでは××ということを考えるから、△△が成り立つ」といった一通りの理解をするということは重要だと思います。

いろいろな引き出しを作っておくことで、初見の問題であっても自分で答えを導き出すことができると思います。

まとめ

今回の記事では『競技プログラミングの鉄則 アルゴリズム力と思考力を高める77の技術』を紹介しました。

450ページ超で、かなりボリューム感があり、とことん勉強したいといった方におススメします。

余談ですが、本書は前回紹介した本に引き続き、競技プログラミング界隈のバイブルです。鉄則本と呼ばれていたりします。

読んでいただきありがとうございました。