Edited at

AtCoder 版!蟻本 (発展的トピック編)

プログラミングコンテストチャレンジブック (通称、蟻本) の AtCoder 化プロジェクトは、初級編中級編上級編で一旦完結していますが、ここでは、P.362~363 に載っている発展的トピックや、その他蟻本では触れられていない話題を随時載せていきたいと思います。

【注意】


  • 本記事の趣旨からしてどうしてもネタバレ問題は生じてしまいますので、それについては了承いただければと思います。


  • 今後随時更新していきますので、各問題の解説などの参考記事やよりよい問題案などの意見をガンガン募集しています。


  • 関連プロジェクトとして、こうきさんによる Atcoder 過去問に自動的にタグをつけるサービスの AtCoder Finder や、類似プロジェクトの Project Dijkstra、つたじぇー☆さんによる蟻本練習問題解説があります。皆で相補的に活動できたらいいなと思います。


【シリーズ】


5 グラフ・組合せ最適化



例題 5-1 オイラー閉路

【キーワード】


  • オイラー路

  • オイラー閉路

【AtCoder 上の類題】

【コメント】

オイラー路に関する問題です。しりとりは典型的な例ですが、時としてかなり鮮やかな使い方ができるときもありますね。




例題 5-2 最小有向木

【キーワード】


  • 最小有向木

  • マトロイド交差

【AtCoder 上の類題】

【コメント】

無向グラフの全域最小木は Kruskal のアルゴリズムで求められますが、有向グラフの最小全域有向木を求める問題です。マトロイド交差問題に帰着できることも知られていますが、専用の O(mn) な Chu-Liu/Edmonds のアルゴリズムも知られており、meldable heap を用いたもっと高速なアルゴリズムも知られているようです:




例題 5-3 関節点・橋

【キーワード】


  • 関節点・橋

  • 二重辺連結成分分解

  • 二重点連結成分分解

【AtCoder 上の類題】

【コメント】

高難易度問題で時々見かける感じですね。いつかの ICPC World Final でも二重辺連結成分分解を使って鮮やかに解く問題があった気がします。




例題 5-4 全域最小カット

【キーワード】


  • 最小カット

  • 全域最小カット

  • (対称) 劣モジュラ関数最小化

【AtCoder 上の類題】

なさそう?

【コメント】

最小カットは多くの場合 2 点 s, t 間で行いますが、グラフ全体で頂点集合 S, V に分けて、その間のカットを最小化する問題です。単に全 2 頂点を試すよりは高速な解法があります。全域最小カットは劣モジュラ関数最小化の特別な例ではありますが、反対にどのような劣モジュラ関数のクラスが最小カットとして表されるかというのは組合せ最適化の分野で現在なお重要な研究課題です。




例題 5-5 単体法

【キーワード】


  • LP

  • IP

  • LP 緩和

  • フロー

  • 単体法

【AtCoder 上の類題】

【コメント】

LP に定式化して単体法で解くことができるタイプの問題は稀に見る気がします。

そのような問題でなくても、問題をとりあえず LP や IP に定式化してみることで、フロー解を思いつくことができるケースもよくある気がします。




例題 5-6 マトロイド

【キーワード】


  • マトロイド

  • Greedy アルゴリズム

  • 全域最小木問題

  • 行列の一次独立性

  • マトロイド交差問題

【AtCoder 上の類題】

【コメント】

時々見かけるマトロイドの話題です。全域最小木問題を解く有名な Kruskal のアルゴリズムは、より一般に「マトロイド上の Greedy アルゴリズム」の特別な例であるとみなせます。他にマトロイド交差問題とよばれるクラスを考えると面白い問題例がたくさん発生します。



6 数値計算



例題 6-1 三分探索、黄金分割法

【キーワード】


  • 凸最適化

  • 三分探索

  • 黄金分割法

【AtCoder 上の類題】

【コメント】

三分探索は、特に ICPC 系だとそれなりによく見かける気がします。




例題 6-2 Karatsuba 法、高速フーリエ変換 (FFT)

【キーワード】


  • Karatsuba 法

  • 高速フーリエ変換

【AtCoder 上の類題】

【コメント】

FFT に類するアルゴリズムもそれなりに見かける気がします。



7 数論



例題 7-1 離散対数

【キーワード】


  • 離散対数

  • Baby-step Giant-step

【AtCoder 上の類題】

【コメント】

時々見る話題、離散対数です。離散対数を求める Baby-step Giant-step アルゴリズムは、離散対数に限らず様々な場面で活用できます。




例題 7-2 スターンブロコット木

【キーワード】


  • スターンブロコット木

【AtCoder 上の類題】

【コメント】

有理数の区間を頂点とする二分探索木です。問題例はあまり見たことがないです。



8 探索



例題 8-1 α-β 探索

【キーワード】


  • 探索

  • α-β 探索

【AtCoder 上の類題】

【コメント】

ゲームの最適手の探索を高速化します。




例題 8-2 特殊な全探索 (蟻本外)

【キーワード】


  • 特殊な全探索や、難しい全探索など

【AtCoder 上の類題】

【コメント】

「実は全探索だった」的な問題が苦手なので、自戒の意味も込めて、特殊な全探索や難しい全探索を載せていきます。



9 データ構造



例題 9-1 平衡二分探索木

【キーワード】


  • 平衡二分探索木

【AtCoder 上の類題】

【コメント】

伝家の宝刀、平衡二分探索木です。自分なりの平衡二分探索木ライブラリの盆栽は結構楽しいです。




例題 9-2 Meldable Heap

【キーワード】


  • Meldable Heap

【AtCoder 上の類題】

【コメント】

2 つのキューを併合することもできる順位キューです。




例題 9-3 HL 分解

【キーワード】


  • HL 分解

【AtCoder 上の類題】

【コメント】

ツリー上のクエリ処理に有効な手法です。ライブラリとして持っていると強い感じです。他にも HL 分解が使える問題は色々ありそうです。



10 文字列



例題 10-1 KMP 法、Aho-Corasick 法

【キーワード】


  • 文字列検索

  • KMP 法、Aho-Corasick 法

【AtCoder 上の類題】

【コメント】

KMP 法、Aho-Corasick 法ともに線形時間で文字列検索を行えます。前処理として検索文字列をオートマトンに変換するので、これを利用して問題を解きます。




例題 10-2 Manacher のアルゴリズム

【キーワード】


  • 文字列検索

  • 回文

  • Manacher のアルゴリズム

【AtCoder 上の類題】

【コメント】

文字列から回文を探すアルゴリズムです。「まあ、なんか...」という感じですね。




例題 10-3 構文解析

【キーワード】


  • 構文解析

【AtCoder 上の類題】

【コメント】

ICPC でよく見る出題です。再帰下降型の構文解析器だけでもライブラリとして持っていると解ける問題は多いです。



11. 個人的に思う他のテーマたち



*例題 11-1 *

【キーワード】




【AtCoder 上の類題】




【コメント】



-1 おわりに

体系化できそうな何か新しい話題を見かける度に、随時更新していきたいと思います。