第二版が出ます！プログラミングコンテストチャレンジブック

一昨年 9 月に初版が出て以来「蟻本」の愛称で皆様にご好評頂いていた僕と岩田 (id:wata_orz) と北川の「プログラミングコンテストチャレンジブック」ですが，お陰様で，このたび第二版が出版されます！第二版の発売日は 1/27 の予定です．よろしくお願いします．

（初版の紹介記事はこちら）

改訂による追加部分は，以下になります．

  • 4 つの新しいトピック：計算幾何，枝刈り探索，分割統治法，文字列アルゴリズム
  • 練習問題コーナー
  • 発展内容コーナー

ページは 50 ページ増となっています．

練習問題コーナー

練習問題コーナーでは，本書で取り上げた各トピックに関連したオンラインジャッジ上の問題を紹介しています．例題を理解するだけでなく，実際に練習問題を自分で解くことで，一層の定着や応用力の増強を図ることができます．

発展内容コーナー

発展内容コーナーでは，難易度や本の性質の都合等で本書で紹介していないものの，コンテストで必要になることのなる知識・テクニックを簡単に紹介しています．ここでのキーワードを元に，さらなる高みを目指してください．

4 つの新しいトピック

新たに追加されたのは，「計算幾何」「枝刈り探索」「分割統治法」「文字列アルゴリズム」の 4 つのトピックになります．これらはどれも，初版の頃から本来は扱いたかったものの，時間の都合等でやむなく諦めていたトピックであり，やはり重要なものです．
特に，計算幾何・枝刈り探索の 2 つは ICPC 等では最もメジャーなジャンルとすら言えます．これらが初版で後回しにされていたのは，GCJ をメインターゲットにしていたという事情と，著者の好みが影響しています．

計算幾何の節では，幾何の問題に対するアルゴリズムを考えるアプローチとして，ギリギリを考える，平面走査をする，凸包を取るなどといったアイディアを紹介しています．*1

枝刈り探索の節では，具体的な問題（数独と集合被覆問題）を取り上げつつ，ナイーブなアルゴリズムに，少しずつ枝刈りやヒューリスティクスを加えたり，IDA* 等より優れた探索手法を採用したりと，アルゴリズムを改善していきます．そこでのアイディアの多くは，他の問題でも使えるものです．

分割統治法の節では，列・ツリー・平面上の点集合といった，異なる対象において分割統治法のアルゴリズムを設計・実装する方法について説明します．

文字列アルゴリズムの節では，文字列が絡む動的計画法，文字列検索，そして接尾辞配列を扱います．特に，接尾辞配列は非常に強力な道具であるため，その応用法についても幅広く言及しています．

追加部分の目次

以下，追加部分の目次になります．

  • 3-6 平面・空間を扱う "計算幾何"
  • 4-5 工夫を凝らして賢く探索
    • 枝刈り
    • A* と IDA*
  • 4-6 分けて解いてまとめる! "分割統治法"
    • 列の分割統治法
    • ツリーの分割統治法
    • 平面の分割統治法
  • 4-7 文字列を華麗に扱う

*1:最初に線分の交差判定を扱っていますが，そのような基礎的な操作を網羅的に解説することはしていません．そのような部分は，単なる手計算や知識としての性質が強く，Web 上等に情報も多いため，本書では取り上げません．より経験やノウハウとしての性質が強い，考え方の部分に焦点を当てました．