アルゴリズム
AtCoder
競技プログラミング
新人プログラマ応援
蟻本
drken@drken
RevisionsEdit RequestsShow all likersShow article in Markdown
Report article

AtCoder 版！蟻本 (上級編)

アルゴリズムAtCoder競技プログラミング新人プログラマ応援蟻本

0 はじめに

初級編と中級編に続いて、今度は上級編です。

プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です:

  • POJ が国内ではあまり使用されなくなった (計算速度が遅いなど)
  • AtCoder 上で問題を解くことが盛んになった

今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほとんどすべて POJ 上の問題です) を AtCoder 上でジャッジできる問題に対応付けようという試みです。今回は上級編を扱います。AtCoder 上で見つからなかったものは AOJ, yukicoder 上の問題も載せています。

【注意】

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

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

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

【シリーズ】

4 さらに極める！ --- 上級編

4-1 より複雑な数学的問題

例題 4-1-1　ランダムウォーク

【キーワード】

  • 期待値
  • 連立一次方程式

【AtCoder 上の類題】

【コメント】
連立一次方程式を解いたりする問題です。双六のような確率的挙動が出て来ると連立一次方程式を解くことになるケースが多いイメージがあります。

参考記事:

例題 4-1-2　mod 演算あれこれ, Fermat の小定理, 中国剰余定理

【キーワード】

  • nCr
  • mod_inverse
  • Fermat の小定理、Euler の定理
  • 中国剰余定理、連立線形合同方程式

【AtCoder 上の類題】

【コメント】
nCr に関わる問題や、中国剰余定理・連立線形合同方程式を用いる問題などです。この辺りの話題についてもよい記事が豊富にあるので紹介します:

例題 4-1-3　包除原理

【キーワード】

  • 数え上げ
  • 包除原理

【AtCoder 上の類題】

【コメント】
包除原理を用いる問題です。典型的なものとしては「第二種スターリング数の導出」や「撹乱順列数え上げ」などがあります。少し難しくなると DP が絡むイメージがあります。他に高度な話題としては、彩色数や高速ゼータ変換などがあります。

参考記事:

例題 4-1-4　周期的でない文字列の数え上げ

【キーワード】

【AtCoder 上の類題】

【コメント】
包除原理のうち、特に約数に関係するものです。メビウス関数が登場するイメージがあります。蟻本や DEGwer さんの数え上げテクニック集に詳しい記載があります。

例題 4-1-5　石の塗り方の数え上げ

【キーワード】

【AtCoder 上の類題】

【コメント】
「ちょうど k 個分ずつ出て来る」みたいなことを利用する問題です。DEGwer さんの pdf のように「部分群のテクニック」と広くとらえるのはすごく面白いと思いました。

4-2 ゲームの必勝法を編み出せ！

例題 4-2-1　コインのゲーム１

【キーワード】

  • DP
  • ゲーム
  • ゲーム DP

【AtCoder 上の類題】

【コメント】
ゲームに関する DP です。難しい問題でなければゲーム木探索を理解していれば簡単です。

参考資料

例題 4-2-2　A Funny Game (POJ No.2484)

【キーワード】

  • ゲーム
  • 簡単な表式で解けるゲーム
  • 対称戦略 (相手のマネをする)

【AtCoder 上の類題】

【コメント】
explicit に解けるタイプのゲームです。A Funny Game はひたすら相手のマネをする戦略をとるのがよいゲームでした。必勝法が簡単な表式で表せるタイプのゲームでは、このような対称戦略を考えることは頻出のイメージです。ここでは数学的考察によって必勝法がシンプルに言い表せるタイプの問題を集めました。

例題 4-2-3　Euclid's Game (POJ No.2348)

【キーワード】

  • ゲーム
  • 自由度の観点から選べる手が実質的に高々 2 通りしかない

【AtCoder 上の類題】

  • ARC 085 D ABS　(ゲーム DP でも挙げた問題ですが、O(1) で解けます、問題の構造は Euclid's Game によく似ています)
  • AGC 010 D Decrementing　(難しめですが、結局選べる手が高々 2 通りしかないゲームです)

【コメント】
一見探索領域が広くてメモ化もできなくて難しそうですが、実質的に選べる手が高々 2 通りしかないタイプのゲームです。

例題 4-2-4　Nim

【キーワード】

  • ゲーム
  • Nim

【AtCoder 上の類題】

【コメント】
すごく有名な問題 Nim です。なお最後に石を取ると負けとしたバージョンを Misere Nim と呼ぶようです。

  • Nim (sigma さん)

例題 4-2-5　Georgia and Bob (POJ No.1704)

【キーワード】

  • Nim
  • 時々見るタイプの Nim

【AtCoder 上の類題】

【コメント】
時々このタイプの Nim を見る気がします。類題として挙げた 2 題はどちらも見た目は大分違いますが本質的には Georgia and Bob と同型な問題です。

例題 4-2-6　コインのゲーム２

【キーワード】

  • ゲーム
  • Nim
  • Grundy 数

【AtCoder 上の類題】

【コメント】
複数盤面を同時に処理するゲームに使える一般的なテク Grundy です！

例題 4-2-7　Cutting Game (POJ No.2311)

【キーワード】

  • ゲーム
  • Nim
  • Grundy 数
  • 分裂のある Grundy 数

【AtCoder 上の類題】

【コメント】
Grundy 数は盤面の分裂がある場合に真価を発揮するイメージです！

ゲーム全般の問題集です。またゲーム系問題への入門として、HackerRank によい教材があるようです:

4-3 グラフマスターへの道

例題 4-3-1　Popular Cows (POJ No.2186)

【キーワード】

  • 強連結成分分解

【AtCoder 上の類題】

【コメント】
有向グラフに強連結成分分解を行い、強連結成分を 1 点につぶすと DAG になります。DAG 上で DP したりなど、色んな問題が出題されます。

例題 4-3-2　Priest John's Busiest Day (POJ No.3683)

【キーワード】

  • 強連結成分分解
  • 2-SAT

【AtCoder 上の類題】

【コメント】
強連結成分分解を用いる典型例として 2-SAT があります。2-SAT 制約は Project Selection Problem (燃やす埋める) とも相性がよいです。

参考記事:

例題 4-3-3　Housewife Wind (POJ No.2763)

【キーワード】

  • ツリー上のクエリ
  • LCA
  • Euler Tour
  • ダブリング

【AtCoder 上の類題】

【コメント】
ツリー上のクエリに関する問題です。典型的にはダブリング、オイラーツアーから、少しよく見るものに HL 分解などがあります。

参考記事:

4-4 厳選！頻出テクニック (2)

例題 4-4-1　Largest Rectangle in a Histogram (POJ No.2559)

【キーワード】

  • ヒストグラム長方形面積最大化
  • stack

【AtCoder 上の類題】

【コメント】
ナイーブにやると O(n^2) かかる処理を stack を用いて O(n) で済ませるテクニックです。類似の話題として最大正方形の面積 - 正方形探索もあります。他に stack を用いて実施できる典型的な問題として括弧列に関する問題があります。

例題 4-4-2　スライド最小値

【キーワード】

  • スライド最小値
  • deque

【AtCoder 上の類題】

【コメント】
DP の高速化テクニックとしてよく見るスライド最小値技法です。スライド最小値そのものの問題は見つからなかったですが、ここでは deque が使えそうな問題を挙げます。

例題 4-4-3　個数制約付きナップサック

【キーワード】

  • DP
  • deque
  • スライド最小値を用いた DP 高速化

【AtCoder 上の類題】

【コメント】
DP 高速化技法としてよく見られる手法の 1 つ、スライド最小値 (他に累積和, インライン DP, Convex Hull Trick など) です。多くの場合、segtree を用いた高速化もできますが、スライド最小値が決まると segtree 高速化よりも計算量オーダーを落とせます。

例題 4-4-4　K-Anonymous Sequence (POJ No.3709)

【キーワード】

  • DP
  • Convex Hull Trick を用いた DP 高速化

【AtCoder 上の類題】

【コメント】
DP 高速化技法としてよく見られる手法の 1 つ、Convex Hull Trick です。
DP 高速化関連記事:

例題 4-4-5　巡回スケジューリング

【キーワード】

  • ダブリング

【AtCoder 上の類題】

【コメント】
べき乗法、行列累乗、LCA などでもおなじみのダブリングを用いた DP です。
参考記事:

4-5 工夫を凝らして賢く探索

例題 4-5-1　数独 (POJ 2676, 2918, 3074, 3076)

【キーワード】

  • 探索
  • 探索順序を工夫する
  • バックトラック

【AtCoder 上の類題】

【コメント】
基本的には DFS などによる全探索ですが、全探索方法があまり自明でないタイプの問題です。DFS ではしばしば「前の状態に戻す」といことをするので、そこをいかに高速に実現するかが大事になることもあります (そこを強く意識した DFS をバックトラックと言います)。

例題 4-5-2　Sequence Destroyer (POJ No.1084)

【キーワード】

  • 探索
  • 枝刈り探索
  • 解が悪くなったら打ち切る
  • 分枝限定法やα-β法的な枝刈り探索

【AtCoder 上の類題】

【コメント】
分枝限定法やα-β法に代表されるような、「解が悪くなったら打ち切る」系の枝刈り探索をする問題です。計算量オーダーが不明になることが多く出題側も苦心しそうなタイプの問題です。ここではもっと広く枝刈り探索に関する問題を載せました。
参考記事:

例題 3-5-3　AとIDA

【キーワード】

  • A*とIDA*

【AtCoder 上の類題】

【コメント】
A* や IDA* によって DFS や BFS を高速化します。

4-6 分けて解いてまとめる！ "分割統治法"

例題 4-6-1　バブルソートの交換回数

【キーワード】

  • 分割統治法

【AtCoder 上の類題】

【コメント】
なんとなく Segtree を使ってもできることが多そうなイメージもある分割統治法です。

例題 4-6-2　Tree (POJ No.1741)

【キーワード】

  • 分割統治法
  • ツリーの重心
  • ツリーの重心分解

【AtCoder 上の類題】

【コメント】
ツリーの重心分解を用いたツリー上の分割統治法です。データ構造をマージする一般的なテクで解けるケースも多いイメージがあります。また、ツリーの重心の数学的性質を活用するタイプの問題も挙げました。
参考記事:

例題 4-6-3　最近点対問題 (Uva 10245)

【キーワード】

  • 分割統治法
  • 平面の分割統治法
  • 最近点対問題

【AtCoder 上の類題】

【コメント】
最近点対問題です。

4-7 文字列を華麗に扱う

例題 4-7-1　禁止文字列　＜募集中！！！＞

【キーワード】

  • 文字列 DP

【AtCoder 上の類題】

【コメント】
Trie DP の前振りです。ごく自然な DP で解くことができます。競プロの問題としては、通常は複数文字列を禁止パターンとして Trie DP の形で出すものと思われるため、類題はあまり見つからなかったです。AtCoder 上の問題を募集中です。

例題 4-7-2　DNA Repair (POJ No.3691)

【キーワード】

  • 文字列 DP
  • Trie 木

【AtCoder 上の類題】

【コメント】
例題 4-7-1 から少し発展して Trie 木を構築するタイプの問題です。

例題 4-7-3　星座 (POJ No.3690)

【キーワード】

  • 文字列検索
  • ローリングハッシュ
  • KMP 法
  • Aho-Corasick 法

【AtCoder 上の類題】

【コメント】
文字列検索関連です。

例題 4-7-4　Sequence (POJ No.3581)

【キーワード】

  • Suffix Array

【AtCoder 上の類題】

【コメント】
Suffix Array です。Suffix Array を求めるアルゴリズムは様々なものが提案されており、特に O(n) で求められる SA-IS は理論上も実際上も高速です。

例題 4-7-5　共通部分文字列(POJ No.2217)

【キーワード】

  • Suffix Array
  • LCP (高さ配列)

【AtCoder 上の類題】

【コメント】
Suffix Array とセットになって使われることの多い LCP です。

例題 4-7-6　最長回文

【キーワード】

  • Suffix Array
  • LCP
  • 回文

【AtCoder 上の類題】

【コメント】
LCP にさらに RMQ を用いると文字列の場所 i, j の接尾辞の先頭何文字が共通しているかを求めることができます。最長回文はそのような LCP 処理を用いる典型的な例です。

文字列全般の問題集です:

4-8 GCJ の問題に挑戦してみよう (3)

各 GCJ の問題たちのキーワードを挙げていきます。この中でも 4-8-5 は一時期流行したテクニックを用いるので類題を挙げます。

例題 4-8-1　Mine Layer (2008 World Final C)

【キーワード】

  • 端から決まる Greedy

【AtCoder 上の類題】

【コメント】
最適化問題の顔をしていますが、実は一意に決まってしまう問題です。

例題 4-8-2　Year of More Code Jam (2009 World Final A)

【キーワード】

  • 期待値
  • 期待値の線形性

【AtCoder 上の類題】

【コメント】
期待値の式変形をひたすら頑張る問題です。

例題 4-8-3　Football Team (2009 Round 3 C)

【キーワード】

  • グラフ
  • 彩色数
  • 二部グラフ判定
  • 平面グラフ
  • 四色定理
  • 三彩色問題

【AtCoder 上の類題】

【コメント】
グラフの彩色に関する問題です。

例題 4-8-4　Endless Knight (2008 Round3 D)

【キーワード】

  • 数え上げ
  • 包除原理
  • 包除原理 + DP

【AtCoder 上の類題】

【コメント】
包除原理を用いる例題です。今の時代となっては比較的典型の部類に入りそうです。

例題 4-8-5　The Year of Code Jam (2008 World Final E)

【キーワード】

  • フロー
  • 最小カット
  • Project Selection Problem (燃やす埋める)
  • 半分だけ変数変換して「燃やす埋める」が使える形にするテク

【AtCoder 上の類題】

【コメント】
蟻本のラストを飾る問題です！！！
GCJ 2008 World Final で最も正答者数の少なかった難問ですが、この問題が世に知れ渡って以降、典型テクニックとして理解されるようになりました。

謝辞

蟻本の例題たちを AtCoder の問題に結び付け、さらに類題を加える試みをしてみました。
本記事を執筆するにあたり、たくさんの方に支えていただきました。本記事の企画に賛同していただいた秋葉さん、これほどまでに素敵な蟻本を執筆してくださった iwi さん、wata さん、kita_masa さん、問題案などを提供していただいた yumechi さん、はむこさん、ヘクトさん、きゅうりさん、とこはるさん、くぬーさん、くちもちとくらさん、kirika さん、n_vip さん、E869120 さん、square10011 さん、nadare さん、リンク切れなどのミスを指摘してくれた Moko さん、くちもちとくらさん、好意的なコメントを寄せていただいた TL の皆さん、いつも楽しいコンテストを開催してくださっている AtCoder 社の方々、読んでいただいている読者の皆さん、そして競技プログラミングに関わるすべての方々への感謝の想いでいっぱいです。今後ますますの競技プログラミング界の発展を願って、むすびの言葉とさせていただきます (まだまだ随時更新します)。

Edit request
40
  • 4-3 グラフマスターへの道
  • 4-4 厳選！頻出テクニック (2)
  • 4-5 工夫を凝らして賢く探索
  • 4-6 分けて解いてまとめる！ "分割統治法"
  • 4-7 文字列を華麗に扱う
  • 4-8 GCJ の問題に挑戦してみよう (3)
  • 謝辞
    • Sign in to continue the action.
    Sign in with EmailSign in with TwitterSign in with GitHubSign in with Google
    or