プログラミングコンテストチャレンジブック (通称、蟻本) の AtCoder 化プロジェクトは、初級編、中級編、上級編で一旦完結していますが、ここでは、P.362～363 に載っている発展的トピックや、その他蟻本では触れられていない話題を随時載せていきたいと思います。
【注意】
本記事の趣旨からしてどうしてもネタバレ問題は生じてしまいますので、それについては了承いただければと思います。
今後随時更新していきますので、各問題の解説などの参考記事やよりよい問題案などの意見をガンガン募集しています。
【シリーズ】
- AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
- AtCoder 版！蟻本 (初級編)
- AtCoder 版！蟻本 (中級編)
- AtCoder 版！蟻本 (上級編)
5 グラフ・組合せ最適化
例題 5-1 オイラー閉路
【キーワード】
- オイラー路
- オイラー閉路
【AtCoder 上の類題】
- AOJ 0225 Kobutanukitsuneko (しりとりです)
- CSA 061 F Xor the Graph (グラフのウォーク被覆問題です)
- SRM 322 DIV1 Medium ExtendedDominoes (オイラー閉路の場合の数も求めます)
【コメント】
オイラー路に関する問題です。しりとりは典型的な例ですが、時としてかなり鮮やかな使い方ができるときもありますね。
- 競プロにおけるオイラー路とその応用について (こうきさん)
例題 5-2 最小有向木
【キーワード】
- 最小有向木
- マトロイド交差
【AtCoder 上の類題】
- AOJ Course Minimum-Cost Arborescence (実は AOJ course の中にあります)
- Japan Alumni Group Summer Camp 2014 Day 4 I 首都
【コメント】
無向グラフの全域最小木は Kruskal のアルゴリズムで求められますが、有向グラフの最小全域有向木を求める問題です。マトロイド交差問題に帰着できることも知られていますが、専用の O(mn) な Chu-Liu/Edmonds のアルゴリズムも知られており、meldable heap を用いたもっと高速なアルゴリズムも知られているようです:
- 最小全域有向木（m log n） (ジョイさん)
例題 5-3 関節点・橋
【キーワード】
- 関節点・橋
- 二重辺連結成分分解
- 二重点連結成分分解
【AtCoder 上の類題】
- ABC 075 C Bridge (ABC の C 問題なのでオーバーキルですが、二重辺連結成分分解ライブラリで殴れます)
- ARC 039 D 旅行会社高橋君 (二重辺連結成分分解によってつぶされたツリーの各頂点の edge-connectivity は 2 になります)
- 2015 天下一 予選A D ハシポン (とりあえず二重辺連結成分分解します)
- ARC 045 D みんな仲良し高橋君 (二重点連結成分分解します、面白いです)
【コメント】
高難易度問題で時々見かける感じですね。いつかの ICPC World Final でも二重辺連結成分分解を使って鮮やかに解く問題があった気がします。
例題 5-4 全域最小カット
【キーワード】
- 最小カット
- 全域最小カット
- (対称) 劣モジュラ関数最小化
【AtCoder 上の類題】
なさそう？
【コメント】
最小カットは多くの場合 2 点 s, t 間で行いますが、グラフ全体で頂点集合 S, V に分けて、その間のカットを最小化する問題です。単に全 2 頂点を試すよりは高速な解法があります。全域最小カットは劣モジュラ関数最小化の特別な例ではありますが、反対にどのような劣モジュラ関数のクラスが最小カットとして表されるかというのは組合せ最適化の分野で現在なお重要な研究課題です。
例題 5-5 単体法
【キーワード】
- LP
- IP
- LP 緩和
- フロー
- 単体法
【AtCoder 上の類題】
- SRM 231 DIV1 Hard Mixture (単体法の verify その 1)
- UVa 10498 Happiness (単体法の verify その 2)
- AOJ 0091 Blur (integrality がよくわからないですが単体法でも通りました、ということはもしかしたらフロー解があるのかもです)
【コメント】
LP に定式化して単体法で解くことができるタイプの問題は稀に見る気がします。
そのような問題でなくても、問題をとりあえず LP や IP に定式化してみることで、フロー解を思いつくことができるケースもよくある気がします。
例題 5-6 マトロイド
【キーワード】
- マトロイド
- Greedy アルゴリズム
- 全域最小木問題
- 行列の一次独立性
- マトロイド交差問題
【AtCoder 上の類題】
- RUPC 2018 day2 C Ball (マトロイドを知らなくても Greedy が自然ですがマトロイドです)
- SRM 526.5 DIV1 Hard MagicMatchesGame (ベクトルマトロイド上の Greedy アルゴリズムで解きます)
- AOJ 1605 橋の建造計画 (マトロイドになるという話が少し話題になりました)
- 一般グラフから edge-disjoint な全域木を最大何個パッキングできるか
- ACM-ICPC 2017 Asia H Homework (DEGwer さんのツイートを参照)
【コメント】
時々見かけるマトロイドの話題です。全域最小木問題を解く有名な Kruskal のアルゴリズムは、より一般に「マトロイド上の Greedy アルゴリズム」の特別な例であるとみなせます。他にマトロイド交差問題とよばれるクラスを考えると面白い問題例がたくさん発生します。
- Matroid maximization (前原さん)
- マトロイドの凸構造 (けんちょん)
6 数値計算
例題 6-1 三分探索、黄金分割法
【キーワード】
- 凸最適化
- 三分探索
- 黄金分割法
【AtCoder 上の類題】
【コメント】
三分探索は、特に ICPC 系だとそれなりによく見かける気がします。
- 競技プログラミングにおける二分探索・三分探索問題まとめ (はまやんさん)
例題 6-2 Karatsuba 法、高速フーリエ変換 (FFT)
【キーワード】
- Karatsuba 法
- 高速フーリエ変換
【AtCoder 上の類題】
- ATC 001 C 高速フーリエ変換 (verify)
- AGC 021 F Trinity (割と最近の問題です)
- Codeforces 176 DIV1 E Ladies' Shop (考察が面白かったです)
【コメント】
FFT に類するアルゴリズムもそれなりに見かける気がします。
7 数論
例題 7-1 離散対数
【キーワード】
- 離散対数
- Baby-step Giant-step
【AtCoder 上の類題】
- ARC 042 D あまり (離散対数を求める Baby-Step Ginat-Step を用います)
- UTPC 2014 K 乱数調整 (同じく BSGS です)
- CSA 059 DIV2 E Fibonacci Mod (BSGS です)
【コメント】
時々見る話題、離散対数です。離散対数を求める Baby-step Giant-step アルゴリズムは、離散対数に限らず様々な場面で活用できます。
例題 7-2 スターンブロコット木
【キーワード】
- スターンブロコット木
【AtCoder 上の類題】
- Project Euler 415 Titanic sets
- Japan Alumni Group Spring Contest 2014 G Proportional Representation (スターンブロコット木ではないですが、有理数の二分探索をする超難問です)
【コメント】
有理数の区間を頂点とする二分探索木です。問題例はあまり見たことがないです。
8 探索
例題 8-1 α-β 探索
【キーワード】
- 探索
- α-β 探索
【AtCoder 上の類題】
- KUPC 2016 F 早解き (α-β 的なことをします)
- Japan Alumni Group Summer Camp 2013 Day 4 E Optimal alpha beta pruning (α-β します)
- ABC 032 D ナップサック問題 (DP や半分全列挙で解きますが分枝限定法でまとめて解くこともできます)
- JAG Practice Contest for ACM-ICPC Asia Regional 2013 J Magical Switches (枝刈り探索しますが計算時間の指数の底を評価できたりして面白いです)
【コメント】
ゲームの最適手の探索を高速化します。
例題 8-2 特殊な全探索 (蟻本外)
【キーワード】
- 特殊な全探索や、難しい全探索など
【AtCoder 上の類題】
- ARC 095 E Symmetric Grid (マッチングを全探索)
- Maximum-Cup 2018 G Sparrow's trick (トーナメントを全探索)
- RUPC 2018 day2-D AABABCAC (トーナメント全探索に似ています、入れ子構造を全探索)
- AOJ 2427 ほそながいところ (難しめの全探索です)
【コメント】
「実は全探索だった」的な問題が苦手なので、自戒の意味も込めて、特殊な全探索や難しい全探索を載せていきます。
9 データ構造
例題 9-1 平衡二分探索木
【キーワード】
- 平衡二分探索木
【AtCoder 上の類題】
- yukicoder 0649 ここでちょっとQK！ (座圧 + BIT で解けますが、平衡二分探索木を持っていると殴れます)
- JOI 2012 春合宿 day4-2 コピー＆ペースト (永続平衡二分探索木として伝説的な問題です、問題はここ)
- ARC 030 D グラフではない (遅延評価機能付き永続平衡二分探索木です)
【コメント】
伝家の宝刀、平衡二分探索木です。自分なりの平衡二分探索木ライブラリの盆栽は結構楽しいです。
- プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～ (秋葉さん)
- 競技プログラミングにおける平衡二分木問題まとめ (はまやんさん)
例題 9-2 Meldable Heap
【キーワード】
- Meldable Heap
【AtCoder 上の類題】
- UTPC 2012 J じょうしょうツリー (秋葉さんの解説が印象的でした)
【コメント】
2 つのキューを併合することもできる順位キューです。
例題 9-3 HL 分解
【キーワード】
- HL 分解
【AtCoder 上の類題】
【コメント】
ツリー上のクエリ処理に有効な手法です。ライブラリとして持っていると強い感じです。他にも HL 分解が使える問題は色々ありそうです。
- Heavy-Light Decomposition (beet さん)
- HL decomposition+SegTreeのlogを1個消す (yosupo さん)
- 競技プログラミングにおけるHL分解まとめ (はまやんさん)
10 文字列
例題 10-1 KMP 法、Aho-Corasick 法
【キーワード】
- 文字列検索
- KMP 法、Aho-Corasick 法
【AtCoder 上の類題】
- yukicoder No.430 文字列検索 (ロリハでも、Trie でも、Aho-Corasick でもできます、ライブラリ整備に)
- RUPC 2018 day3-G 検閲により置換 (Censored String) (Aho-Corasick の練習に)
- JOI 2010 春合宿 day2-2 DNA synthesizer (Trie や Aho-Corasick で解きます, 問題はここ)
- AOJ 2257 桜詩 願はくは花の下にて春死なむ (Aho-Corasick)
- JAG Practice Contest for ACM-ICPC Asia Regional 2017 H Separate String (Aho-Corasick)
【コメント】
KMP 法、Aho-Corasick 法ともに線形時間で文字列検索を行えます。前処理として検索文字列をオートマトンに変換するので、これを利用して問題を解きます。
例題 10-2 Manacher のアルゴリズム
【キーワード】
- 文字列検索
- 回文
- Manacher のアルゴリズム
【AtCoder 上の類題】
- Xmas Contest 2015 C Colored Tiles (Manacher で解けます、n_vip さん提供)
【コメント】
文字列から回文を探すアルゴリズムです。「まあ、なんか...」という感じですね。
例題 10-3 構文解析
【キーワード】
- 構文解析
【AtCoder 上の類題】
- AOJ 0109 Smart Calculator
- AOJ 1346 Miscalculation
- AOJ 1102 Calculation of Expressions (複素数です、大量のコーナーケースがあります)
- AOJ 2523 Time Complexity
【コメント】
ICPC でよく見る出題です。再帰下降型の構文解析器だけでもライブラリとして持っていると解ける問題は多いです。
11. 個人的に思う他のテーマたち
*例題 11-1 *
【キーワード】
【AtCoder 上の類題】
【コメント】
-1 おわりに
体系化できそうな何か新しい話題を見かける度に、随時更新していきたいと思います。