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

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

今回は競技プログラミングに役立つ『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』(米田 優峻 著)を紹介します。

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

  • プログラミングの参考書に迷っている方
  • 書籍で競技プログラミングの勉強をしたい方
  • Atcoderのレーティングを上げたい方

私も半年ぐらいこの本で勉強をしてきたので、その経験も含めこの本の魅力やおススメポイントを紹介していこうと思います。

私が感じたこの本の難易度感も紹介するので、この本の購入を検討している方にも最後まで読んでいただきたいです!

目次

  • この本の特色
  • この本の難易度
  • 各章のポイント
  • まとめ

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

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

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

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

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

この本の特色

著者のコメントを以下に引用します。

アルゴリズムは、プログラミングを用いて問題を解決していくには欠かせない大切な道具です。

一方、アルゴリズムを理解し、そして応用できるようになるためには、ある程度の数学的知識と数学的考察力も大切です。

本書のレビューにも書かれている件数が多いのですが、数学よりの内容になっています。

高校数学程度のレベルを理解していないと少し難しく感じてしまうかもしれません。

しかしながら、フルカラーの図が沢山使われているので、とても分かりやすいです。

難しい内容であれば注意書きを書いてあったり、導出過程も丁寧に書いているので、省略されすぎていて理解できないなんてことはないと思います。

また、この著者の説明資料はどれもデザインが優れていて、抵抗感なく見ることが出来ます。

本書には約200問の演習問題が掲載されています。そして、各問題にはジャッジシステムがAtcoder上に提供されており、書いたコードの正誤判定が出来ます。

この本の難易度

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

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

私が感じているAtcoderの問題の難易度と求められる能力というのは、

  1. 茶色ライン: 競技プログラミングに慣れていますか?
  2. 緑色ライン: 主要なアルゴリズムを一通り理解していますか?
  3. 水色ライン: 主要なアルゴリズムを応用して問題に使用できますか?

です。

本書の例題は、基本的なアルゴリズムの紹介から説明までをしているので、Atcoderの茶色~緑色の問題に対応していると思います。

また、演習問題は例題をひねったものも多く出題されているので、「なんとなくの理解」ではなくアルゴリズムの特性までしっかり理解していないと解けない問題も多いです。

各章のポイント

各章についておおざっぱに目次を見て、読んだ/解いた感想を書きます。

第1章 アルゴリズムと数学の密接なかかわり

この章では、「アルゴリズムというものはどういったものか」という説明や「本書の読み進め方」されています。

本書のテーマである、アルゴリズムの数学部分はどういった部分に現れてくるのかの説明がされています。

「アルゴリズムという用語が数学っぽい」という認識よりも、「プログラムでこういう処理をするために数学的な解法が必要なんだな」と理解しておくだけでも今後にかなり影響を与えると思います。

アルゴリズムのための数学の基礎知識

序章として、プログラミングに使う演算などのを説明しています。四則演算は私生活でもよく使いますが、剰余、論理演算、関数といった概念はプログラミングで頻出なので覚える必要があります。

また計算量という概念にも触れています。

家庭用コンピューターでは1秒に数億回の計算程度を行えます。

しかし、実際にプログラミングで必要とされる処理はそれ以上になってしまってしまうかもしれません(例:1兆回)。

なので、あらかじめ計算量を見積もったり、アルゴリズムを工夫をして計算量を出来るだけ削減するという工程を踏みます。

競技プログラミングでは、問題を解く過程の考察は「計算量削減パート」「実装パート」に分かれていて、非常に大事な概念となります。

3章 基本的なアルゴリズム / 4章 発展的なアルゴリズム

この章から本格的にアルゴリズムの解説に入ります。

ある問題が与えられたときに、どうしたら題意を満たすプログラムを実装できるか、計算量の削減が出来るかがテーマとなります。

数学的な考え方をするアルゴリズムや、グラフ理論といった考え方を用いたアルゴリズムが登場します。

プログラミングにおいて、主要なアプローチの仕方(アルゴリズム)を覚えることも重要ですが、どういった処理が行われいるかをきちんと理解しておく必要があります。

「このアルゴリズムはこういう特性があるからこの問題は解けて、あの問題は解けない」という特性を理解して置かないと今後の問題に対応できなくなります。

この真の理解というプロセスがとても難しいのでこれに全てを費やすかもしれません…(実際私もすごく苦戦しています。)

5章 問題解決のための数学的考察

いままでの章ではアルゴリズムに重点を置いて説明をしてきましたが、ここでは考察というステップがテーマです。

実際に問題を解くにあたってプログラムを書く前に、どうしたら問題が解けるかなどの見通しを立てる考察パートがあります。

先ほども説明しましたが、「アルゴリズムへの理解」に加え、様々な「考察のパターン」を理解する必要があります。

もちろん全ての問題において適用できるとは限りませんが、こういう風な視点で見れば見通しがよくなるかもしれないといったテクニックです。

問題を解く道筋を見やすくするための方法として覚える必要があると思います。

まとめ

今回の記事では『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』を紹介しました。

余談ですが、本書は競技プログラミング界隈のバイブルといっても過言ではないほどの名著であるため、E8(=著者の活動名)本や数学本などと呼ばれていたりもします。

次回は、E8さんの次回作である『競技プログラミングの鉄則』を紹介しようと思います。

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