目指せアリ充！「プログラミングコンテスト チャレンジブック」を中級編まで読み終えた

書籍

リア充になれないならアリ充になればいいじゃない
というわけで1月から毎日1時間「プログラミングコンテスト チャレンジブック」通称「アリ本」を読んでいた。1ヶ月が経過しなんとか中級編まで読み終わったので感想や学んだことなどをメモしておく。


農夫ジョンの奇妙な冒険
本書で扱う問題にたびたび農夫ジョンという人物が登場する。彼は最初の頃は飼っている牛の小屋の配置などを考えたり後ろ向きな牛を前向きにしたりと牛を働かせようと必死。しかし次第に優秀な牛とそうでない牛がいることに気づいたジョンは牛に食事やドリンクを振舞うなど牛の待遇改善が重要であると悟る。そして自我に目覚めた牛と農夫ジョンとの関係は意外な方向に・・・。というわけで農夫ジョンにまつわる壮大な物語が楽しめるのがアリ本最大の特徴。こんな素敵な物語を楽しみつつアルゴリズムも学べるとあっては、もう読むしかないよね！

初級編の壁！動的計画法
私にとって本書で最初の壁が動的計画法だった。値の動きがなかなかイメージできずに苦労したし、問題から漸化式を導くのも全く思いつかず解答を見て驚くこと多数。とはいえ何問も解いているうちに多少は慣れてきた気がする。というより唯一の攻略法が慣れなんじゃないか疑惑。まだ使いこなせているとは言えないけど、この本読む前のような苦手意識はなくなってきている。

中級編のヤマ場！？ネットワークフロー
本書で一番勉強になったのがこれ。以前は苦手だったのだけど本書のおかげで随分親しみを感じるようになった。ネットワークフローは馴染みのない人も多いかもしれないのだけど、簡単に言うと最適パスを求める問題の拡張版みたいなもの。どう拡張したのかというと、初級編ででてくるような最適パスは一本の最適パスが見つかればよくて、これはダイクストラ法やベルマンフォード法で解ける。
一方でネットワークフローはパスが複数ある時に、パス全体での最適化を考える。でパス全体で最適化するのにそれぞれのパスを順番に最適化すると、最初のほうで最適化したパスが有利になってしまう(後で最適化するパスは残り物のパスしか使えないので)。なので後で最適化するパスは既にあるパスよりもトータルでよくなるパスがあるなら最適化済みのパスの書き換えOK、みたいなのを許すのがネットワークフロー(でいいのかな。自信なし)。
ネットワークフローは安定マッチング問題やグラフ最小カット問題でキーとなる考え方で適用範囲が非常に広くアリ本でもかなりのページ数を割いていてとても勉強になった。

いよいよ上級編・・・！
というわけで明日から上級編を読むよ！ぺらぺら見た感じでは大学のときに悩まされた中国剰余定理とかメビウスとかオイラーとかの名前がちらほら見え隠れしていて今から身震い、もとい武者震いがいたします。頑張って読むよ。あと全体的に理解が万全でないので読み終わったら2週目に入りたい感じ。