Webエンジニアのライフハック日記

ゲームをしたりe-Sportsの試合を観に行くのが大好きなエンジニアのブログ。仕事の話から、日常をちょっと便利にする話、節約の話などをメインに書いていきます。たまに実際に買った商品レビューなども。

プログラミングコンテストとかアルゴリズムとかを学びたい人向けの本3選

アップデート

  • 2019年4月1日: 結構読まれているようなので内容を書き直しました

はじめに

僕の古いブログの記事を引用していた以下の記事を見たら、こんなことが書いてあった。

任意の整数を扱う問題が出たら基本的にDP使うんか?

syuntoku14.hatenablog.com

「任意の整数を扱う問題」と「DP(動的計画法: Dymanic Programming)」は関係がないので、「任意の整数を扱う問題が出たら基本的にDPを使う」は誤りである。しかし、動的計画法をどのような問題に対して使えばいいかは難しいし、そもそも動的計画法が何なのか、どのように実装したら良いのかわからないプログラマも多いだろう。

この方はアルゴリズムの勉強ではなく、Pythonの練習をしているようだが、「アルゴリズムの勉強したいが何をしたらいいのかわからない」人は多いだろう。そこでおすすめなのがプログラミングコンテストだ。プログラミングコンテストアルゴリズム力やプログラミングの速さを競うコンテストだ。今回は僕が読んだことあるアルゴリズムプログラミングコンテストに関する本を3冊紹介する。

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテスト」あるいは「競技プログラミング」と聞いて一番有名な本がこれだろう。表紙が蟻の柄なので「蟻本」と呼ばれていたりする。特徴は以下の通りである。

この本は、本気でプログラミングコンテストで勝ちたい人が読む本 であり、 難易度は高め である。アルゴリズムにあまり触れたことがない人は、後述の「最強最速アルゴリズマー養成講座」または「最強最速アルゴリズマー養成講座」おすすめする。下記2冊を呼んだ上でもっと高度なアルゴリズムを勉強したい場合はこちらの本を読むとよいだろう。

最強最速アルゴリズマー養成講座

高橋直大さんという、AtCoder社の社長によって書かれた本である。表紙がヒョウ柄チーター柄?)なので「チーター本」などと呼ばれている。特徴は以下の通りである。

  • 練習問題にtopcoderの問題を採用している
  • サンプルコードが C#, C++, Java と豊富
  • 難易度も易しい

難易度はめちゃめた簡単で、今回紹介する3冊の中では最も簡単だろう。簡単なので物足りなさを感じる人も多いだろうが、そう感じたら上記の「蟻本」を呼んだら良い。そういった点で、アルゴリズム初心者にはよい本なのだが、練習問題にtopcoderを採用しているのが難点である。

アルゴリズムの勉強をするのであれば、プログラミングコンテストのサイトを使って勉強するのが最適である。自分の書いたコードが正しいかどうか採点できるからである。プログラミングコンテストサイトで有名なところでは、topcoder *1, AtCoder *2, AOJ (Aizu Online Judge)*3 などがあるのだが、AtCoderやAOJと比べてtopcoderはサイトが分かりづらい。その点、後述の「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」はAOJを利用していてわかりやすいので、基本的にはこちらの本をおすすめしたい。*4

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

これら3冊の本の中では一番新しい本で、AOJ(Aizu Online Judge: http://judge.u-aizu.ac.jp/onlinejudge/)にも関わっている会津大学の渡辺先生が執筆した本である。秋葉さん(プログラミングコンテストチャレンジブックの著者)も参加している。特徴は以下の通りである。

  • Aizu Online Judge の問題と対応しているため実践しやすい
  • サンプルコードはCまたはC++
  • 難易度もそこまで高くない。

AOJを使う前提の本なので、本を読んでAOJで実践・答え合わせができるし、AOJの使い方が乗っているのも初心者にはありがたい。新しい本なので、図も多く内容も分かりやすい。難易度も平易なところからスタートするので、本気の人向けの本ではないが、アルゴリズムを学びたい人にはぴったりだろう。

注意点としては、サンプルコードがCまたはC++しかない点である。サンプルコードの豊富さでは「チーター本」には負ける。ただ、Javaで書いてもRubyで書いてもPythonで書いてもAOJに提出すれば正しく採点はしてくれるのでその点は大丈夫。AOJでは他人の書いたコードも見れるので、それを参考にしても良い。新しい本でわかりやすいので基本的にはこの本をおすすめしたい。

まとめ

アルゴリズムの勉強を実践的に(実際にコードを書きながら)したいなら、この3冊のどれかになると思う。

かなと思う。一番のオススメは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」である。是非参考にして欲しい。

番外編

番外編で「世界で闘うプログラミング力を鍛える150問」というのも割と有名ではあるが、この本よりは上記の3冊をおすすめしたい。

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

*1:https://www.topcoder.com/

*2:https://atcoder.jp/

*3:会津大学が運営しているプログラミングコンテストサイト http://judge.u-aizu.ac.jp/onlinejudge/

*4:この本は連載をそのまま本に落としただけなので、高橋直大先生は「書籍用に書き直して第二版を書きたい」とずっと言っている