「問題解決力を鍛える! アルゴリズムとデータ構造」を読んだ

「問題解決力を鍛える! アルゴリズムとデータ構造」を読んだので、そのメモです。章末問題は気になった問題しかやっていないので、時間を見つけてもう一度取り組みたい。

全体を通して感じたこと

本書を一言でいうと「丁寧」に尽きると思う。どこまで丁寧なんだ、というくらい丁寧。

まず解説が丁寧で用語もきちんと、できるだけ噛み砕いて説明してあります。図もたくさんあって、イメージをつけながら理解できます。その上コードもしっかり乗っていて、解説でわからなかったところは読んで理解できる。

解説が丁寧で他書やネットに頼らなくても読み進められるので、途中で思考が中断されないのがよかった。自分の場合は、子供を寝かしつけた後、深夜まで集中して一気に読み進められた。個人的には理論的な話と実装が別れているほうが好きなんだけど、わからないときにさっと実装を眺められるのは確かに嬉しいなと思った。

競技プログラミング向けの書籍はきちんと読んだことがなかったので、知らないことも多かった。ネットで拾った断片的な情報はいろいろ知っていたけど、この本を読んで断片的な知識がいろいろつながったのはとても良かった。

以下は面白いなと思ったところ

判定問題と最適化問題
二分探索の応用例として、最適化問題を判定問題に帰着させて解く方法が紹介されていた。読んでみれば、たしかにそうだよね、という内容だけど、いままで気づかなかったので面白かった。
Union Find
あまり知らなかったんですが、有名なのかも。Union Find はグループ分けを効率的に管理するデータ構造のこと。
- issame(x, y): x と y が同じグループに所属するかどうかを返す
- unite(x, y): x と y を含むグループを併合する
という演算が高速にできるのがポイント。最小全域木を求めるクラスカル法の効率的な実装などに利用できる。
トポロジカルソート
与えられた有向グラフに対し、各頂点を辺の向きに沿うように順序つけて並び替えることで、makeとかでうまいこと依存関係を解決するの使われている。実は深さ優先探索における再帰関数の抜けた順がそのままソート順になっているんだというのが面白いなと思った。
フォード・ファルカーソン法と残余グラフ
特に理屈があるわけではないんだけど、16章のネットワークフローの話は、やっぱり面白い。小学校のときに電気回路の話を水の流れで説明されたときに面白い、と思ったのを引きずっているだけかもしれない。

やっぱり競技プログラミング楽しそう（参画するとはいっていない）。10年前に買ってちゃんと読んでいなかった蟻本、もう一回開いてみよう。