どんな本？

「最小カット、雰囲気で解いてませんか」と問い詰めてくる1500ページ超の鈍器。競プロで最大流ライブラリを貼るだけの日々が、劣モジュラ関数やマトロイド交叉まで含めた組合せ最適化の壮大な地図として繋がって見えてきます。Schrijver御大が線形計画双対から多面体的組合せ論、ネットワークフローの最小カットまで、証明を省略せず淡々と積み上げてくれるのがすごい。読み終わる頃には競プロが「Schrijverの応用問題」に見えてくるという副作用付き。というか、読み終わる日は来るのでしょうか。

どんな本？

「劣モジュラって、なんか強そうな響き」で止まっていませんか。集合関数の最適化と聞いて回れ右した過去がある方こそ、この本の出番です。最小カットや施設配置がなぜ効率よく解けるのか、その裏で働いているのが劣モジュラ性という「離散版の凸性」。貪欲法が理論保証つきで動く気持ちよさ、機械学習の特徴選択やセンサ配置への応用まで、風通しよく繋げてくれるのがありがたい。読み終える頃には「とりあえず劣モジュラかどうか確認しよう」という新しい口癖が手に入ります。副作用として日常会話が通じなくなる恐れあり。

どんな本？

「計算量オーダーって何ですか？」と面接で聞かれて汗が止まらなくなった経験、ありませんか。この本は動的計画法から貪欲法、グラフ理論、そしてネットワークフローの最小カットまで、なんとなく避けてきた武器を一通り手渡してくれます。図が丁寧なので、これまで呪文にしか見えなかったダイクストラ法もすっと入ってくるのがすごい。AtCoder緑を目指す人にも、業務でO(n²)を書いて怒られた人にもおすすめ。読み終わる頃には、日常のちょっとした選択も貪欲法で解きたくなる副作用があるので注意。

どんな本？

「動的計画法、なんとなく書ける」から「なぜこの漸化式で正しいのか説明できる」への昇格試験のような一冊。分割統治、貪欲法、ネットワークフロー、NP完全性まで、アルゴリズム界の主要キャストが総出演します。特にフローと最小カット周りの丁寧さが際立っていて、双対性の直感を掴んだ瞬間、AtCoderの問題文が急に別言語に見えてくる。ページ数は鈍器級ですが、証明が「なるほど」で終わるのが快感なのです。積読しても本棚の格が上がる、副作用まで優秀な名著。