Go to Qiita Advent Calendar 2024 Top
LoginSignup
2703
2622

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@drken(けんちょん (Otsuki))in株式会社NTTデータ数理システム

AtCoder 版！蟻本 (初級編)

Last updated at Posted at 2018-02-20

0 はじめに

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

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

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

【注意】

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

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

【シリーズ】

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

初級編は全体的に、ABC C 問題 (300 点) 相当の難易度の問題が多いです。一番最初に挙げたダーツはかなり難しい (400 点相当) ので、本記事の最後に挑むのも良さそうです。

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

####例題 1-1-1　(ハードルの上がった) くじびき ＜難問！！！！！＞
【キーワード】

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

【AtCoder 上の類題】

【コメント】
蟻本 1-6 に再掲されているハードルの上がったバージョンです。いきなり解くのは難しいかもしれません。ABC や ARC で出題するなら 400 点相当だと思います。まずは 2-1 章や 2-2 章の比較的易しめの問題を練習して再び挑むのがよさそうです。AtCoder を始めた方が最初に目指す登竜門としてとてもよい問題と言えるでしょう。この問題が自然に解けるようになった頃には大分強くなった実感が湧くと思います！

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

####例題 1-6-1　三角形
【キーワード】

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

【AtCoder 上の類題】

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

  • 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 上の類題】

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

####例題 2-1-2　Lake Counting (POJ No.2386)
【キーワード】

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

【AtCoder 上の類題】

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

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

####例題 2-1-3　迷路の最短路
【キーワード】

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

【AtCoder 上の類題】

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

####例題 2-1-4　特殊な状態の列挙
【キーワード】

  • n! 通りの全探索
  • next_permutation

【AtCoder 上の類題】

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

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

####例題 2-2-1　硬貨の問題
【キーワード】

  • Greedy
  • コイン

【AtCoder 上の類題】

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

####例題 2-2-2　区間スケジューリング問題
【キーワード】

【AtCoder 上の類題】

【コメント】
区間の終端 (または始端) でソートするのは極めてよくみるテクニックで、今後難しい問題に挑むときにも常に念頭に置いておきたいです。

####例題 2-2-3　Best Cow Line (POJ No.3617)
【キーワード】

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

【AtCoder 上の類題】

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

####例題 2-2-4　Saruman's Army (POJ No.3069)
【キーワード】

  • Greedy
  • より厳しいところをとっていく Greedy (より一般に「交換しても悪化しない」)

【AtCoder 上の類題】

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

####例題 2-2-5　Fence Repair (POJ No.3253)
【キーワード】

  • Greedy
  • priority_queue
  • ハフマン符号
  • 二分木

【AtCoder 上の類題】

【コメント】
ハフマン符号を求める Greedy、priority_queue も用います。
Codeforces の問題ですが、なんとか近いものがありました！

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

####例題 2-3-1　01ナップサック問題
【キーワード】

  • DP
  • ナップサック DP

【AtCoder 上の類題】

【コメント】
ナップサックな DP については記事を書いてみました。DP を漸化式だととらえる立場からの入門記事です。DP を全探索の効率化から入る立場の入門資料として「プログラミングコンテストにおける動的計画法」がとてもよいです。漸化式派と全探索メモ化派は、強い人たちの間でも二分されているので肌の合う考え方で入門していくのがいいと思います。

桁 DP について参考記事:

####例題 2-3-2　最長共通部分列問題
【キーワード】

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

【AtCoder 上の類題】

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

####例題 2-3-3　個数制限なしナップサック問題
【キーワード】

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

【AtCoder 上の類題】

【コメント】
各品物を何個でも選んでよいバージョンのナップサックです。愚直にやると計算量が $O(nW^2)$ かかってしまうところをうまくやって $O(nW)$ に落とすテクニックです。配列再利用と呼ばれる DP 時のメモリ消費を抑えるテクニックとも相性がいいです。忘れた頃に見かけるイメージです。

####例題 2-3-4　01ナップサック問題その２
【キーワード】

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

【AtCoder 上の類題】

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

####例題 2-3-5　個数制限付き部分和問題
【キーワード】

  • DP
  • ナップサック DP
  • DP の値に bool 値より多くの情報を持たせる
  • DP の値に復元のための情報を持たせる
  • (少し発展すると) 戻す DP

【AtCoder 上の類題】

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

戻す DP について参考記事:

####例題 2-3-6　最長増加部分列問題
【キーワード】

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

【AtCoder 上の類題】

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

参考記事:
競技プログラミングにおける最長部分増加列問題まとめ (はまやんさん)

####例題 2-3-7　分割数
【キーワード】

  • DP
  • 分割数

【AtCoder 上の類題】

【コメント】
時々高難易度な問題で部分的に登場する分割数です。同じように高難易度な問題で登場する話題に、スターリング数やベル数があります。

参考記事:

####例題 2-3-8　重複組合せ
【キーワード】

  • DP
  • 重複組み合わせ

【AtCoder 上の類題】

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

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

　

だいたい、TDPC です。

####例題 2-3-9　ゲーム DP
【キーワード】

  • DP
  • ゲーム DP

【AtCoder 上の類題】

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

####例題 2-3-10　区間 DP
【キーワード】

  • DP
  • 区間 DP

【AtCoder 上の類題】

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

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

参考記事:
競技プログラミングにおける区間DP問題まとめ (はまやんさん)

####例題 2-3-11　ツリー DP
【キーワード】

  • DP
  • ツリー DP

【AtCoder 上の類題】

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

参考記事:
競技プログラミングにおける木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 上の類題】

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

DEGwer さんの数え上げテクニック集の「3.1 大きい順に並べる」にも類似の記載があります。

余談ですが「ソートしてナップサック」をかなり一般的なフレームワークに乗せた論文がアルゴリズム系の国際会議 ISSAC 2016 の Best Paper Award に選ばれています！

####例題 2-3-15　部分文字列 DP
【キーワード】

  • DP
  • 部分文字列 DP

【AtCoder 上の類題】

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

参考記事:
部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集

####例題 2-3-16　挿入 DP
【キーワード】

  • DP
  • 挿入 DP

【AtCoder 上の類題】

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

DEGwer さんの数え上げテクニック集の「3.2 順列は挿入 DP」に挿入 DP がどういうときに有効かの説明が書いてあります。

参考記事:
競技プログラミングにおける挿入DP問題まとめ (はまやんさん)

####例題 2-3-17　連結性 DP
【キーワード】

  • DP
  • 連結性 DP

【AtCoder 上の類題】

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

参考記事:
競技プログラミングにおける連結DP問題まとめ (はまやんさん)

####例題 2-3-18　きたまさ法
【キーワード】

  • DP
  • きたまさ法

【AtCoder 上の類題】

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

DP のその他参考資料

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

####例題 2-4-1　Expedition (POJ No.2431)
【キーワード】

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

【AtCoder 上の類題】

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

####例題 2-4-2　二分探索木 (set, map の練習)
【キーワード】

  • set, map

【AtCoder 上の類題】

【コメント】
ABC C 問題を解けるようにしていく上で set や map を使えるようになることも重要なステップだと思います。

####例題 2-4-3　食物連鎖 (POJ No.1182)
【キーワード】

  • Union-Find 木
  • ノードコピーして考える

【AtCoder 上の類題】

【コメント】
Union-Find 木はちょくちょく出てくるデータ構造です。蟻本の例題はとてもよい問題ではあるのですが、中国語の問題というのが大分辛いですね...。発展的話題として、重み付き Union-Find 木や、永続 Union-Find 木があります。

参考記事:
競技プログラミングにおけるUnionFind問題まとめ (はまやんさん)

2-5 あれもこれも実は "グラフ"

####例題 2-5-1　二部グラフ判定
【キーワード】

  • DFS
  • 二部グラフ
  • 二部グラフ判定 (2色彩色)

【AtCoder 上の類題】

【コメント】
いずれも「二部グラフ ⇔ 奇数長サイクルを含まない」を活用する問題ですね。

####例題 2-5-2　Roadblocks (POJ No.3255)
【キーワード】

  • 最短路問題
  • Dijkstra のアルゴリズム

【AtCoder 上の類題】

【コメント】
お馴染みの Dijkstra 法です！
意外と純粋な Dijkstra な問題はなかなかないですね... AOJ には多数あるのですが...

####例題 2-5-3　Conscription (POJ No.3723)
【キーワード】

  • 最小全域木問題
  • Kruskal のアルゴリズム

【AtCoder 上の類題】

【コメント】
最小全域木絡みは良問が多いですね！
調べれば調べるほど気分がよくなって、ついつい色んな問題を載せてしまいました。

参考記事:
様々な最小全域木 (前原さん): 面白いです！

####例題 2-5-4　Layout (POJ No.3169)
【キーワード】

  • 牛ゲー
  • 最短路問題
  • Bellman-Ford のアルゴリズム

【AtCoder 上の類題】

【コメント】
出ました！！！！！いわゆる牛ゲーです！！！！
蟻本初級編で最も難しいと呼び声の高い牛ゲーです！！！
ちなみに牛ゲーの名前の由来がまさにこの POJ の例題に牛が登場するからです。

参考記事:
競技プログラミングにおけるベルマンフォード問題まとめ (はまやんさん)

####例題 2-5-5　Warshall-Floyd を使う問題
【キーワード】

  • 全頂点間最短路
  • Warshall-Floyd のアルゴリズム

【AtCoder 上の類題】

【コメント】
蟻本には例題がないですが需要はありそうなので、Warshall-Floyd のアルゴリズムが使える問題を挙げました。

2-6 数学的な問題を解くコツ

####例題 2-6-1　線分上の格子点の個数
【キーワード】

  • 最大公約数
  • Euclid の互除法

【AtCoder 上の類題】

【コメント】
ユークリッドの互除法自体は頻出ですが、「線分上の格子点の個数」が最大公約数を求めることで求められるというのは、少し理解が難しいかもしれません。

####例題 2-6-2　双六
【キーワード】

  • 拡張 Euclid の互除法

【AtCoder 上の類題】

【コメント】
AtCoder 上のピッタリな問題は見つけられなかったです。募集中です。
とりあえず拡張 Euclid の互除法を確かめようとなったら、mod_inverse を拡張 Euclid 互除法によって実装してみて、mod_inverse が登場する問題を解くのがよさそうです。

####例題 2-6-3　素数判定
【キーワード】

  • 素数
  • 素数判定
  • 素因数分解

【AtCoder 上の類題】

【コメント】
おなじみの素数判定 & 素因数分解です。

####例題 2-6-4　素数の個数
【キーワード】

  • 素数
  • Eratosthenes の篩

【AtCoder 上の類題】

【コメント】
そすーそすー
Eratosthenes の篩です。
Eratosthenes の篩的な前処理をしたあとに「素因数分解」を高速に実行する osa_k 法も。

####例題 2-6-5　区間内の素数の個数
【キーワード】

  • 素数
  • Eratosthenes の篩
  • Eratosthenes の区間篩

【AtCoder 上の類題】

【コメント】
日本語の区間篩のジャッジが存在しなかったため、アルゴ式でジャッジを作りました。

####例題 2-6-6　Carmichael Numbers (Uva No.10006)
【キーワード】

  • べき
  • 繰り返し二乗法
  • ダブリング
  • Fermat の小定理
  • カーマイケル数 (擬素数)

【AtCoder 上の類題】

【コメント】
カーマイケル数大好きです！！！！！！
最後の問題の原案を担当していましたが、元ネタはカーマイケル数です。

参考記事:

-1 おわりに

蟻本の例題たちを AtCoder の問題に結び付け、さらに類題を加える試みをしてみました。改良案をドンドン募集しています！

2703
2622
24

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2703
2622

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?