0. はじめに

• レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう！】
• レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

からの続きです！

上級編から読む方へ

近年、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 問	この 120 問解けば実力上がります
3-4.	「黄色コーダー」を目指す人のための Tips 4 個
4.	「橙色コーダー」になるためには何をすれば良いか？	橙色までサポートします
5.	「橙色コーダー」の先　～ガチンコ競技としての競プロのはじまり～
6.	おわりに

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

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

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

レーティング	色	相対的な位置	絶対的な位置
2800+	赤	上位 0.3%
2400-2799	橙	上位 0.9%
2000-2399	黄	上位 2.5%	アルゴリズムの研究職・研究開発で重宝されるレベル
1600-1999	青	上位 6%	ほとんどのIT企業でアルゴリズム能力がカンストする
1200-1599	水	上位 12%	半数以上のIT企業でアルゴリズム能力がカンストする
800-1199	緑	上位 24%	エンジニアとしてかなり優秀
400-799	茶	上位 40%	学生なら優秀
1-399	灰	上位 100%

※ 絶対的な位置に関しては AtCoder 社長・chokudai さんのブログ がソースです。

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

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

• AtCoder Beginner Contest でほぼ確実に 5 問正解できる
• AtCoder Beginner Contest で確率 3-5 割で全問正解できる
• それほど難しくない問題（500 点以内）をかなり速く解くことができる
  • 問題毎の正解者数によるが、A 問題だと 1 分、B 問題だと 2 分、C 問題だと 5 分、D 問題だと 10 分、E 問題だと 22 分が目安。
  • 目安通りの時間で解けば、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 つだと思います。

• ステップ 1: 11 個のアルゴリズムを新たにマスターする！
• ステップ 2: 2 個のデータ構造を新たにマスターする！
• ステップ 3: TopCoder SRM の問題を解いて数学的考察力をつける！
• ステップ 4: 日本情報オリンピック（JOI）の問題を解いて実装力をつける！
• ステップ 5: 過去問を解きまくる！
• ステップ 6: 「バーチャル参加」で早解き力をもっと鍛える！
• ステップ 7: タイピングを練習して早解き力をさらに磨く！

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

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

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

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

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

座標圧縮

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

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

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

• 座標圧縮について勉強した (java)| バイトの競プロメモ
• 座標圧縮| 個人的な競プロメモ

半分全列挙

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

2 グループに分けて全列挙して、1 つのグループは全探索し、もう 1 つのグループは二分探索などで高速に処理する

というアルゴリズムです。この説明だけだと良くわからないと思うので、以下の問題を考えてみましょう。

数列 A=[A1,A2,...,AN]$A=[A_1,A_2,...,A_N]$、B=[B1,B2,...,BN]$B=[B_1,B_2,...,B_N]$、C=[C1,C2,...,CN]$C=[C_1,C_2,...,C_N]$、D=[D1,D2,...,DN]$D=[D_1,D_2,...,D_N]$ がある。Ai+Bj+Ck+Dl≤K$A_i+B_j+C_k+D_l\le K$ となるような (i,j,k,l)$(i,j,k,l)$ の組の個数を求めよ。
制約：N≤1500$N\le 1500$、0≤Ai,Bj,Ck,Dl,K≤109$0\le A_i,B_j,C_k,D_l,K\le {10}^9$

この問題について、以下の解法が考えられます。

• まず、長さ N2$N^2$ の配列 X$X$ を定義して、Ai+Bj$A_i+B_j$ の値を小さい順に入れる。例えば、A=[3,4,6]$A=[3,4,6]$、B=[2,6,7]$B=[2,6,7]$ の場合、X=[5,6,8,9,10,10,11,12,13]$X=[5,6,8,9,10,10,11,12,13]$ となる。
• 次に、(k,l)$(k,l)$ の組を全探索する。k,l$k,l$ の値を決めたとき、Ai+Bj≤K−Ck−Dl$A_i+B_j\le K-C_k-D_l$ を満たすような (i,j)$(i,j)$ の組の個数が分かれば良い。つまり、Xt≤K−Ck−Dl$X_t\le K-C_k-D_l$ を満たす t$t$ の個数が分かれば良い。これは二分探索によって求められる。
• 全体の計算量は O(N2logN)$O(N^{2}logN)$。

このように、2 つのグループに分けて工夫して列挙するようなテクニックを「半分全列挙」といいます。詳しい実装は以下のようになります。

• サンプルコード

行列累乗

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

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

ダブリング

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

• ダブリング| sataniC++
• 最小共通祖先 (LCA) 問題に見る、ダブリング

Grundy 数

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

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

Rolling Hash

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

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

平方分割

平方分割（バケット法）は、簡潔に書くと、長さ N$N$ の列を 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 の正解問題数と、黄色コーダーを達成できた割合は、以下のようになっています。²

正解問題数	黄色コーダー達成割合
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 Virtual Contest というサービスを紹介しました。一方、2019 年 11 月、AtCoder 公式が、コンテストを仮想的にやることができるシステムを開発しました。

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

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

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

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

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

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

ということです。Windows 10 の標準機能で画面のキャプチャと動画を録画する方法「スクリーンショット」の利用がおすすめです。

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 問解けば黄色コーダーになれる

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

1 ～ 100 問目

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

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

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

101 ～ 150 問目

最後の 50 問は、上級編で初めて紹介したアルゴリズム・データ構造で解ける問題がほとんどです。分野別にまとめられていますので、アルゴリズムを完全にマスターするために役立ててください。

基本問題から応用問題まで幅広く取り上げています。応用問題の中には難問も含まれるので、黄色コーダーを目指す人は 50 問中 35 問正解を目安に頑張ってください。50 問全部解けたら、ほぼ確実に黄色コーダーレベルのアルゴリズム活用能力がついたといって良いでしょう。

座標圧縮

101　DSL_4_A - Union of Rectangles　二次元座標圧縮の基本問題です。
102　ABC 036 C - 座圧　「座標圧縮とは何なのか」を感じられる問題です。
103　JOI 2013 予選 5 - 魚の生息範囲
104　JOI 2008 本選 5 - ペンキの色

半分全列挙

105　DPL_4_B - Coin Combination Problem II　基本問題です。
106　AtCoder Beginner Contest 032 D - ナップザック問題　の 34 点の部分点
107　CODE THANKS FESTIVAL 2017 G - Mixture Drug
108　JOI 2015 予選 6 - 財宝　とあるデータ構造を使うので、やや難しいです。

※ 中級編で 23 問目として紹介した JOI 2008 本選 5 - ダーツ も半分全列挙で簡単に解けます。

行列累乗

109　yukicoder No.526 - フィボナッチ数列の第N項をMで割った余りを求める　基本問題です。
110　AtCoder Beginner Contest 009 D - 漸化式　チャレンジ問題です。O(N3logMlogA)$O(N^{3}logMlogA)$ が間に合わないので、TLE がちょっと厳しいです。

ダブリング（最長共通祖先 [LCA] を含む）

111　GRL_5_C - LCA: Lowest Common Ancestor　基本問題です。
112　AtCoder Beginner Contest 014 D - 閉路
113　AtCoder Regular Contest 060 E - 高橋君とホテル　LCA ではないですが、ダブリングの発想を使って解けます。
114　JOI 2010 本選 5 - JOI 国のお祭り事情　超難問のチャレンジ問題です。橙色コーダー相応以上の難易度がありますが、是非挑戦してみましょう。

Grundy 数

115　AtCoder Regular Contest 013 C - 笑いをとれるかな？
116　AOJ 0401 - 石遊び
117　AtCoder Grand Contest 017 D - Game on Tree　AtCoder 1100 点のチャレンジ問題です。黄色～橙色コーダー相応の難易度があります。

Rolling Hash

118　ALDS_14_B - 文字列検索　基本問題です。
119　AtCoder Beginner Contest 141 E - Who Says a Pun?
120　AtCoder Beginner Contest 135 F - Strings of Eternity
121　AtCoder Beginner Contest 150 F - Xor Shift　文字列ではないけど Rolling Hash が使える問題です。ちなみに、Rolling Hash は文字列上だけでなく配列にも適用することができます。

平方分割

122　全国統一プログラミング王決定戦本戦 D - Deforestation　バケット法を使って、O(NN−−√)$O(N\sqrt{N})$ で解くことができます。

※ セグメント木のところで紹介しますが、

• Range Minimum Query (RMQ)
• Range Sum Query (RSQ)

といった問題も平方分割で解くことができます。もちろん、セグメント木を使うと解くことができますが、平方分割で解いてみてもいいかもしれません。

最大流／最小カット

123　GRL_6_A - Maximum Flow　基本問題です。
124　AtCoder Beginner Contest 010 D - 浮気予防　最小カット問題に帰着することができます。
125　AtCoder Regular Contest 074 F - Lotus Leaves　チャレンジ問題。2 個考察ステップが必要で、難しいです。

二部グラフを扱う問題

126　CODE FESTIVAL 2017 Qual B C - 3 Steps

二部マッチングを扱う問題

127　GRL_7_A - Bipartite Matching　基本問題です。
128　AtCoder Beginner Contest 091 C - 2D Plane 2N Points　貪欲法でも解けますが、二部マッチングでも是非解いてみてください。
129　AOJ 1163 - Cards
130　SoundHound Inc. Programming Contest 2018 (春) C - 広告　ヒント：二部グラフの最大独立集合のサイズは、頂点数から二部グラフの最大マッチングを引いたものです。
131　AtCoder Regular Contest 013 D - 切り分けできるかな？　チャレンジ問題。50 問の中で最難問の 1 つです。

Binary Indexed Tree (BIT) を使う問題

132　DSL_2_B - Range Sum Query　基本問題です。
133　DSL_2_D - Range Add Query　基本問題です。
134　ALDS_5_D - 反転数　基本問題です。
135　AOJ 0365 - 文字列スワップ　反転数を少し応用させた問題です。
136　AtCoder Regular Contest 033 - C
137　AtCoder Beginner Contest 136 F - Enclosed Points
138　JOI 2011 本選 5 - 微生物実験　チャレンジ問題です。

Range Minimum Query (RMQ)

139　DSL_2_A - Range Minimum Query　基本問題です。
140　AtCoder Grand Contest 004 B - Colorful Slimes

遅延評価セグメント木

141　DSL_2_F - RMQ and RUQ　基本問題です。
142　DSL_2_H - RMQ and RAQ　基本問題です。
143　Square869120Contest #2 H - Counting 1's
144　JOI 2008 春合宿 - Typhoon
145　JOI 2012 春合宿 - Fortune Telling
146　「みんなのプロコン」2017 予選 D - 工場

その他のテクニック

計算幾何のアルゴリズムのうち一つ、「偏角ソート」によって解ける問題たちです。

147　AtCoder Beginner Contest 033 D - 三角形の分類
148　AtCoder Beginner Contest 139 F - Engines

最短経路アルゴリズムの一つ、「拡張ダイクストラ法」によって解ける問題たちです。

149　JOI 2017 予選 6 - ヘビの JOI 君
150　いろはちゃんコンテスト Day2 G - 通学路

---

これが全部解けたら、自信もって「黄色コーダー相当のアルゴリズム構築能力がある」といってよいです。あとは 3-2-3. 節 で述べたように、TopCoder の SRM を解いて数学的考察力を上げれば、きっと黄色コーダーになれるでしょう。

3-4. 「黄色コーダー」を目指す人のための Tips 4 個

3 章の最後に、黄色コーダーを目指す皆さんにとって便利な情報をいくつか紹介したいと思います。

3-4-1. 海外コンテストサイトのすすめ

皆さんは、AtCoder というコンテストサイトで競プロをやっていると思います。しかし、AtCoder では週に 1 回しかコンテストがありません。そうすると、

「実力を上げるためにもっとコンテストに出たい！」

と思う人もいると考えられます。そこでお勧めなのは、「海外のコンテストに参加する」という手段です。その中でも最もやりやすいのは、ロシアが運営している

• CodeForces

というコンテストサイトです。

CodeForces の利点

週に 2, 3 回もコンテストをやってくれるので、コンテストに出たい人にとってはお得です。例えば 2020/2/9 ～ 2/18 の僅か 10 日間で 5 回もコンテストが開催されています。

CodeForces の欠点と、その解決法

• 開始時刻が 24 ～ 26 時とかになることが多く、夜が遅いことです。
  • 実際、毎回がそうという訳ではなく、開催時刻が早く参加できるコンテストもあります。
  • 出れなかったコンテストの問題は、過去問として（あるいはバーチャル参加で）解けばよいです。
• 問題文が英語であることです。
  • いずれ英語は必要になるので、少なくとも競プロの問題文を読めるくらいまでのレベルまでは、英語を勉強することをお勧めします。

3-4-2. 競プロ作問のすすめ

日本には、AtCoder だけではなく、yukicoder という比較的ゆるふわなコンテストサイトがあります。yukicoder の最大の特徴として挙げられるのは、レート帯に関わらず、だれでも作問をすることができることです。

何故競プロ作問は良いのでしょうか。この理由は 2 つあります。

• 自ら問題を作ってみることで、アルゴリズムへの理解が深まるうえ、作問者側の気持ちを感じることができる。それらは実力の向上につながる。
• 「作問」という新しいことをやってみることで、競プロのモチベーション維持につながる。

さて、どのようにして作問をすれば良いのでしょうか。yukicoder や AtCoder 非公式コンテストなどで作問をする方法・テクニックは、以下の記事にまとまっています。

• 競技プログラミングにおける作問テクニックを総整理！ 〜初心者から経験者まで〜

という訳で、もし宜しければ、皆さんも一度競プロ作問をやってみませんか。

3-4-3. 過去問は何分で解説を見れば良いのか？

さて、過去問を解いてそもそも解法が全然分からないとき、いつになったら解説を読めば適切なのかわからない人が多いと思います。そこで、経験則からの大体の目安を提示しておきます。

	100 点	200 点	300 点	400 点	500 点	600 点	700 点	800 点	900 点
水色コーダー	3 分	4 分	10 分	25 分	45 分	90 分	120 分
青色コーダー	2 分	3 分	6 分	20 分	40 分	80 分	100 分	120 分
黄色コーダー	1 分	2 分	4 分	15 分	35 分	60 分	80 分	100 分	120 分
橙色コーダー	15 秒	1 分	3 分	10 分	30 分	45 分	60 分	80 分	110 分

※ 茶色コーダー・緑コーダーの場合はこちらを参照。
※ 答えるのにかかった時間ではなく、解法が分からなかった時間です。

3-4-4. ライブラリ整備のすすめ

皆さんの中に、こういう考えをお持ちの人はいますでしょうか。

例えばセグメント木とか RMQ とか BIT とか UnionFind とか、いちいち書いていると時間がかかって面倒なのではないか。これをどうにかして節約できないか。

この問題を解決する手段の一つがライブラリ整備です。予め各種アルゴリズムの実装ソースコードを作っておき、コンテスト時にはそのソースコードを貼り付けるだけにする、という手法です。（以下、ライブラリ整備の例です。セグメント木や幾何ライブラリなどを整備しています。）

※ AtCoder ではライブラリが使えますが、中高生が出場できる大会の一つ「日本情報オリンピック」の本選・春合宿本番ではライブラリが使えないことにご注意ください。

4. 「橙色コーダー」になるためには何をすれば良いのか

3 章では、黄色コーダーに到達には何が要求されるのか、到達するまでの練習方法、意識すべきポイントなどについて記しました。

本章では、黄色コーダーから、一個上のランクである橙色コーダーに上がるためには、何をすれば良いのかを記します。

黄色と橙色の差は「演習量」

黄色コーダーから橙色コーダーにかけて、学ぶべきアルゴリズムはそれほど増えません。

一方で、レーティングが 2000 以上となると AtCoder Beginner Contest におけるレーティングの変動が無くなるなどといった理由で、レーティングを上げるために解くべき問題のバリエーションが一気に増えます。そのため、演習量が大切になってきます。実際に、mencotton さんのツイート によると、以下の統計情報が明らかになっています。

条件	60% ライン	90% ライン
黄色コーダー達成	1510 問 AC	1880 問 AC
橙色コーダー達成	1910 問 AC	2200 問 AC

つまり、黄色コーダー達成から橙色コーダー達成まで、およそ 400 問解く必要があったケースが多い、ということが分かります。

しかし、重要なのは解く問題の数だけではありません。橙コーダーになると、

• 早解き力　だけでなく、
• 難しい問題を解く力

も重要になってくるのです。その難問をコンテスト時間いっぱい使って解けるようになるためには、どのような練習をすれば良いのでしょうか。

難問を時間かけて解く練習が重要 (2/20 午前 0 時追記)

• AtCoder Problems　における橙後半相応（2600+）～赤色コーダー相応の難易度を、時間かけて解く

ことが練習として良いと思います。³

最初は 1 問当たり 2 時間くらいかかったり、2 時間あっても解けないことがあると思います。それは高難易度帯の考察をやったことがないので当然です。しかし、難問を 50 問くらい解いていくうちに、数問に 1 問の割合で解けるようになっていきます。

橙後半相応の難易度の問題を 1 時間以内で解ける確率が 2-3 割になると、橙色コーダーの実力が付いたといえるでしょう。

難問を解くにあたって重要なこと (2/20 午前 0 時追記)

最後に、難問を解くにあたって重要なことをいくつか紹介します。

1 点目

解説は見ないことをお勧めします。
そのくらいの難易度になってくると、たくさん考えた分だけ、考察力が付くからです。また、どんな感じで解法が見えたのかというのが分かれば復習などに役立てることができますが、それは自力で解けたときにしかわからないので、自力で解くことは大切です。

2 点目

さて、どのタイミングで問題を解くのを諦めれば良いのでしょうか。
解法を考える時間だけで 120 分程度使っても解法が分からなかった場合は、この問題を諦めて別の問題を解くことをお勧めします。なお、2 週間～数カ月くらい経ってから、以前諦めた問題に再挑戦するのはとても良い方法です。それが解けたときの達成感はとても大きく、モチベーションの維持にもつながります。

3 点目

過去問を解くときに、集中するときと集中しないときでは効率が全然違います。
一方、難問を解くためには 2 時間や 3 時間など長い時間を使う必要があることが多いです。そのため、集中力が切れやすいです。集中力を維持する一つの手段としては、タイマーで時間を測ると良いです。難問を解く練習には、それほど早解き力は必要ないですが、集中力の維持という別の目的でタイマーが有効だと考えられます。

5. 「橙色コーダー」の先　～ガチンコ競技としての競プロのはじまり～

日本で橙色コーダー以上の参加者は、僅か 106 人しかいません。

しかし、そのような人にしか見られない景色があるのです。これは、「ガチンコ競技としての競プロ」をより強く感じ始めるということです。橙色コーダー以上の強い人は、

• 企業コンテストの本戦に行くことができる機会が多い
• 国際情報オリンピック (IOI) や ACM国際大学対抗プログラミングコンテストの世界大会を見据え始める

といった感じになり、一気に「競技をやってる感」が増します。

例えば、企業コンテスト本戦の場合、予選を勝ち抜いた参加者は現地会場に集まって、同じ部屋でコーディングをします。第一回日本最強プログラマー学生選手権決勝の場合、200 人が大会本番の緊張した雰囲気の中コーディングをするのです。しかも賞金がかかっており、全国統一プログラミング王決定戦の場合、優勝賞金は 50 万円と非常に高額です。

そのように、橙色コーダー以上、特にレッドコーダーになると、ガチンコ競技としての、そしてスポーツとしての新しい競プロの世界が見え始めるのです。

目指せレッドコーダー！

6. おわりに

競技プログラミングの世界はとても広いです。だからこそ、楽しい側面もあれば、実力がそう簡単に上がらないという厳しい側面もあります。

ですが、本記事が一人でも多くの「競プロで上達したい」と思っている AtCoder 参加者の役に立つことができれば、とても嬉しい気持ちです。記事を最後までお読みいただき、ありがとうございました！

謝辞

今回は、競技プログラミングで上達するためのガイドラインを書いてみるという試みをしました。これはおそらく、少なくとも私が調べた中では初めての試みです。

そんな中、本記事を執筆するにあたり、たくさんの方々に支えていただきました。今の素晴らしい AtCoder を提供してくださった chokudai さん、各種アルゴリズムの記事を提供してくださった drken さん、iwiwi さん、satanic0258 さん、ganariya さん、Kutimoti さん、hamayanhamayan さん、ageprocpp さん、mickey24 さん、imos さん、maskot1977 さん、ofutonfuton さん、python_walker さん、baitop さん、Pocala さん、cinnamo-coder さん、Yang33-kassa さん、prd-xxx さん、tsutaj さん、pokutuna さん、過去問精選 150 問それぞれの素敵な問題を提供してくださった方々、読んでくださった読者の皆さん、そして競技プログラミングに関わるすべての方々に感謝申し上げます。本当にありがとうございました。