この記事は、Competitive Programming Advent Calendar 2017 - Adventarの22日目の記事です。
「前編」とありますが、完成がいつになるのか、そして次回が中編なのか後編なのかは全く未定です。
(注・2018・2019のAdvent Calendarでも続編はありません。）
ちなみに昨年分はこちらです。
Advent Calendar 2016 : ABC#001のA問題をコンパクトに解く - kmjp's blog
はじめに
すでに世の中には、日本語による競技プログラミングの解説書や教材が出ています。
著名なものには下記の物があります。*1
- プログラミングコンテストチャレンジブック [第2版] | マイナビブックス (通称蟻本)
- 最強最速アルゴリズマー養成講座 | SBクリエイティブ (通称チーター本)
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 | マイナビブックス (通称AOJ本・螺旋本・TLE本)
- 東京大学全学自由セミナー 実践的プログラミング教材 問題解決のためのプログラミング一巡り2014年度版
それとは別に一部で話題になった解説書としてCompetitive programming books（以後CPHBと略す）があります。
著者の努力に感銘を受け、かつ自分の勉強になるかと思ったので、夏ごろから和訳を始めてみました。
最初こそ順調だったものの、さすがに著者が４年かけただけあり量が膨大で、残念ながら半分どころか8章/30章しか終わらなかった*2のですが、参考までに途中版を載せておきます。
ライセンスは原著に準拠します。
私は校正のプロでもアルゴリズムのプロでもなく、また時間も十分掛けられていないので、あくまで参考に留めてください。
わかりにくい点は原著を参照して頂いた方が正確です。
CPHB邦訳PDF(WIP)
GitHub - kmjp/cphb at jp
これだけではなんなので、以下本書の内容の概要(日本語訳未完部分も含む)を紹介します。
本書の内容
CPHBは他の書籍に比べ、問題例の記載が少なく、その分網羅しているアルゴリズムが多いです。
例が少ないと言っても、実際のコンテスト問題の記載がないだけで、アルゴリズム解説自体はちゃんとしています。
アルゴリズムのカバー範囲だけなら蟻本よりも広いため、蟻本を読んだ人も一周目を通してみるとよいと思います。
特に21章以降のAdvanced Topicsは中級者以上の人にも参考になるでしょう。
また、参考文献の記載が充実していて、「このアルゴリズムは何年に誰々が提案した」などの脚注が豊富なため、その観点でも勉強になります。
| 章 | 内容 |
|---|---|
| 1 Introduction | はじめに |
| 1.1 Programming languages | 言語の説明 |
| 1.2 Input and output | 標準入出力 |
| 1.3 Working with numbers | 基本的な演算 |
| 1.4 Shortening code | typedefやマクロ |
| 1.5 Mathematics | 簡単な総和の公式や集合論、ブール演算、対数 |
| 1.6 Contests and resources | 他のコンテスト |
| 2 Time complexity | 時間計算量 |
| 2.1 Calculation rules | 計算量の計算方法 |
| 2.2 Complexity classes | 計算量クラス |
| 2.3 Estimating efficiency | 効率の概算方法 |
| 2.4 Maximum subarray sum | 部分列の最大値の求め方から計算量を学ぶ |
| 3 Sorting | ソート |
| 3.1 Sorting theory | 基本的なソート |
| 3.2 Sorting in C++ | C++のライブラリにおけるソート |
| 3.3 Binary search | 二分探索の活用法 |
| 4 Data structures | (おもにC++における)データ構造 |
| 4.1 Dynamic arrays | vector |
| 4.2 Set structures | set |
| 4.3 Map structures | map |
| 4.4 Iterators and ranges | イテレータ |
| 4.5 Other structures | bitset, deque, stack, queue, priority_queue, policyベースデータ構造 |
| 4.6 Comparison to sorting | ソートの計算量 |
| 5 Complete search | 全探索 |
| 5.1 Generating subsets | 部分集合の列挙 |
| 5.2 Generating permutations | 順列の列挙 |
| 5.3 Backtracking | バックトラック |
| 5.4 Pruning the search | 枝刈り探索 |
| 5.5 Meet in the middle | 半分全列挙 |
| 6 Greedy algorithms | 貪欲法 |
| 6.1 Coin problem | コイン問題を例に貪欲法を説明 |
| 6.2 Scheduling | 区間スケジューリング |
| 6.3 Tasks and deadlines | タスク実行順問題 |
| 6.4 Minimizing sums | 差の累乗の総和の最小化 |
| 6.5 Data compression | 圧縮とハフマン符号 |
| 7 Dynamic programming | 動的計画法 |
| 7.1 Coin problem | コイン問題再び（メモ化再帰） |
| 7.2 Longest increasing subsequence | 最長増加部分列 |
| 7.3 Paths in a grid | グリッド上のパスの最小コスト経路 |
| 7.4 Knapsack problems | ナップサック問題 |
| 7.5 Edit distance | 編集距離 |
| 7.6 Counting tilings | タイルの並べ方 |
| 8 Amortized analysis | ならし解析 |
| 8.1 Two pointers method | 尺取り法 |
| 8.2 Nearest smaller elements | 最寄の小さな要素の探索 |
| 8.3 Sliding window minimum | スライド最小値 |
| 9 Range queries | 区間クエリ |
| 9.1 Static array queries | 累積和 |
| 9.2 Binary indexed tree | BIT |
| 9.3 Segment tree | セグメントツリー |
| 9.4 Additional techniques | 座標圧縮・区間更新 |
| 10 Bit manipulation | ビット演算の活用 |
| 10.1 Bit representation | ビット表現 |
| 10.2 Bit operations | ビット演算とGCCの組み込み命令 |
| 10.3 Representing sets | ビットマスクによる部分集合の表現 |
| 10.4 Bit optimizations | ビット演算による処理の最適化 |
| 10.5 Dynamic programming | BitDP、部分集合数え上げ |
| II Graph algorithms | グラフアルゴリズム |
| 11 Basics of graphs | グラフの基本 |
| 11.1 Graph terminology | 用語集 |
| 11.2 Graph representation | グラフの表現方法（隣接行列・隣接リスト） |
| 12 Graph traversal | グラフの探索 |
| 12.1 Depth-first search | 深さ優先探索 |
| 12.2 Breadth-first search | 幅優先探索 |
| 12.3 Applications | 実用例（連結性チェック・閉路検出・二部グラフ判定） |
| 13 Shortest paths | 最短経路 |
| 13.1 Bellman–Ford algorithm | ベルマンフォード法・負の閉路 |
| 13.2 Dijkstra’s algorithm | ダイクストラ法・負の閉路 |
| 13.3 Floyd–Warshall algorithm | ワーシャルフロイト法 |
| 14 Tree algorithms | 木構造に対するアルゴリズム |
| 14.1 Tree traversal | 木の探索 |
| 14.2 Diameter | 直径 |
| 14.3 All longest paths | 最長路の列挙 |
| 14.4 Binary trees | 二分木 |
| 15 Spanning trees | スパニングツリー |
| 15.1 Kruskal’s algorithm | クラスカル法 |
| 15.2 Union-find structure | Union-Findデータ構造 |
| 15.3 Prim’s algorithm | プリム法 |
| 16 Directed graphs | 有向グラフに対するアルゴリズム |
| 16.1 Topological sorting | トポロジカルソート |
| 16.2 Dynamic programming | DAGに対するDP |
| 16.3 Successor paths | ダブリング |
| 16.4 Cycle detection | 閉路検出・フロイト法 |
| 17 Strong connectivity | 強連結 |
| 17.1 Kosaraju’s algorithm | 強連結成分分解 |
| 17.2 2SAT problem | 2SATへの応用 |
| 18 Tree queries | 木に対するクエリ |
| 18.1 Finding ancestors | 祖先の検索・ダブリング |
| 18.2 Subtrees and paths | オイラーツアー・サブツリーやパスに対するクエリ |
| 18.3 Lowest common ancestor | 最小共通先祖(LCA)・ノード間距離 |
| 18.4 Offline algorithms | データ構造をマージする一般的なテク |
| 19 Paths and circuits | パスと閉路 |
| 19.1 Eulerian paths | オイラー閉路を作成するHierholzerアルゴリズム |
| 19.2 Hamiltonian paths | ハミルトンパス |
| 19.3 De Bruijn sequences | De Bruijn列 |
| 19.4 Knight’s tours | ナイトツアー問題 |
| 20 Flows and cuts | 最大フローと最小カット |
| 20.1 Ford–Fulkerson algorithm | フォード・フルカーソン法 |
| 20.2 Disjoint paths | 辺・点を共有しないパス |
| 20.3 Maximum matchings | 最大マッチング・Hallの定理・Kőnigの定理 |
| 20.4 Path covers | パス被覆・Dilworthの定理 |
| III Advanced topics | さらに進んだ話題 |
| 21 Number theory | 整数論 |
| 21.1 Primes and factors | 素数・素因数分解・エラトステネスの篩・ユークリッドの互除法・オイラーのトーシェント関数 |
| 21.2 Modular arithmetic | モジュラ演算・フェルマーの小定理・オイラーの定理・逆元 |
| 21.3 Solving equations | ディオファントス方程式・中国人剰余定理 |
| 21.4 Other results | ラグランジュ法・ゼッケンドルフの定理・ピタゴラス数・ウィルソンの定理 |
| 22 Combinatorics | 組み合わせ |
| 22.1 Binomial coefficients | 二項係数 |
| 22.2 Catalan numbers | カタラン数・括弧列の数え上げ・木の数え上げ |
| 22.3 Inclusion-exclusion | 包除原理 |
| 22.4 Burnside’s lemma | バーンサイドの補題 |
| 22.5 Cayley’s formula | ケイリーの公式・Prüfer code |
| 23 Matrices | 行列 |
| 23.1 Operations | 行列の和・積・累乗・行列式・逆行列 |
| 23.2 Linear recurrences | 線形回帰・漸化式・フィボナッチ数列 |
| 23.3 Graphs and matrices | 行列によるグラフ処理・パスの数え上げ・最短経路・キルヒホッフの定理 |
| 24 Probability | 確率論 |
| 24.1 Calculation | 計算方法 |
| 24.2 Events | 事象・余事象・和事象・積事象・条件付き確率 |
| 24.3 Random variables | 期待値・分散 |
| 24.4 Markov chains | マルコフ連鎖 |
| 24.5 Randomized algorithms | 乱拓アルゴリズム・モンテカルロ法・グラフ彩色 |
| 25 Game theory | ゲーム論 |
| 25.1 Game states | 状態・状態遷移グラフ |
| 25.2 Nim game | NimとMisère ゲーム |
| 25.3 Sprague–Grundy theorem | Grundy数 |
| 26 String algorithms | 文字列に対するアルゴリズム |
| 26.1 String terminology | 基本的な用語 |
| 26.2 Trie structure | Trieデータ構造 |
| 26.3 String hashing | ローリングハッシュ・衝突・誕生日パラドックス |
| 26.4 Z-algorithm | Zアルゴリズム |
| 27 Square root algorithms | 平方分割 |
| 27.1 Combining algorithms | ２種類のアルゴリズムの使い分け |
| 27.2 Integer partitions | ナップサック問題・文字列構築 |
| 27.3 Mo’s algorithm | Mo's Algorithm |
| 28 Segment trees revisited | セグメントツリーの応用的な話題 |
| 28.1 Lazy propagation | 遅延伝搬処理・多項式の更新 |
| 28.2 Dynamic trees | 動的木・永続セグメントツリー |
| 28.3 Data structures | セグメントツリーのノードにさらに複雑な値を載せる |
| 28.4 Two-dimensionality | 二次元セグメントツリー |
| 29 Geometry | 幾何 |
| 29.1 Complex numbers | 複素数 |
| 29.2 Points and lines | 頂点と直線の表現・直線の交点・多角形の内外判定 |
| 29.3 Polygon area | 多角形の面積・ピックの公式 |
| 29.4 Distance functions | マンハッタン距離 |
| 30 Sweep line algorithms | 平面走査 |
| 30.1 Intersection points | 直線の交点数え上げ |
| 30.2 Closest pair problem | 再近傍点対 |
| 30.3 Convex hull problem | 凸法の構成 |
感想とまとめ
去年に続きネタ被りをしないよう気を付けていたのですが、おそらくネタ被りはなかったので安心しています。
夏ごろ少し訳し始めてみて、これはAdvent Calendarまでに結構いいところまで行けるかと思いましたが、やはり時間の確保が難しく1/3すら到達できなかったのが残念です。
このぐらい雑な訳でも1章3時間はかかるんですよね。
せめて10章まで行ければよい区切りだったのですが、git操作ミスによる巻き戻しがきつかったです。
今回8章までということでまだ基本的な内容のみですが、それでもしばしば知らない項目が出てきて非常に参考になりました。
中級者以上も一周目を通すことをお勧めします。蟻本を補完するのにも役に立つでしょう。
和訳だけでもしんどかったので、これを何年もかけて作り上げたAntti Laaksonenには頭が下がります。
これ図も全部TeX上で描いてるんですよね。おかげでこちらは追加のソフトが不要で、図はほぼ使いまわしで和訳できました。
またアルゴリズムについて初出の文献を調べたり、これを作るのにかかった労力がどれだけのものか想像できません。
和訳は半分どころか1/4しか進まなかったので、来年以降も継続できるのか、そして完訳まで何年かかるか不明です。
来年には高確率で競技プログラミングおよびこのブログ執筆を半引退状態になる見込みなので…。
来年のCalendarでは、引退状態になってたらポエムでも書こうかな。でもそれなら先に和訳すませないとな。
明日23日はHiroyuki-Nagataさんの「競プロ始めた」です。
競プロ始めた・続けたという記事は読んでてこちらのモチベーションが上がることも多く好みなトピックなので、期待したいですね。
