0. はじめに
からの続きです！！！
中級編から読む方へ
近年、AtCoder を中心とした競技プログラミング（競プロ）の存在感が日に日に高まってきています。近年では、AtCoderJobs という AtCoder での実力に応じて求人に応募できるサービスや、アルゴリズム実技検定という名の検定サービスも現れてきています。
そんな中、**「競プロでどうやって上達すれば良いのかわからない」**と思い悩んでいる方は多いと思います。その悩みも、実力帯ごとに異なり、
- 最初に何をやれば良いのか悩んでいる競プロ未経験者もいる
- 競プロ成績上位に食い込むためには何をやれば良いのか悩んでいる人もいる
- 部活や社内などで、どういう競プロの教え方をすれば良いのか悩んでいる人もいる
と思います。そこで本記事では、競技プログラミングで上達するためにはどういうことを学べば良いのか、どういう練習をすれば良いのかのガイドラインをレベル別に示し、上達に役立ててもらうことを最大の目標としております。
目次
初級編
| 章 | タイトル | 備考 |
|---|---|---|
| 0. | はじめに | |
| 1-1. | 競プロとは何か | ここからサポートしていきます |
| 1-2. | 競プロの 6 つの面白さ | 「競プロって、面白い」を伝えていきます |
| 1-3. | 早速競プロを始めてみよう | |
| 1-4. | AtCoder のレーティングとは | |
| 1-5. | 「茶色コーダー」で要求される 4 つのこと | |
| 1-6. | 「茶色コーダー」になるためのガイドライン | 初級編のメインです |
| 1-7. | Tips： AtCoder の過去問を解ける便利なサイト | |
| 1-8. | おまけ：競プロにおける C++ のすすめ |
中級編
| 章 | タイトル | 備考 |
|---|---|---|
| 2-1. | 「水色コーダー」で要求される 4 つのこと | |
| 2-2. | 「水色コーダー」になるためのガイドライン | 中級編のメインです |
| 2-3. | 分野別 初中級者が解くべき過去問精選 100 問 | この 100 問解けば実力上がると思います |
| 2-4. | 「水色コーダー」を目指す人のための Tips 5 個 |
上級編
| 章 | タイトル | 備考 |
|---|---|---|
| 3-1. | 「黄色コーダー」で要求される 6 つのこと | |
| 3-2. | 「黄色コーダー」になるためのガイドライン | 上級編のメインです |
| 3-3. | 分野別 上級者が解くべき過去問精選 100 + 50 問 | この 150 問で実力上がります |
| 3-4. | 「競プロ典型 90 問」のすすめ | 新たに誕生した教材です |
| 3-5. | 「黄色コーダー」を目指す人のための Tips 4 個 | |
| 4. | 「橙色コーダー」になるためには何をすれば良いか？ | 橙色までサポートします |
| 5. | 「橙色コーダー」の先 ～ガチンコ競技としての競プロのはじまり～ | |
| 6. | おわりに |
2-0. 中級編で紹介すること
中級編では、AtCoder で水色コーダーまで最速で上達する方法を記します。つまり、レーティング 1200 に最速で到達する方法を記します。
なお、AtCoder のレーティングは以下の表の通りです。水色コーダーは、全体の上位 1 割くらいです。1
| レーティング | 色 | 相対的な位置 | 絶対的な位置 |
|---|---|---|---|
| 2800+ | 赤 | 上位 0.2% | |
| 2400-2799 | 橙 | 上位 0.6% | |
| 2000-2399 | 黄 | 上位 2% | アルゴリズムの研究職・研究開発で重宝されるレベル |
| 1600-1999 | 青 | 上位 5% | ほとんどのIT企業でアルゴリズム能力がカンストする |
| 1200-1599 | 水 | 上位 10% | 半数以上のIT企業でアルゴリズム能力がカンストする |
| 800-1199 | 緑 | 上位 20% | エンジニアとしてかなり優秀 |
| 400-799 | 茶 | 上位 35% | 学生なら優秀 |
| 1-399 | 灰 | 上位 100% | |
| (2020/08/03 相対的な位置を修正 (更新) しました) | |||
| ※ 絶対的な位置に関しては AtCoder 社長・chokudai さんのブログ がソースです。 | |||
 |
2-1. 「水色コーダー」で要求される 4 つのこと
AtCoder で水色コーダー、つまりレーティング 1200 に到達するには、
- AtCoder Beginner Contest で確率 8 割以上で 4 問正解できる
- AtCoder Beginner Contest で確率 3-4 割で 5 問正解できる
- AtCoder Beginner Contest の問題をある程度早く解くことができる
- 目安は、A 問題 1 分、B 問題 4 分、C 問題 10 分、D 問題 25 分
ことが要求されます。そのためには、以下の 4 つのことができれば良いと考えます。（もちろん、茶色コーダーで要求される 4 つのこと は全てクリアしている必要があります。）
条件 1
標準ライブラリ（STL）を理解し、コンテストでもそれを使えるようになる。
ちなみに、C++ の場合、使えてほしい STL は以下の 25 個。
| abs | sin/cos/tan | string | min/max | swap |
| __gcd | rand | clock | reverse | sort |
| vector | stack | queue | priority_queue | map |
| lower_bound | set | pair | tuple | assert |
| count | find | next_permutation | __builtin_popcount | bitset |
条件 2
以下に書かれている、基本的なアルゴリズムとデータ構造を全て理解する。
アルゴリズム（12 個）
- 全探索（bit 全探索、順列全探索を含む）
- 二分探索
- 深さ優先探索（DFS）
- 幅優先探索（BFS）
- 動的計画法（bitDP などを含む）
- ダイクストラ法（最短経路問題）
- ワーシャルフロイド法（最短経路問題）
- クラスカル法（最小全域木問題）
- 高速な素数判定法
- べき乗を高速に計算するアルゴリズム
- 逆元を計算するアルゴリズム
- 累積和
データ構造（3 個）
- グラフ（グラフ理論）
- 木
- Union-Find
条件 3
条件 2 で紹介した基本的なアルゴリズムをコンテスト中に引き出し、それらを使えるようになる。
つまり、本記事で紹介する「基本アルゴリズム」が完全に身につく、ということ。
条件 4
15 行程度のプログラムであれば、ほぼバグらせずに書くことができる。
35 行程度のプログラムであれば、ある程度速く書くことができる。バグらせても、平均して 5 分以内でバグを解決できる。
※ 実際に、35 行程度のプログラムを、バグ取り含めて平均して 15 分で書けるようになれば、難しめの数学的考察が必要な問題が無い場合、AtCoder Beginner Contest で 4 問正解を 50 分以内で達成できることが多い。
補足
上の 4 つの条件を満たすようになれば、AtCoder Beginner Contest の D 問題までは 7 - 8 割解けるようになると思います。1 - 2 割は難しめの数学的考察が必要な問題が出題されますが、それを解かなくてもコーディングの速度と正確性を鍛えることによって、水色コーダーになることは十分可能です。
ちなみに、E 問題となれば数学的考察を必要とする問題も少し増えてきますが、典型アルゴリズムの活用で解ける問題が多いので、過去問を解いて演習量を増やせば、3 - 5 割くらいの確率で解けるようになっていくと思います。
さて、それらができるようになるためには、どのような練習をすれば良いのでしょうか。
2-2. 「水色コーダー」になるためのガイドライン
水色コーダーに到達するためにやるべきことは、以下の 5 つだと考えています。
- ステップ 1: 標準ライブラリを使えるようになる！
- ステップ 2: 12 個の基本アルゴリズムをマスターする！
- ステップ 3: 3 個の基本データ構造をマスターする！
- ステップ 4: 過去問を解きまくる！
- ステップ 5: バーチャルコンテストを活用して早解きを鍛える！
それぞれ、順番に説明していきたいと思います。
2-2-1. 標準ライブラリを使えるようになる！
競技プログラミングにおいて、標準ライブラリ（STL）はとても便利です。例えば C++ で問題を解く場合、AtCoder Beginner Contest の E 問題レベルでは 50% 程度の問題で、どこかしらの場面で標準ライブラリの機能が役立ちます。
ただし、全ての標準ライブラリを理解する必要がある訳ではありません。例えば C++ の場合、競プロで知っておきたい標準ライブラリは以下の 25 個に絞られます。
| abs | sin/cos/tan | string | min/max | swap |
| __gcd | rand | clock | reverse | sort |
| vector | stack | queue | priority_queue | map |
| lower_bound | set | pair | tuple | assert |
| count | find | next_permutation | __builtin_popcount | bitset |
そこで、標準ライブラリを使えるようになるために、読むべき記事が 2 つあります。（私が執筆した記事です）
記事を読んで、これらの記事に載っている問題例を解くと、標準ライブラリ（STL 機能）がマスターできると思います。
25 個の標準ライブラリの機能を理解する
標準ライブラリが競プロのどんな場面で使われるか理解する
2-2-2. 12 個の基本アルゴリズムをマスターする！
初級編でも述べた通り、競プロの本質は「実行時間制限に間に合う効率的なプログラムを考え、実装すること」です。その効率的なプログラムを実装することにおいて、典型的なアルゴリズムを知っていると非常にお得です。
しかし、水色コーダー、すなわちレーティング 1200 に到達するために理解する必要があるアルゴリズムは、僅か 12 個です。
| 全探索 | 二分探索 | 深さ優先探索 (DFS) | 幅優先探索 (BFS) |
| 動的計画法 (DP) | ダイクストラ法 | ワーシャルフロイド法 | クラスカル法 |
| 高速な素数判定法 | べき乗を高速に計算する手法 | 逆元を計算する手法 | 累積和 |
| ※ ダイクストラ法・ワーシャルフロイド法は最短経路問題を解くアルゴリズムです。 | |||
| ※ クラスカル法は最小全域木問題を解くアルゴリズムです。 |
それらのアルゴリズムが学習できる記事たちなどを紹介します。
全探索
全探索には、「全列挙」「ビット全探索」「順列全探索」「再帰関数を用いた全探索」など多くの種類に分かれます。しかし、基本的に以下の記事を読めば全部理解できます。
- 全列挙 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 2 章
- その他の全探索 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 3 章
二分探索
アルゴリズムの代表例ともいわれる二分探索は、以下の 2 記事で解説されています。
- 二分探索とは：アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より
- 競プロで使える二分探索：二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
【補足】二分探索に類似したアルゴリズムとして「二分法」があります。それについて詳しく知りたい方は以下の記事をお読みください。
深さ優先探索 (DFS)
競プロに使えるテクニックの一つです。以下の記事で解説されています。
幅優先探索 (BFS)
競プロで使えるテクニックの一つです。以下の記事で解説されています。
動的計画法 (DP)
以下の 3 つの種類の動的計画法（DP）が理解できれば、水色コーダーになるために求められる動的計画法の問題は大体解けます。
- ナップザック DP（部分和問題・最小共通部分列などは全てこれに含まれます）
- 区間 DP
- bit DP
それぞれの種類について、アルゴリズムは以下の記事で解説されています。
- ナップザック DP： 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
- 区間 DP： 区間 DP を勉強してみた - Kutimoti の競プロメモ
- bit DP： ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 の 11 章
ちなみに、茶色コーダー・緑コーダーには少し難しめですが、DP の教育的な問題がまとまったコンテストがあるので、過去問としてこれを最初の数問だけでも解くと良いと思います。（全部で 26 問あります）
- コンテスト： Educational DP Contest | AtCoder
- 解説記事： リンク
ダイクストラ法
$N$ 頂点 $M$ 辺のグラフにおける頂点 $1$ から各頂点への最短経路長を、$O(M \log{N})$ で計算するアルゴリズムです。詳しくは、以下の記事で解説されています。
ワーシャルフロイド法
$N$ 頂点 $M$ 辺のグラフにおける全頂点対間の最短経路長を、$O(N^3)$ で計算するアルゴリズムです。詳しくは、以下の記事で解説されています。
クラスカル法
以下の 2 記事で解説されています。
- アルゴリズム：最小全域木問題 (クラスカル法とプリム法)
- （参考）正当性の証明：Kruskal法をココロから納得する | けんちょんの競プロ精進記録
高速な素数判定法
$N$ が素数であるか $O(\sqrt{N})$ で計算する手法です。
単純に、$N$ を $2, 3, 4, 5, ..., \sqrt{N}$ で割って、どれでも割れなければ素数です、というアルゴリズムです。例えば、$37$ は $2, 3, 4, 5, 6$ のいずれでも割れないので素数です。
※ 正当性は、もし $N$ が素数でなくて $N = pq$ $(p \geq 2, q \geq 2)$ で表せるとすると、$p, q$ の少なくとも片方が $\sqrt{N}$ 以下だからです。両方 $\sqrt{N}$ を超えてしまうと、$pq > \sqrt{N} * \sqrt{N} = N$、よって $pq > N$ となってしまい、矛盾が生じます。
べき乗を高速に計算するアルゴリズム
$a^b$ を $m$ で割った余りが $O(\log{b})$ で計算するアルゴリズムです。以下の記事で解説されています。
逆元を高速に計算するアルゴリズム
$ax \equiv b \pmod{p}$ [$p$ は素数] となるような $x$ を $O(\log{p})$ で計算するアルゴリズムです。以下の記事で解説されています。
-
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 の 5 章
- $p = 1000000007$ の場合が書かれていますが、この記事に書かれている手法は一般の素数 mod にも応用が効きます。
累積和
競プロで使えるテクニックの一つです。以下の記事で解説されています。
また、累積和の亜種として、「いもす法」というアルゴリズムもあります。これも勉強しておくと良いです。
2-2-3. 3 個の基本データ構造をマスターする！
前節で述べた通り、競技プログラミングにはアルゴリズムを学ぶことが大切です。一方、データ構造を学ぶことも大事です。ちなみに、アルゴリズムとデータ構造を混同して覚える人が多いのですが、違いは以下のようになります。
- アルゴリズム：問題を解くための方法のこと。
- データ構造：データの集まりを一定の形式で系統立てて格納するときの形式。
さて、水色コーダーになるために必要なデータ構造は主に以下の 3 つです。
- グラフ
- 木
- Union-Find
それらのデータ構造が学習できる記事たちなどを紹介します。
グラフ
グラフとは、「頂点」と「辺」で構成されるデータ構造です。基礎知識は、以下の記事で解説されています。
木
木とは、$N$ 頂点 $N-1$ 辺の連結なグラフです。その特殊な性質ゆえに、競プロではよく問題にされます。（深さ優先探索などとセットで出されることが多いです）詳しくは、以下の記事をご覧ください。
Union-Find
競プロで頻出のデータ構造です。以下の記事で解説されています。
2-2-4. 過去問を解きまくる！
皆さん、アルゴリズムとデータ構造を理解した後に、重要となってくることは過去問を解くことです。水色コーダーになる辺りまでは、
競プロの実力 = アルゴリズムの理解度 × 競プロの演習量
だと考えることもできます。したがって、過去問を解くことはとても重要です。実際に、mencotton さんのツイート によると、800 問解けば 60% 、1100 問解けば 90% の人が水色コーダーになれます。（2020/01/17 時点の統計です）
一方で、**「解いた過去問の問題数 = 競プロの演習量」とは限りません。**私の考えとして、特に初中級者のうちは、「教育的な質の高い問題」と「それほど高くない問題」に分かれていると思っています。
そこで、少ない問題数でも「水色コーダー」を達成しやすいように、茶色コーダー・緑コーダーにとって教育的良問だと思った問題を合計 100 問選びました。
にまとめられていますので、基本的なアルゴリズムを学習した後は、この精選 100 問を解き、余力があれば AtCoder Problems などのサービスを利用してさらに過去問を解いていくことをお勧めします。
2-2-5. 早解きを鍛える！ ～バーチャルコンテストのすすめ～
競プロで戦う上で、難しい問題を解くことも重要ですが、簡単な問題を安定して早解きすることも重要です。実際に、AtCoder Beginner Contest 155 において、
- 3 完最上位のパフォーマンス：1430
- 3 完最下位のパフォーマンス：307
と、とても大きな差があります。さて、早解きを鍛えるには何をすれば良いのでしょうか。ここでお勧めなのが「バーチャルコンテスト」です。
便利なサイト「AtCoder Problems」によるバーチャルコンテスト
(2020/08/03 AtCoder Virtual Contest のサービス終了に伴い、修正しました)
を使うと、仮想的に自分でコンテストを好きな時間にやることができます。より具体的に書くと、AtCoder の過去問から何問か選んで、開始時間と終了時間を決めて、コンテスト形式で過去問を解けるという感じのサービスです。ちなみに、2 人以上の参加者と同時に戦うことができるのが面白い点の一つです。（以下のように、コンテストと同様順位表がリアルタイムで動きます）
サービスの利用方法
基本的に、GitHub のアカウントからログインする必要があります。AtCoder Problems のサイトを開くと、右上に「Login」と書かれているリンクが表示されると思います。これをクリックして、GitHub アカウントと連携することでログインしてください。
バーチャルコンテストに参加するためには、AtCoder Problems の右上の「Virtual Contest」というリンクをクリックして、バーチャルコンテストのページに移動してください。そうすると、下図のような画面が表示されると思います。
あとは、好きなバーチャルコンテストを選んで、それに参加してください。自分でバーチャルコンテストを作りたい場合は、「Create New Contest」 という緑色のボタンを押して、コンテスト設定フォームに進んでください。あとはフォームの通りに、コンテストタイトルや使う問題などを入力すると良いです。
バーチャルコンテストには、「Join」というボタンを押すことで参加できます。コンテスト時間中に AtCoder で該当する問題の提出をすることでバーチャルコンテストに参加でき、順位表も更新されます。
バーチャルコンテストの活用の仕方
このサービスを活用して、例えば以下のようなバーチャルコンテストを定期的に（例えば 1 週間に 2 回とか）やると、プログラムの実装を速くできる力が身につくと思います。
- AtCoder Beginner Contest から、A 問題 1 問・B 問題 2 問・C 問題 3 問の合計 6 問を集める。
- これを合計 30 分でできるだけ解く。
水色コーダーを目指す参加者にとっては、AtCoder Beginner Contest の A, B 問題なんかあまりにも簡単かもしれませんが、早解き力はそういう基本的なところで差が付きます。そのため、高難易度の練習だけでなく、低難易度を早解きする練習もした方が実力が伸びると考えられます。
2-3. 分野別 初中級者が解くべき過去問精選 100 問
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。
分野ごとに問題が分けられています。また、アルゴリズムの確認問題から応用問題まで幅広い層の問題がありますので、是非解いてみることをおすすめします。難しい問題もあるので、水色コーダーを目指す人は 100 問中 70 問正解を目安に頑張ってください。
100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います。そのため、既に水色コーダー以上であっても、100 問全部を解いていない場合は、解く価値が大きいと思います。
全探索：全列挙
1 ITP1_7_B - How Many Ways? 基本問題です。
2 AtCoder Beginner Contest 106 B - 105
3 AtCoder Beginner Contest 122 B - ATCoder
4 パ研杯2019 C - カラオケ これが解ければ全探索に慣れたと思って良いです。
全探索：工夫して通り数を減らす全列挙
5 AtCoder Beginner Contest 095 C - Half and Half
6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
7 JOI 2007 本選 3 - 最古の遺跡 面白いです。Python3 だと想定解法が TLE する可能性があります。
8 Square869120Contest #6 B - AtCoder Markets 全探索すると無数に通り数があるように見えますが、ひとつ工夫すると現実的な通り数で全列挙できる問題です。
9 JOI 2008 予選 4 - 星座探し
全探索：ビット全探索
10 ALDS_5_A - 総当たり 基本問題です。
11 AtCoder Beginner Contest 128 C - Switches
12 AtCoder Beginner Contest 002 D - 派閥
13 JOI 2008 予選 5 - おせんべい 茶色コーダーにはやや難問ですが解くことをおすすめします。
14 Square869120Contest #4 B - Buildings are Colorful! 工夫も必要で、一筋縄では解けない難問ですが、解けば確実に力がつきます。
全探索：順列全探索
15 AtCoder Beginner Contest 145 C - Average Length
16 AtCoder Beginner Contest 150 C - Count Order
17 ALDS_13_A - 8 クイーン問題 面白いです。
二分探索
18 ALDS_4_B - 二分探索 基本問題です。map でも解けますが二分探索で解いてみてください。
19 JOI 2009 本選 2 - ピザ
20 AtCoder Beginner Contest 077 C - Snuke Festival 面白いです。
21 AtCoder Beginner Contest 023 D - 射撃王 教育的に良いです。
22 AtCoder Regular Contest 054 B - ムーアの法則 微分して二分法をすると解けます。三分探索と話が繋がってくるので、それも調べてみると良いと思います。
23 JOI 2008 本選 3 - ダーツ 工夫して二分探索する、チャレンジ問題です。
深さ優先探索
24 ALDS_11_B - 深さ優先探索 基本問題です。
25 AOJ 1160 - 島はいくつある？ グラフの連結成分数は、深さ優先探索で計算できます。
26 AtCoder Beginner Contest 138 D - Ki 木構造の問題の多くは、深さ優先探索を使います。
27 JOI 2009 予選 4 - 薄氷渡り 深さ優先探索は、木構造だけではありません、ということを教えてくれる問題です。再帰関数を使って解けます。
幅優先探索
28 ALDS_11_C - 幅優先探索 基本問題です。
29 AtCoder Beginner Contest 007 C - 幅優先探索 重み無しグラフの最短経路問題は、幅優先探索で解けます。
30 JOI 2011 予選 5 - チーズ
31 JOI 2012 予選 5 - イルミネーション 少し実装が重いですが、頑張れば解けます。
32 AOJ 1166 - 迷図と命ず 実装が少し重いです。
33 AtCoder Beginner Contest 088 D - Grid Repainting これが解ければ、幅優先探索に慣れたと思って良いです。
動的計画法：ナップザック DP
34 ALDS_10_A - フィボナッチ数 超基本。「DP とは何か」を感じることができます。
35 DPL_1_B - 0,1ナップザック問題 基本問題です。
36 DPL_1_C - ナップザック問題 基本問題です。
37 DPL_1_A - コイン問題 基本問題です。
38 ALDS_10_C - 最長共通部分列 基本問題です。
(ここから先は、どのような DP で解けるのかは書きませんが、全部ナップザック DP またはその亜種で解くことができます。)
39 JOI 2011 予選 4 - 1 年生
40 JOI 2012 予選 4 - パスタ
41 JOI 2013 予選 4 - 暑い日々
42 JOI 2015 予選 4 - シルクロード
43 パ研杯2019 D - パ研軍旗
44 AOJ 1167 - ポロック予想
45 AOJ 2199 - 差分パルス符号変調
動的計画法：区間 DP
46 ALDS_10_B - 連鎖行列積 基本問題です。
47 JOI 2015 本選 2 - ケーキの切り分け 2 $O(N^2)$ の区間 DP です。
48 AOJ 1611 ダルマ落とし $O(N^3)$ の区間 DP です。
動的計画法：bit DP
49 DPL_2_A - 巡回セールスマン問題 基本問題です。
50 Square869120Contest #1 G - Revenge of Traveling Salesman Problem 巡回セールスマン問題を少し変えた問題です。
51 JOI 2014 予選 4 - 部活のスケジュール表 bitDP に含まれるか微妙ですが、一応入れておきます。
52 JOI 2017 予選 4 - ぬいぐるみの整理 少し難しいですが、是非挑戦してみてください。
動的計画法：その他
その他の DP として代表的なものは、最長増加部分列問題 (LIS) です。
53 DPL_1_D - 最長増加部分列
54 AtCoder Beginner Contest 006 D - トランプ挿入ソート
55 AtCoder Beginner Contest 134 E - Sequence Decomposing チャレンジ問題です。
最短経路問題：ダイクストラ法
56 GRL_1_A - 単一始点最短経路 基本問題です。
57 JOI 2008 予選 6 - 船旅 後述のワーシャルフロイド法でも解けます。
58 JOI 2016 予選 5 - ゾンビ島 前述の幅優先探索も使います。実装がやや重めです。
59 JOI 2014 予選 5 - タクシー
最短経路問題：ワーシャルフロイド法
60 GRL_1_C - 全点対間最短経路 基本問題です。
61 AtCoder Beginner Contest 012 D - バスと避けられない運命
62 AtCoder Beginner Contest 079 D - Wall
63 AtCoder Beginner Contest 074 D - Restoring Road Network ちょっと数学的考察が必要で難しいですが、是非解いてみましょう。
最小全域木問題
64 GRL_2_A - 最小全域木 基本問題です。
65 JOI 2010 春合宿 - Finals (問題pdf) JOI 春合宿の問題ですが、比較的簡単です。
66 AOJ 1127 - Building a Space Station
67 AtCoder Beginner Contest 065 D - Built? やや難しいです。単純に最小全域木を求めると、$N$ 頂点 $N^2$ 辺になりますが、なんとそれを減らすことができます。
高速な素数判定法
68 NTL_1_A - 素因数分解 基本問題です。
69 AtCoder Beginner Contest 084 D - 2017-like Number
高速なべき乗計算
70 NTL_1_B - べき乗
71 Square869120Contest #1 E - 散歩
※ べき乗だけを使う問題は少ないですが、$nCr$ などを求める際に、逆元とセットで出てくることが多いです。例えば、$ax≡1 \ (mod \ p)$ の解は $a^{p-2} \ mod \ p$ となります。（$p$ が素数の場合）
逆元を使う問題
72 AtCoder Beginner Contest 034 C - 経路 nCr を求めるだけの基本問題です。
73 AtCoder Beginner Contest 145 D - Knight
74 AtCoder Beginner Contest 021 D - 多重ループ
75 AtCoder Beginner Contest 149 F - Surrounded Nodes チャレンジ問題です。解けなくても、「そういう特殊な出力形式の問題ってあるんだな」と感じてほしいです。
累積和
76 全国統一プログラミング王決定戦本戦 A - Abundant Resources 基本です。累積和を使わなくても解けますが、是非使って解いてみてください。
77 JOI 2010 本選 1 - 旅人
78 JOI 2011 本選 1 - 惑星探査 二次元累積和です。
79 AtCoder Beginner Contest 106 D - AtCoder Express 2
80 GigaCode 2019 D - 家の建設
(ここから先は、「いもす法」というアルゴリズムを使う場合があります。)
81 AtCoder Beginner Contest 014 C - AtColor 基本問題です。
82 AOJ 2013 - 大崎
83 JOI 2015 本選 1 - 鉄道運賃
84 JOI 2012 本選 4 - 釘 チャレンジ問題です。
Union-Find
85 DSL_1_A - 互いに素な集合 基本問題です。
86 AtCoder Beginner Contest 075 C - Bridge 深さ優先探索による連結成分の個数の数え上げでも解けますが、Union-Find でも解いてみましょう。
87 AtCoder Beginner Contest 120 D - Decayed Bridge 一個の考察ステップがあり、少し難しいですが、解くことで得られる力は大きいと思います。
その他のテクニック
「圧縮」によって解ける問題たちです。
88 JOI 2008 本選 1 - 碁石ならべ
89 JOI 2013 本選 1 - 電飾
「単純な幾何計算」によって解ける問題たちです。標準ライブラリに存在する、2 乗根・三角関数などを使うと解けます。
90 Square869120Contest #5 B - Emblem
91 AtCoder Beginner Contest 144 D - Water Bottle 本記事では触れていませんが、三角関数の逆関数を使って解くことができます。
実装問題
考察に比べて実装がとても重い問題です。練習になると思います。
92 AOJ 1193 - 連鎖消滅パズル
93 Square869120Contest #3 B - 石落としゲーム
94 AOJ 1149 - ケーキカット
数学的な問題
AtCoder の問題の一部では、解くために数学的な考察を必要とします。上級編にも繋げていくために、水色コーダーを目指している人は「数学的考察って何なのか」「数学的考察ってどんな感じで使うのか」くらいは知っておくと良いと思うので、これを感じられる問題の代表例を紹介しておきます。
95 AtCoder Beginner Contest 149 B - Greedy Takahashi 200-300 点問題で出る数学的問題は大体そんな感じです。（貪欲法アルゴリズムに繋がってきます。）
96 AtCoder Beginner Contest 139 D - ModSum 考察一個です。
97 AtCoder Beginner Contest 150 D - Semi Common Multiple
98 三井住友信託銀行プログラミングコンテスト2019 予選 E - Colorful Hats 2
99 DDCC2020 予選 D - Digit Sum Replace これも考察一個です。
100 Tenka1 Programmer Beginner Contest D - Crossing やや難しいですが、頑張って解いてください。
これが全部解けたら、自信をもって「水色コーダー相当の実力」があるといってよいです。
2-4. 「水色コーダー」を目指す人のための Tips 5 個
中級編の最後に、水色コーダーを目指す皆さんにとって便利な情報をいくつか紹介したいと思います。
2-4-1. 「蟻本」のすすめ
ところで、プログラミングコンテストチャレンジブック（通称：蟻本）という本があります。
この本では、競技プログラミングで使われるアルゴリズムの解説がされてあるだけでなく、各種アルゴリズムを使う競プロの問題の解き方も丁寧に説明されています。
競プロ関連の本の中で最も売れているものだといって良いです。「蟻本を読んで強くなった！」という人はたくさんいるので、是非持っておきましょう。サンプルコードなども載っているので、「典型アルゴリズムのコードの書き方を忘れてしまった！」なんてときにも便利です。
2-4-2. AOJ の「ALDS」コースのすすめ
初級編でも述べたように、AOJ はプログラミングの基礎やアルゴリズムの基礎が学べるコースがたくさんあるのが特徴です。2 その中で、典型アルゴリズムが学べるコースがあって、
というものです。全部で 60 問近くありますが、本記事の中級編に載っている大体のアルゴリズムが確認できるので、各種アルゴリズムを学習した後に、是非該当する分野の問題を解いてみてください。（典型アルゴリズムを既に知っていたという方も、アルゴリズムを使う練習にもなるので解くことをお勧めします）
※ ちなみに、中級編どころか上級編ですら述べないようなアルゴリズムを使う問題も ALDS には載っていますので、全ての問題を解く必要はありません。
2-4-3. 過去問は何分で解説を見ればよいか？
さて、過去問を解いていて、そもそも解法が全然分からないとき、いつになったら解説を読めば適切なのかわからない人が多いと思います。そこで、経験則からの大体の目安を提示しておきます。
| 難易度 | 100 点問題 | 200 点問題 | 300 点問題 | 400 点問題 | 500 点問題 | 600 点問題 |
|---|---|---|---|---|---|---|
| 茶色コーダー | 5 分 | 7 分 | 30 分 | 45 分 | - | - |
| 緑色コーダー | 5 分 | 5 分 | 20 分 | 35 分 | 50 分 | 2 時間 |
| 比較的簡単な問題にも関わらず解法がわからない場合、「典型知識や典型テクニックを知らないから解けなかった」という可能性がとても高いです。そのため、早めに解説を見ることをおすすめします。(2/20 00:47 PM. 追記) |
※ 何分経っても解法が分からなかったら、ということです。つまり、例えば緑コーダーが 400 点問題を解くとき、解き始めてから 15 分で解法がわかって実装も 10 分でできたのに、10 分間バグの原因がわからなくて合計 35 分超えてしまったので解説を見るべき、ということではないです。
2-4-4. Twitter 活用のすすめ
競技プログラミングをやっていくうちに、何かわからないことを質問したくなることがあると思います。例えば、
「このコードのバグが分からない。誰か原因教えて。」
「動的計画法が理解できないので教えてください。」
とか、色々あると思います。そんな時に便利なのは Twitter です。基本的に競技プログラミングをやっている人は優しい（というかコミュニティがあたたかい）ので、Twitter に質問を投稿したり、ダイレクトメッセージで強い人に聞いたりすると、答えてくれる場合が多いです。
また、Twitter をやっている場合、コンテストで成功して一色上にあがったときに、例えば「水色になりました！！！！」とかいうツイートをすると、とても多くの人から「おめでとう」とリプライされることがあります。これは競プロ界隈の文化の一つなのですが、色が上がったときにとてつもない達成感を得ることができます。
2-4-5. 競プロ関連イベント参加のすすめ
競技プログラマーが一箇所の会場に集まってコンテストをやるようなイベントが定期的に開かれます。例えば、
- 東京工業大学プログラミングコンテスト2019 (TTPC2019) オンサイト [2019年8月31日開催]
- GigaCode 2019 [2019年11月24日開催]
- ゆるふわ競技プログラミングオンサイト at FORCIA [2020年2月29日開催]
などがあります。
このような競技プログラミング関連のイベントに参加する初中級者は現状それほど多くないのですが、一度参加してみることをお勧めします。
- 競プロ参加者との交流ができて楽しい
- 普段はオンライン上での活動がほとんどである「競技プログラミング」に対するモチベーションの維持、あるいはモチベーションの向上に繋がる
などが、利点として挙げられます。
2-5. 本記事を終えた次は？
本記事の内容をマスターできれば、水色コーダーになれると思います。水色コーダーといったら、AtCoder の上位 1 割ですので、十分中級者を名乗って良いと思います。ちなみに水色コーダーになると、半数以上の企業においてアルゴリズム構築能力がカンストします。
しかし、さらに上を目指したい。青色コーダーや黄色コーダー、そして橙色コーダーといった競プロ成績上位ランカーを狙っていきたいという方。中級編よりもさらに高いレベルまでフォローしていますので、是非上級編もお読みください。
（初中級者の方でも、上級者にどういうアルゴリズム・知識・練習方法が求められるかを知る機会になると思うので、興味があれば是非お読みください。）
上級編
-1. つづく
次は、上級編に続きます。
-
2020 年 8 月 3 日時点です。 ↩
-
初級編で説明した Introduction To Programming I (ITP1)、中級編で説明した Introduction To Algorithms and Data Sets (ALDS) だけではなく、動的計画法が学べる DPL、グラフ理論が学べる GRL、整数論が学べる NTL など、AOJ には様々なコースが用意されています。 ↩