Edited at 2018-02-20

AtCoder 版！蟻本 (初級編)

0 はじめに

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

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

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

【注意】

本記事の趣旨からしてどうしてもネタバレ問題は生じてしまいますので、それについては了承いただければと思います。
今後随時更新していきますので、各問題の解説などの参考記事やよりよい問題案などの意見をガンガン募集しています。
各アルゴリズムを用いる AtCoder の問題を収集する試みもなされています。相補的に活動できたらいいなと思います。アルゴリズムから問題を探す

【シリーズ】

1 いざチャレンジ！でもその前に --- 準備編

1-1 プログラミングコンテストって何？

例題 1-1-1　(ハードルの上がった) くじびき

【キーワード】

全探索 (4 重の for 文) だと間に合わない
半分全列挙

【AtCoder 上の類題】

第７回日本情報オリンピック本選（オンライン）C ダーツ　(ほぼ同じ問題です)

【コメント】
蟻本 1-6 に再掲されているハードルの上がったバージョンです。いきなり解くのは難しいかもしれません。AOJ 0529 にも同じ問題があります。srupのメモ帳 AOJ 0529 Darts に詳しい解説があります。

1-6 気楽にウォーミングアップ

例題 1-6-1　三角形

【キーワード】

全探索 (三重の for 文)
三角形の成立条件

【AtCoder 上の類題】

ARC 004 A 2点間距離の最大値 ( The longest distance )　(全探索部分の考え方は一緒)
ABC 085 C Otoshidama　(三重の for 文では少し厳しく工夫が必要です)
AOJ 0582 Triangle Types　(三角形パートは共通点あり)

【コメント】
競技プログラミングにおけるすべての基本 全探索 です。全探索といっても

for 文を二重三重にして回す
bit 全探索
DFS
BFS

とステップがありますが、これは最も基本的な for 文型の全探索です。ここを抑えるだけでも、ABC の C 問題の打率 3 割までは達成できると思います。

例題 1-6-2　Ants (POJ No.1852)

【キーワード】

発想力
弾性衝突

【AtCoder 上の類題】

AGC 013 C Ants on a Circle　(蟻のオマージュにして類似の発想をする問題です...が、ものすごく難しいのでここから下の問題たちをやって実力をつけてから挑むのがよさそうです, はむこさん提供)

【コメント】
言わずと知れた蟻本冒頭の感動的問題です！
一節によると、これが蟻本の名前の由来だという説もあります。

2 基礎からスタート！ --- 初級編

2-1 すべての基本 "全探索"

例題 2-1-1　部分和問題

【キーワード】

$2^{n}$ 通りを調べる全探索 (bit 全探索)

【AtCoder 上の類題】

ABC 045 C たくさんの数式 / Many Formulas　(同じく $2^{n}$ 通りを調べる全探索)
ABC 079 C Train Ticket
ARC 029 A 高橋君とお肉
ABC 002 D 派閥　(全探索部分の考え方は共通)

【コメント】
通称 bit 全探索と呼ばれているタイプの全探索です。蟻本のように再帰関数の形で書くこともできますし、ビットで集合を管理する手法で全探索することもできます。

例題 2-1-2　Lake Counting (POJ No.2386)

【キーワード】

DFS
(弱) 連結成分分解
グリッドグラフ上の探索

【AtCoder 上の類題】

ATC 001 A 深さ優先探索　(かなり似ています, yumechiさん提供)
ARC 031 B 埋め立て　(比較的似ています、yumechiさん提供)
ARC 037 B バウムテスト　(見た目は違いますが実装するアルゴリズムは似ています)
AOJ 1160 島はいくつある？　(ほぼまったくそのままな問題です)

【コメント】
初めて Lake Counting を見たときはとても難しそうに思えましたが、今となってはパターン化した DFS の実装で簡単に記述できます。このタイプの DFS をスラスラと書けるようになることが、競技プログラミングの重要なステップになると思います。

また、ARC 037 B バウムテストは Lake Counting とは見た目は違いますがやることはすごく似ています。こういうのを同じ問題だと思えるようになることもまた、重要なステップかと思います。

例題 2-1-3　迷路の最短路

【キーワード】

BFS
BFS を用いる最短路問題
グリッド上の探索

【AtCoder 上の類題】

ABC 007 C 幅優先探索　(まんまです)
第１０回日本情報オリンピック予選（オンライン）E - チーズ (Cheese)
ARC 031 B 埋め立て　(DFS にも入れましたが BFS で解いてもよいです、yumechiさん提供)
ARC 005 C - 器物損壊！高橋君 ( Search and destroy )　(少し発展して、0-1 BFS と呼ばれているものです)
AOJ 0503 Cup　(BFS はパズル的な問題の最短手数を求めるのにも有効です)

【コメント】
こちらも超典型テクなので身に着けることがとても重要そうです。

例題 2-1-4　特殊な状態の列挙

【キーワード】

n! 通りの全探索
next_permutation

【AtCoder 上の類題】

【コメント】
小さな n でしか適用できないので難しい問題になると逆に見かけないですが、n! 通りの全探索ができることも重要なステップになります。n が少し大きくなると bit DP が想定解法であるケースが多いです。

2-2 猪突猛進！ "貪欲法"

例題 2-2-1　硬貨の問題

【キーワード】

Greedy
コイン

【AtCoder 上の類題】

第７回日本情報オリンピック予選（オンライン） A おつり　(ほぼまんまな問題です)
AOJ Course コイン問題　(より一般的なコイン問題、おそらく Greedy は通らないです)

【コメント】
硬貨の問題が Greedy で良いことは、そんなに自明じゃないようです。

例題 2-2-2　区間スケジューリング問題　＜募集中！！！＞

【キーワード】

Greedy
区間の終端でソート (DEGwer さんの数え上げ pdf にも記載あり)

【AtCoder 上の類題】

Codeforces 296 DIV1 B Clique Problem　(少し難しめ、区間スケジューリング問題に帰着)
ABC 038 D プレゼント　(難しめです、区間ソートして LIS に帰着)

【コメント】
なかなかピッタリな問題が見つからず、Codeforces の問題を挙げる苦肉の策をとりました。やや難しめですが区間スケジューリング問題に帰着できます。
区間の終端 (または始端) でソートするのは極めてよくみるテクニックで、今後難しい問題に挑むときにも常に念頭に置いておきたいです。

例題 2-2-3　Best Cow Line (POJ No.3617)

【キーワード】

Greedy
辞書順最小なものを求める Greedy

【AtCoder 上の類題】

ABC 076 C Dubious Document 2　(辞書順最小 Greedy の練習です)
ABC 007 B 辞書式順序　(そもそも辞書次式順序とはなにか)
ABC 009 C 辞書式順序ふたたび　(かなり難しいです)

【コメント】
辞書順最小なものを求めよと言われたときにとにかく先頭から順に最小になることを優先していく考え方は超頻出ですね。

例題 2-2-4　Saruman's Army (POJ No.3069)

【キーワード】

Greedy
より厳しいところをとっていく Greedy (適切な表現を大募集！)

【AtCoder 上の類題】

ABC 083 C Multiple Gift　(例題はなるべく遠い方を選ぶ Greedy でしたが、これは近い方を選ぶ Greedy です)
ABC 048 C Boxes and Candies　(発想は似ています)
ABC 006 C 積み重ね　(典型問題です)
SRM 560 DIV1 Easy TomekPhone　(一次元量同士を比較する最大二部マッチング)
SRM 549 DIV1 Easy PointyWizardHats　(二次元量同士を比較する最大二部マッチング)

【コメント】
Greedy アルゴリズムを考えるときに、より厳しいところをとっていく考え方は頻出のイメージです。その最も典型的な例として、一次元的 (二次元量もOK) な数量の大小関係だけでマッチング条件が決まるような問題における最大二部マッチング問題があります。

例題 2-2-5　Fence Repair (POJ No.3253)　＜募集中！！！！！＞

【キーワード】

Greedy
priority_queue
ハフマン符号
二分木

【AtCoder 上の類題】

大募集

【コメント】
ハフマン符号を求める Greedy、priority_queue も用います。

2-3 値を覚えて再利用 "動的計画法"

例題 2-3-1　01ナップサック問題

【キーワード】

DP
ナップサック DP

【AtCoder 上の類題】

AOJ Course 0-1ナップザック問題　(まんまです)
TDPC A コンテスト　(部分和問題です)
TDPC D サイコロ　(添字増やす系のナップサックです)
第１２回日本情報オリンピック予選（オンライン） D 暑い日々 (Hot days)
TDPC E 数　(いわゆる桁 DP です。桁 DP もナップサックの一種で、bit DP とは完全に別物です)

【コメント】
ナップサックな DP については記事を書いてみました。DP を漸化式だととらえる立場からの入門記事です。DP を全探索の効率化から入る立場の入門資料としては「プログラミングコンテストにおける動的計画法」がとてもよいです。

例題 2-3-2　最長共通部分列問題

【キーワード】

DP
LCS
二次元ナップサック DP

【AtCoder 上の類題】

【コメント】
系列に沿って進んでいく index が 2 つになったバージョンのナップサック型 DP です。

例題 2-3-3　個数制限なしナップサック問題　＜募集中！！！＞

【キーワード】

DP
ナップサック DP
個数制限なしナップサック DP

【AtCoder 上の類題】

AOJ Course ナップザック問題
AOJ 2502 VOCAL ANDROID
SRM 459 DIV1 Medium NumberPyramids

【コメント】
各品物を何個でも選んでよいバージョンのナップサックです。愚直にやると計算量が $O (n W^{2})$ かかってしまうところをうまくやって $O (n W)$ に落とすテクニックです。忘れた頃に見かける系のテクニックなイメージです。AtCoder 上の問題は見つけられなかったので募集中です。

例題 2-3-4　01ナップサック問題その２

【キーワード】

DP
ナップサック DP
dp[W] := 重み W 以下での価値の最大値 -> dp[V] := 価値 V 以上を達成できる重さの最小値

【AtCoder 上の類題】

ABC 032 D ナップサック問題　(後に出て来る半分全列挙も含みます)
ARC 057 B 高橋君ゲーム

【コメント】
このテクニックも忘れた頃に見かけるイメージがあります。

例題 2-3-5　個数制限付き部分和問題

【キーワード】

DP
ナップサック DP
DP の値に復元のための情報を持たせる

【AtCoder 上の類題】

ARC 083 E Bichrome Tree　(難しめです)
第１３回日本情報オリンピック本選（オンライン） D フクロモモンガ（Sugar Glider）　(難しめです)
SRM 588 DIV1 Medium KeyDungeonDiv1

【コメント】
DP の値を単に bool 型にするのではなく、復元のための情報を持たせる系の問題です。その辺りのことは前記事に詳しく書いてみました。元々高度なテクニックなので問題例も難しめです。

例題 2-3-6　最長増加部分列問題

【キーワード】

DP
LIS
インライン DP (実家 DP)

【AtCoder 上の類題】

ABC 006 D トランプ挿入ソート
ABC 038 D プレゼント　(区間スケジューリング問題のところでも挙げました)
TDPC K - ターゲット
JOI春合宿2016 オンラインジャッジ A - マトリョーシカ人形　(難しいです。LIS ではないですが LIS の理解があると解きやすいです)

【コメント】
sky さんの提唱するインライン DP (通称、実家DP) の最も簡単な例で、なおかつ超頻出の LIS です。LIS に帰着できる問題は数多いのでライブラリとして持っておくだけでも強いですが、LIS の仕組みにより精通しているとより応用の効く問題もあります。

例題 2-3-7　分割数

【キーワード】

DP
分割数

【AtCoder 上の類題】

【コメント】
分割数についても記事を書いてみました。
分割数と、分割数が使える問題まとめ

例題 2-3-8　重複組み合わせ　＜募集中！！！＞

【キーワード】

DP
重複組み合わせ

【AtCoder 上の類題】

ABC 021 D 多重ループ　(きゅうりさん提供)
yukicoder No.250 atetubouのzetubou　(yumechiさん提供)

【コメント】
難しい問題の部分的なパートで登場するイメージのある重複組合せです。確かこのあり本の例題をさらに応用した問題があった気がするのですが、誰か知っているでしょうか...？？？

2-3-α その他典型としてあると思う動的計画法 (bit DP, Trie DP, Grundy DP, 行列累乗, 実家 DP, 連立方程式, Convex Hull Trick は中級編や上級編にあるので除きます)

例題 2-3-9　ゲーム DP

【キーワード】

DP
ゲーム DP

【AtCoder 上の類題】

【コメント】
ゲーム DP は蟻本上級編に載っているのですが、ゲーム DP (ゲーム木探索) だけなら初級編の段階で学んでもよさそうです。(TDPC は B で詰まるという声は多々聞くのでよい解説を見つけたいです)

例題 2-3-10　区間 DP

【キーワード】

DP
区間 DP

【AtCoder 上の類題】

TDPC I イゥイ
AOJ 2415 刺身　(Monge です)
ATC 002 C 最適二分探索木　(刺身と一緒ですが Monge してもなお足りず、Hu-Tucker が必要です)

【コメント】
区間に対する DP です。Monge 性は蟻本にない話題なのでどこかで学ぶ必要があります。通常の区間 DP は O(n^3) かかり、Monge 性を満たすと O(n^2) にすることができます。

最適二分探索木問題に限ってはさらに O(n logn) で解ける Hu-Tucker のアルゴリズムが知られています。

例題 2-3-11　ツリー DP

【キーワード】

DP
ツリー DP

【AtCoder 上の類題】

ABC 036 D 塗り絵
ABC 070 D Transit Tree Path
TDPC N 木　(少し難しめです)
TDPC P うなぎ　(ツリー二重 DP と呼んでいます。ノード v の値の更新自体に DP が必要なやつです。)
ARC 083 E Bichrome Tree　(ツリー二重 DP の他例です。例題 2-3-5 の類題にも挙げました。)

【コメント】
ツリー上の DP です。より高度な話題として、全方位木 DP があります。

例題 2-3-12　DAG DP

【キーワード】

DP
DAG DP

【AtCoder 上の類題】

【コメント】
ツリー DP を発展させて、一般的な DAG 上での DP です。ツリー DP とほぼ変わらない実装でできます。

例題 2-3-13　グリッド DP

【キーワード】

DP
グリッド DP

【AtCoder 上の類題】

【コメント】
DAG DP の一種ですが、特にグリッド上の DP です。JOI ではよく見るイメージです。
一般の DAG DP と異なり、メモ化再帰じゃなくても for 文でループを回す実装ができます。

例題 2-3-14　ソートしてからナップサック DP

【キーワード】

DP
ナップサック DP
先にソート

【AtCoder 上の類題】

第１１回日本情報オリンピック予選（オンライン） C 最高のピザ
第１０回日本情報オリンピック本選（オンライン） B 古本屋 (Books)
TDPC H ナップザック
2017 CODE FESTIVAL Final D Zabuton　(難しいですが、先にソートするんだろうな...と思えることが重要です。そう思えたらどうソートするかをひたすら考えます)
SRM 502 DIV1 Medium TheProgrammingContestDivOne　(SRM の問題ですが、個人的に良問だと思います。)

【コメント】
DP 部分はごく普通のナップサック DP ですが、一見すると順序も自由に入れ替えられるので困るタイプの DP です。こういったものは順番を先に fix できるケースが多いのでそれをどうしたらいいかをひたすら考察することになります。

例題 2-3-15　部分文字列 DP

【キーワード】

DP
部分文字列 DP

【AtCoder 上の類題】

ARC 081 E Don't Be a Subsequence　(難しいですが典型的な部分文字列 DP です)
TDPC G 辞書順　(典型的ではありますが、復元パートがかなり思いつきづらく難しいです)

【コメント】
特に名前がないので勝手に名付けました！
文字列の部分文字列全体を探索するような DP です。桁 DP と同様ちゃんと名前がつけば、もう少し解法が広まる気がします。

例題 2-3-16　挿入 DP

【キーワード】

DP
挿入 DP

【AtCoder 上の類題】

TDPC O 文字列

【コメント】
発想はナップサックに近いのですが、今ある並びの中に新しいものを挿入していく DP です。高難易度でお馴染みです。「bit DP でやりたくなるけど制約上とても無理で、部分点として bit DP が設定されている」というのがよくあるパターンです。

例題 2-3-17　連結性 DP

【キーワード】

DP
連結性 DP

【AtCoder 上の類題】

TDPC S マス目

【コメント】
超面倒な DP です。

例題 2-3-18　きたまさ法

【キーワード】

DP
きたまさ法

【AtCoder 上の類題】

TDPC T フィボナッチ

【コメント】
きたまさ法です。蟻本 P.182 のコラム「もっと高速な漸化式の計算」に「興味のある人は考えてみるといいでしょう」と書いてあるものです。

2-4 データを工夫して記憶する "データ構造"

例題 2-4-1　Expedition (POJ No.2431)

【キーワード】

priority_queue
「あとで補償する」という発想

【AtCoder 上の類題】

2017 CODE FESTIVAL THANKS C - Factory　(priority_queue を有効活用できる例です)
ABC 062 D - 3N Numbers　(priority_queue)
第９回日本情報オリンピック本選（オンライン） E - ダンジョン　(超高難易度問題ですが「あとで補償する」という発想は似ています)

【コメント】
「あとで補償する」という発想は高難易度な問題でよく見るイメージです。そして大体そういう問題はセグメントツリーや BIT を使って効率的に実行していくイメージがあります。蟻本の例題 Expedition はそういう問題にしては珍しく高度なデータ構造を必要としない問題だと言えます。