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.	おわりに

3-0. 上級編で紹介すること

上級編では、AtCoder で黄色コーダー（レーティング 2000）、そして橙色コーダー（レーティング 2400）まで上達する方法を記します。

なお、AtCoder のレーティングは以下の通りです。黄色コーダーだと上位 2%、橙色コーダーだと**上位 0.6%**くらいです。¹

レーティング	色	相対的な位置	絶対的な位置
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 さんのブログがソースです。

3-1. 「黄色コーダー」で要求される 6 つのこと

AtCoder で黄色コーダー、つまりレーティング 2000 に到達するには、

AtCoder Beginner Contest でほぼ確実に 5 問正解できる
AtCoder Beginner Contest で確率 50% で全問（6 問）正解できる
それほど難しくない問題（500 点以内）をかなり速く解くことができる
- 問題毎の正解者数によるが、A 問題だと 1 分、B 問題だと 2 分、C 問題だと 5 分、D 問題だと 10 分、E 問題だと 20 分が目安。
- 目安通りの時間で解けば、40 分以内で 5 問正解できる。
AtCoder Grand Contest (AGC) などの数学的考察を要するコンテストでも、ある程度の戦績を残す
- 例えば AGC の場合、2 問正解以上が望ましい

ことが要求されます。そのためには、以下の 6 つのことができれば良いと考えます。（もちろん、水色コーダーで要求される 4 つのことは全てクリアしている必要があります。）

条件 1

「プログラミングコンテストチャレンジブック（蟻本）」に載っている大半のアルゴリズムとデータ構造を理解する。具体的には、以下のアルゴリズム（計 23 個）とデータ構造（計 5 個）を理解する。

(i) 中級編 2-1. 節に書かれている 12 個のアルゴリズムと 3 個のデータ構造。


全探索	二分探索	深さ優先探索	幅優先探索
動的計画法	ダイクストラ法	ワーシャルフロイド法	クラスカル法
高速な素数判定法	べき乗の高速な計算	逆元の計算	累積和・いもす法
グラフ理論	木	Union-Find

(ii) 中級編には書かれていないが蟻本には書かれている、11 個のアルゴリズム。


座標圧縮	半分全列挙	行列累乗	ダブリング
Grundy 数	Rolling Hash	平方分割	最大流
最小カット	二部グラフ判定	二部マッチング

(iii) 中級編には書かれていないが蟻本には書かれている 2 個のデータ構造。


Binary Indexed Tree (BIT)	セグメント木（※遅延評価セグメント木を含む）

条件 2

条件 1 で紹介したアルゴリズム・データ構造をコンテスト中に引き出し、それらを使えるようになる。
つまり、本記事で紹介する「アルゴリズム」「データ構造」が完全に身につく、ということ。

条件 3

ある程度の数学的考察ができるようになる。

※ AtCoder には、アルゴリズムが活用できるかどうかを問う問題だけでなく、数学的考察ができるかどうかを問う問題も出てきます。（中級編 2-3. 節の問題 95 ～ 100 で述べた通りです。）特に、問題が難しくなるにつれ、この傾向が強まります。そのため、黄色コーダーになるためには、数学的考察を要する問題も十分に解ける必要があります。

条件 4

25 行程度のプログラムであれば、ほぼバグらせずに書くことができる。
60 行程度のプログラムであっても、ある程度速く書くことができる。バグらせても、平均して 10 分以内でバグを解決できる。

※ 実際に、60 行程度のプログラムを、バグ取り含めて平均して 30 分以内で書けるようになれば、AtCoder Beginner Contest で全問正解 75 分以内が十分望めます。

条件 5

タイピングがある程度高速にできる。経験則では、1 分間におよそ 350 タイプ数以上の速度があることが望ましい。

実際に、成績上位者の中にもタイピングが遅い（200 タイプ数など）人は一部いますが、特に AtCoder Beginner Contest を戦うにあたって、タイピングの速度はとても重要です。

例えば、AtCoder Beginner Contest 148 において、30 分で全完するのと 40 分で全完するのでは、パフォーマンスが 250 以上 異なります。

条件 6

AtCoder の過去問を目安として 1000 問以上解き、競プロの問題に完全に慣れる。

補足

上の 6 つの条件を満たすようになれば、AtCoder Beginner Contest の E 問題までは安定して早解きできると思います。F 問題も、正解者数が 250 人を超える比較的簡単な問題であれば、正解することができると思います。

ちなみに、直近 15 回の AtCoder Beginner Contest (ABC141 ～ ABC155) において、F 問題の正解者数が 250 人を超えたのは 7 回です。そのように、全問正解を 3 - 5 割の確率で達成するのも十分可能です。

また 6 つの条件を満たすと数学的考察力も向上してくるので、AtCoder Grand Contest の問題も段々と解ける割合が増えてくると思います。

さて、それらができるようになるためには、どのような練習をすれば良いのでしょうか。

3-2. 「黄色コーダー」になるためのガイドライン

黄色コーダーに到達するためにやるべきことは、以下の 7 つだと思います。

それぞれ、順番に説明していきたいと思います。

3-2-1. 11 個のアルゴリズムを新たにマスターする！

黄色コーダーになるためにマスターするべきアルゴリズムは、以下の 23 個です。


全探索	二分探索	深さ優先探索	幅優先探索
動的計画法	ダイクストラ法	ワーシャルフロイド法	クラスカル法
高速な素数判定法	べき乗の高速な計算	逆元の計算	累積和・いもす法
座標圧縮	半分全列挙	行列累乗	ダブリング
Grundy 数	Rolling Hash	平方分割	最大流
最小カット	二部グラフ判定	二部マッチング

そのうち、最初の 12 個（表の 1 ～ 3 行目）をマスターする方法は、中級編 2-2-2. 節で解説がされていますので、こちらをご覧ください。本節では、残りの 11 個を理解できる記事たちを紹介したいと思います。

座標圧縮

まとまった解説記事が見つからないので、こちらで簡潔に解説しておきます。

座標圧縮とは、とても大きい座標があって現実的に扱えないサイズである場合に、圧縮して計算量を抑えるというテクニックです。以下の画像のように、相対的な位置関係が崩れないように圧縮します。（一次元の場合でも、二次元の場合でも通用します。）

実装などを含めた詳しい部分は、以下の記事に書かれています。

半分全列挙

$N$ 通りの全列挙を $O(\sqrt{N})$ 程度の計算回数で効率的に計算する手法です。以下の記事で解説されています。(2020/08/03 更新)

たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】の 5 章

行列累乗

行列の累乗を繰り返し二乗法を利用して効率的に求めるテクニックです。フィボナッチ数の $10^{9}$ 番目の値を高速に求めたり、漸化式の $10^{9}$ 番目の値を高速に求めたりすることに使われます。以下の記事で解説されています。

競技プログラミングにおけるDPの考え方 ~繰り返し２乗法と行列累乗~

ダブリング

「$N$ 個次の要素を知りたい」という状況で頻繁に使われるテクニックです。以下の記事で解説されています。

Grundy 数

競プロには、ゲーム理論の問題がよく出ます。ゲーム理論の問題を解くにあたって、「Nim」というゲームに見ることができる「Grundy 数」は知っておくべき概念です。以下の記事で解説されています。

競プロにおけるNim、Grundy数とNimK

Rolling Hash

競プロでは、文字列に対するクエリに高速に答えるなどといった問題がよく出ます。文字列系の問題を解くにあたって、Rolling Hash は知っておくべきアルゴリズムです。以下の記事で解説されています。

ローリングハッシュと Suffix Array　の 1 ～ 18 ページ

平方分割

平方分割（バケット法）は、簡潔に書くと、長さ $N$ の列を $\sqrt{N}$ 個ごとに分けて考えるアルゴリズムです。以下の記事で解説されています。

プログラミングコンテストでのデータ構造　の 19 ～ 32 ページ

最大流（最大フロー）

最大流は、グラフ上の流れ（フロー）を扱うアルゴリズムの中では最も競プロで使われるものです。以下の記事で解説されています。

最大流 (max flow)　の 1 ～ 34 ページ

最小カット

フローで解ける競プロの問題の中には、最小カット問題に帰着することで解ける問題も多いです。最小カット問題に関する解説と正当性の証明は、以下の記事にまとまっています。

最大流 (max flow) の 35 ～ 45 ページ

二部グラフ判定

そもそも「二部グラフ」って何でしょう？　これは、グラフの各頂点を青と赤で塗るとき、「青の頂点同士を繋ぐ辺」「赤の頂点同士を繋ぐ辺」が存在しないように塗ることができるグラフのことです。

二部グラフは特殊な性質を持っているため、競プロで問題にされることが多いです。そのような問題を解くためにはまず、グラフが二部グラフかどうかを判定しなければなりません。その二部グラフ判定は、以下の記事で解説されています。

2 部グラフ判定問題

二部マッチング

二部グラフのマッチングは、輸送問題など実世界の問題を解くときによく使われるアルゴリズムです。もちろん、競プロで出題されることもあります。以下の記事で解説されています。

‪実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬

補足

新たに学習したアルゴリズムを使って解ける問題は、

3-3. 節：分野別　上級者が解くべき過去問精選 100 + 50 問

に載っています！

3-2-2. 2 個のデータ構造を新たにマスターする！

前節で述べた通り、競技プログラミングにはアルゴリズムを学ぶことが大切です。一方、データ構造を学ぶことも大事です。

さて、黄色コーダー になるために必要なアルゴリズムは、以下の 2 つです。

Binary Indexed Tree (BIT)
セグメント木（RMQ だけでなく、遅延評価セグメント木などを含む）

それらのアルゴリズムが学習できる記事たちなどを紹介します。

Binary Indexed Tree (BIT)

競プロで頻出のデータ構造の一つです。解説は、以下の記事にまとまっています。

Binary Indexed Tree　の 1 ～ 20 ページ
21 ページ目以降も、競プロのどういう場面で BIT が使われるかが書いてあるので、読むといいと思います。

セグメント木

競プロで頻出のデータ構造の一つです。AtCoder ではそれほど多く見ないですが、日本情報オリンピックでは、とても多くの問題がセグメント木を使って解けます。

基本的に、セグメント木は

単純なセグメント木（RMQ またはその亜種）
遅延評価セグメント木

の 2 つに分かれます。それぞれの解説は、以下の記事にまとまっています。

典型１：RMQ を解くアルゴリズム

Range Minimum Query (RMQ) の 1 ～ 23 ページ目
図を用いてわかりやすく解説されています。

典型２：遅延セグメント木

遅延評価セグメント木をソラで書きたいあなたに
「遅延評価セグメント木とは何なのか」という説明から、遅延評価セグメント木のアルゴリズム、そしてそれを使えばどんな問題が解けるのか、まで解説されています。

補足

新たに学習したデータ構造を使って解ける問題は、

3-3. 節：分野別　上級者が解くべき過去問精選 100 + 50 問

に載っています！

3-2-3. TopCoder SRM の問題を解いて数学的考察力を鍛える！

前述のとおり、黄色コーダーになるためには、アルゴリズム活用能力だけでなく、数学的考察力も身につける必要があります。一方で、アルゴリズムを学習するだけでは数学的考察力は身につきません。果たして、どのような練習をしたら数学的考察力が身につくのでしょうか。

そこで、お勧めの練習方法は、

TopCoder の SRM を解くこと

です。ちなみに、SRM とは Topcoder で開かれる競プロコンテストのことです。私が TopCoder を解くのをお勧めする理由は以下の 2 点です。

TopCoder の問題は、全般的に数学的考察力が問われる問題の割合が大きい
ただ数学的考察力が問われるだけではなく、解いた時の学びが多い問題の割合も大きい

そこで、どのようにして TopCoder の問題を解けばよいのでしょうか。

TopCoder に登録する方法

TopCoder の問題を解くには、アカウントを登録する必要があります。アカウントを登録する方法は以下の記事に書かれています。

TopCoderアカウント登録、SRM(Single Round Match)解説

TopCoder で問題を解く方法

さて、アカウント登録が完了した人へ。TopCoder は AtCoder のように問題閲覧・提出方法が簡単ではないので、どのようにして問題を見るか、どのようにして提出するかわからない人が多いと思います。以下の記事に解説されていますので、是非お読みください。

Topcoderで練習問題にたどり着くのに一苦労した話。サイトの構成が複雑すぎる

SRM Div1 Easy を埋めよう　～Div1 Easy Hunting 50問～

さて、数多くある SRM の問題の中から、何を解けばよいのでしょうか。水色コーダーや青色コーダーにとっては、SRM Div1 Easy の難易度を解くのが適切です。AtCoder 換算で 400 ～ 700 点相当の難易度の問題が多いです。

そこで、SRM Div1 Easy の中で数学的考察力が身につく教育的良問 50 問を紹介します。是非解いてみましょう。

SRM Div1 Easy Hunting 50問　by　@square1001

3-2-4. 日本情報オリンピック（JOI）の問題を解いて実装力を鍛える！

前節では、黄色コーダーになるためには、数学的考察力が必要だと書きました。一方で、黄色コーダーになるために、実装力も必要だと思います。例えば、

50-70 行程度のプログラムを素早く書く
50-70 行程度の長めのプログラムでも、バグの発生する個数をできるだけ少なくする

などが要求されます。そこで、実装力を鍛えるために、解くべき最も適切な過去問は、

日本情報オリンピックの過去問

です。日本情報オリンピックの問題は実装が重いものが多く、実装の練習になります。ちなみに、ものによっては 200 行以上の実装を要する問題もいくつかあります。

https://joi.goodbaton.com/ に難易度別過去問リストが載っているので、是非解いてみてください。難易度は 1 ～ 12 の 12 段階に分かれているのですが、各実力帯ごとの解くべき難易度は、

AtCoder レート	解くべき難易度帯
水色コーダー	6 ～ 7
青色コーダー	7 ～ 9
黄色コーダー	8 ～ 10

といった感じです。

3-2-5. 過去問を解きまくる！

黄色コーダーになるためには、たくさんの過去問を解く必要があります。実際に、AtCoder の正解問題数と、黄色コーダーを達成できた割合は、以下のようになっています。(2019/12/09 時点の統計です)²

正解問題数	黄色コーダー達成割合
500 - 599 問	6.8%
600 - 799 問	11.5%
800 - 999 問	17.1%
1000 - 1199 問	35.4%
1200 - 1499 問	58.8%
1500 - 1999 問	87.1%
2000 問以上	100.0%

そのため、AtCoder Problems などを使って、過去問を解きまくることが大切です。しかし、SRM や JOI の問題も含めて解いたり、アルゴリズムやデータ構造をしっかり理解できた人の方が、上達は速いと思います。

ですので、過去問を解くのは大切ですが、ただ過去問をがむしゃらに解くのではなく、3-2-1. 節から 3-2-4. 節までで述べたことを意識して過去問埋めをしましょう。

3-2-6. 「バーチャル参加」を活用して早解き力をもっと鍛える！

中級編では、AtCoder Problems によるバーチャルコンテストのサービスを紹介しました。一方、2019 年 11 月、AtCoder 公式が、コンテストを仮想的にやることができるシステムを開発しました。

これが、**「バーチャル参加」**です。

バーチャル参加では、リアルタイムで「バーチャル順位表」が更新されるので、コンテストのような感覚で問題を解くことができます。（過去にバーチャル参加をやった人の中での順位が、バーチャル順位表に反映されます。）

さて、早解き力を鍛えるためには、以下のようにバーチャル参加を活用すると良いと思います。

AtCoder Beginner Contest を 1 個選び、バーチャル参加をする。
これは、昔の 4 問編成のコンテストでも、現在の 6 問編成のコンテストでも良い。
できれば解いていない問題が多い方が良いが、直近 1 カ月以内に解いた問題が存在しない場合は、バーチャル参加するコンテストとして選べる。
これを週に 2-3 回やる。（4 問編成だと 50 分、6 問編成だと 80-100 分で終わると思うので、大した負担ではない。）

もう一個有効な手段があって、これはバーチャル参加中の自分を振り返るという手段です。バーチャル参加後に、自分がコンテスト中にどのような動きをしたのか、そして実際にどこで時間を取られたのか（考察か、実装か、バグ取りか）原因を分析することで、上達は速くなると思います。しかし、いちいちバーチャル参加中に自分の挙動をメモすることはできません。そこで役立つのは、

バーチャル参加中の、パソコンのスクリーンの動きをビデオで撮っておく

ということです。録画の方法については、例えば Windows 10 の場合

をお読みください。（@renee さんコメントを頂きありがとうございます。）

3-2-7. タイピングを練習して早解き力をさらに磨く！

競技プログラミングは、速度の勝負という面があります。特に、AtCoder Beginner Contest ではその面が大きいです。例えば、AtCoder Beginner Contest 148 の場合、

タイム	パフォーマンス
30 分全完	2400
40 分全完	2146
50 分全完	1971
60 分全完	1813

となり、10 分でパフォーマンス 250 以上変わることもあります。その 10 分を削り出すために重要になってくるのがタイピング速度です。

タイピングは、オンラインゲーム感覚で練習することができます。そこで、便利なサイトをいくつか紹介します。

1. 寿司打

Flash タイピング【寿司打 - SushiDA -】
日本語のタイピングが練習できます。
ランキングもあって、楽しいです。

2. 10FastFingers

Typing Test English - 10FastFingers.com
英語の基本単語 200 語のタイピングが練習できます。

3. P検　タイピング

無料タイピング練習| P検-ICTプロフィシエンシー協会
日本語と英語が両方できます。
多くの種類の文章が出てくるので、タイピングの練習の効果が比較的大きいです。

以上 7 項目を、ガイドラインとして説明しました。
この 7 項目をしっかりやれば、黄色コーダー、つまりレーティング 2000 を達成できる確率は十分に高いと考えられます。

そして、皆さんが黄色コーダーになる頃には、既にほとんどの会社でアルゴリズム構築能力がカンストしてしまうという、とんでもなく優秀な人材になっているのです。

3-3. 分野別　上級者が解くべき過去問精選 100 + 50 問

3-2-5. 節で、

AtCoder の問題を 1500 問解けば黄色コーダーになれる人が 8 割以上

と書きました。しかし、「習得したアルゴリズムをどれくらい使えるようになったか」によって、上達速度が大きく変わってきます。そこで、「これを解いたら学習したアルゴリズムが使えるようになる！」という教育的良問を中心に、水色コーダー以上の競プロ中級者・上級者が解くべき過去問を精選 150 問、紹介したいと思います。

1 ～ 100 問目

最初の 100 問は、中級編で紹介した基本的なアルゴリズム・データ構造で解ける問題がほとんどです。

本記事 2-3. 節| 分野別　初中級者が解くべき過去問精選 100 問

にまとめられています。確かに初中級者と書いてあるのですが、100 問中 40 問程度が水色コーダー・青コーダー相応の難易度です。ですので、黄色コーダーを達成していないうちは、100 問全部解く勢いで埋めることをおすすめします。