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%**くらいです。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 さんのブログ がソースです。 | |||
 |
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 つだと思います。
- ステップ 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 個を理解できる記事たちを紹介したいと思います。
座標圧縮
まとまった解説記事が見つからないので、こちらで簡潔に解説しておきます。
座標圧縮とは、とても大きい座標があって現実的に扱えないサイズである場合に、圧縮して計算量を抑えるというテクニックです。以下の画像のように、相対的な位置関係が崩れないように圧縮します。（一次元の場合でも、二次元の場合でも通用します。）
実装などを含めた詳しい部分は、以下の記事に書かれています。
半分全列挙
$N$ 通りの全列挙を $O(\sqrt{N})$ 程度の計算回数で効率的に計算する手法です。以下の記事で解説されています。(2020/08/03 更新)
行列累乗
行列の累乗を繰り返し二乗法を利用して効率的に求めるテクニックです。フィボナッチ数の $10^{9}$ 番目の値を高速に求めたり、漸化式の $10^{9}$ 番目の値を高速に求めたりすることに使われます。以下の記事で解説されています。
ダブリング
「$N$ 個次の要素を知りたい」という状況で頻繁に使われるテクニックです。以下の記事で解説されています。
Grundy 数
競プロには、ゲーム理論の問題がよく出ます。ゲーム理論の問題を解くにあたって、「Nim」というゲームに見ることができる「Grundy 数」は知っておくべき概念です。以下の記事で解説されています。
Rolling Hash
競プロでは、文字列に対するクエリに高速に答えるなどといった問題がよく出ます。文字列系の問題を解くにあたって、Rolling Hash は知っておくべきアルゴリズムです。以下の記事で解説されています。
- ローリングハッシュと Suffix Array の 1 ～ 18 ページ
平方分割
平方分割（バケット法）は、簡潔に書くと、長さ $N$ の列を $\sqrt{N}$ 個ごとに分けて考えるアルゴリズムです。以下の記事で解説されています。
- プログラミングコンテストでのデータ構造 の 19 ～ 32 ページ
最大流（最大フロー）
最大流は、グラフ上の流れ（フロー）を扱うアルゴリズムの中では最も競プロで使われるものです。以下の記事で解説されています。
- 最大流 (max flow) の 1 ～ 34 ページ
最小カット
フローで解ける競プロの問題の中には、最小カット問題に帰着することで解ける問題も多いです。最小カット問題に関する解説と正当性の証明は、以下の記事にまとまっています。
- 最大流 (max flow) の 35 ～ 45 ページ
二部グラフ判定
そもそも「二部グラフ」って何でしょう？ これは、グラフの各頂点を青と赤で塗るとき、「青の頂点同士を繋ぐ辺」「赤の頂点同士を繋ぐ辺」が存在しないように塗ることができるグラフのことです。
二部グラフは特殊な性質を持っているため、競プロで問題にされることが多いです。そのような問題を解くためにはまず、グラフが二部グラフかどうかを判定しなければなりません。その二部グラフ判定は、以下の記事で解説されています。
二部マッチング
二部グラフのマッチングは、輸送問題など実世界の問題を解くときによく使われるアルゴリズムです。もちろん、競プロで出題されることもあります。以下の記事で解説されています。
補足
新たに学習したアルゴリズムを使って解ける問題は、
に載っています！
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-2-3. TopCoder SRM の問題を解いて数学的考察力を鍛える！
前述のとおり、黄色コーダーになるためには、アルゴリズム活用能力だけでなく、数学的考察力も身につける必要があります。一方で、アルゴリズムを学習するだけでは数学的考察力は身につきません。果たして、どのような練習をしたら数学的考察力が身につくのでしょうか。
そこで、お勧めの練習方法は、
- TopCoder の SRM を解くこと
です。ちなみに、SRM とは Topcoder で開かれる競プロコンテストのことです。私が TopCoder を解くのをお勧めする理由は以下の 2 点です。
- TopCoder の問題は、全般的に数学的考察力が問われる問題の割合が大きい
- ただ数学的考察力が問われるだけではなく、解いた時の学びが多い問題の割合も大きい
そこで、どのようにして TopCoder の問題を解けばよいのでしょうか。
TopCoder に登録する方法
TopCoder の問題を解くには、アカウントを登録する必要があります。アカウントを登録する方法は以下の記事に書かれています。
TopCoder で問題を解く方法
さて、アカウント登録が完了した人へ。TopCoder は AtCoder のように問題閲覧・提出方法が簡単ではないので、どのようにして問題を見るか、どのようにして提出するかわからない人が多いと思います。以下の記事に解説されていますので、是非お読みください。
SRM Div1 Easy を埋めよう ～Div1 Easy Hunting 50問～
さて、数多くある SRM の問題の中から、何を解けばよいのでしょうか。水色コーダーや青色コーダーにとっては、SRM Div1 Easy の難易度を解くのが適切です。AtCoder 換算で 400 ～ 700 点相当の難易度の問題が多いです。
そこで、SRM Div1 Easy の中で数学的考察力が身につく教育的良問 50 問を紹介します。是非解いてみましょう。
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 時点の統計です)2
| 正解問題数 | 黄色コーダー達成割合 |
|---|---|
| 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 問は、中級編で紹介した基本的なアルゴリズム・データ構造で解ける問題がほとんどです。
にまとめられています。確かに初中級者と書いてあるのですが、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 本選 3 - ダーツ も半分全列挙で簡単に解けます。
行列累乗
109 yukicoder No.526 - フィボナッチ数列の第N項をMで割った余りを求める 基本問題です。
110 AtCoder Beginner Contest 009 D - 漸化式 チャレンジ問題です。$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(N \sqrt{N})$ で解くことができます。
※ セグメント木のところで紹介しますが、
といった問題も平方分割で解くことができます。もちろん、セグメント木を使うと解くことができますが、平方分割で解いてみてもいいかもしれません。
最大流／最小カット
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. 「競プロ典型 90 問」のすすめ（2021/7/12 追記）
ここまで、中級編と上級編では、以下の問題集を紹介しました。
しかし、これには「過去問である」「解説が整備されていない問題もある」などのデメリットがあります。また、AtCoder ではアルゴリズム・考察テクニックの両方が重要であるにも関わらず、後者を対策できる問題が 10 問程度しか収録されておらず、アルゴリズムにかなりの重点を置いています。
このような欠点を解消しようと思い、2021 年に入り
という新たな教材が生まれ、同年 7/11 に完成しました。（これも私が作成した教材です）
競プロ上級者を目指すために必要な問題が 90 問集まっているほか、問題のレベルは AtCoder Beginner Contest の C ～ F 問題と幅広く、難易度別に分けられています。したがって、「簡単な問題の復習」「典型知識の習得」の両方の用途に使えます。
また、下図のようにキーワードが書かれた解説もあり、要点が整理しやすいです。そして、自分のプログラムが正しいかどうかを確認できる「ジャッジシステム」が AtCoder に用意されているため、効率よく練習を行うことができます。
特に、レーティングが 400（茶色）～2299（黄色中位） の参加者にはお勧めできます。この教材について詳しく知りたい方は、
をご覧ください。
3-5. 「黄色コーダー」を目指す人のための Tips 4 個
3 章の最後に、黄色コーダーを目指す皆さんにとって便利な情報をいくつか紹介したいと思います。
3-5-1. 海外コンテストサイトのすすめ
皆さんは、AtCoder というコンテストサイトで競プロをやっていると思います。しかし、AtCoder では週に 1 回しかコンテストがありません。そうすると、
「実力を上げるためにもっとコンテストに出たい！」
と思う人もいると考えられます。そこでお勧めなのは、「海外のコンテストに参加する」という手段です。その中でも最もやりやすいのは、ロシアの
というコンテストサイトです。
CodeForces の利点
週に 2, 3 回もコンテストをやってくれるので、コンテストに出たい人にとってはお得です。例えば 2020/2/9 ～ 2/18 の僅か 10 日間で 5 回もコンテストが開催されています。
CodeForces の欠点と、その解決法
- 開始時刻が 24 ～ 26 時とかになることが多く、夜が遅いことです。
- 海外のコンテストなので、時差の関係で日本では深夜開催になってしまいます。
- ただし、毎回がそうという訳ではなく、開催時刻が早く参加できるコンテストもあります。
- 出れなかったコンテストの問題は、過去問として（あるいはバーチャル参加で）解けばよいです。
- 問題文が英語であることです。
- いずれ英語は必要になるので、少なくとも競プロの問題文を読めるくらいまでのレベルまでは、英語を勉強することをお勧めします。
3-5-2. 競プロ作問のすすめ
日本には、AtCoder だけではなく、yukicoder という比較的ゆるふわなコンテストサイトがあります。yukicoder の最大の特徴として挙げられるのは、レート帯に関わらず、だれでも作問をすることができることです。
何故競プロ作問は良いのでしょうか。この理由は 2 つあります。
- 自ら問題を作ってみることで、アルゴリズムへの理解が深まるうえ、作問者の意図を感じることができる。それらは実力の向上につながる。
- 「作問」という新しいことをやってみることで、競プロのモチベーション維持につながる。
さて、どのようにして作問をすれば良いのでしょうか。yukicoder や AtCoder 非公式コンテストなどで作問をする方法・テクニックは、以下の記事にまとまっています。
という訳で、もし宜しければ、皆さんも一度競プロ作問をやってみませんか。
3-5-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 分 |
| 比較的簡単な問題にも関わらず解法がわからない場合、「典型知識や典型テクニックを知らないから解けなかった」という可能性がとても高いです。そのため、早めに解説を見ることをおすすめします。(2/20 00:47 PM. 追記) |
※ 茶色コーダー・緑コーダーの場合はこちらを参照。
※ 答えるのにかかった時間ではなく、解法が分からなかった時間です。
3-5-4. ライブラリ整備のすすめ
皆さんの中に、こういう考えを持っている人はいますか。
例えばセグメント木とか RMQ とか BIT とか UnionFind とか、いちいち書いていると時間がかかって面倒なのではないか。これをどうにかして節約できないか。
この問題を解決する手段の一つがライブラリ整備です。予め各種アルゴリズムの実装ソースコードを作っておき、コンテスト時にはそのソースコードを貼り付けるだけにする、という手法です。（以下、ライブラリ整備の例です。セグメント木や幾何ライブラリなどを整備しています。）
※ AtCoder ではライブラリが使えますが、中高生が出場できる大会の一つ「日本情報オリンピック」の本選・春合宿本番ではライブラリが使えないことにご注意ください。
4. 「橙色コーダー」になるためには何をすれば良いのか
3 章では、黄色コーダーに到達には何が要求されるのか、到達するまでの練習方法、意識すべきポイントなどについて記しました。
本章では、黄色コーダーから、一個上のランクである橙色コーダーに上がるためには、何をすれば良いのかを記します。
黄色と橙色の差は「演習量」
黄色コーダーから橙色コーダーにかけて、学ぶべきアルゴリズムはそれほど増えません。
一方で、レーティングが 2000 以上となると AtCoder Beginner Contest におけるレーティングの変動が無くなるなどといった理由で、レーティングを上げるために解くべき問題のバリエーションが一気に増えます。そのため、演習量が大切になってきます。実際に、mencotton さんのツイート によると、以下の統計情報が明らかになっています。（2020/01/17 時点の統計です）
| 条件 | 60% ライン | 90% ライン |
|---|---|---|
| 黄色コーダー達成 | 1510 問 AC | 1880 問 AC |
| 橙色コーダー達成 | 1910 問 AC | 2200 問 AC |
つまり、黄色コーダー達成から橙色コーダー達成まで、およそ 400 問解く必要があったケースが多い、ということが分かります。
しかし、重要なのは解く問題の数だけではありません。橙コーダーになると、
- 「早解き力」 だけでなく
- 難しい問題を解く力
も重要になってくるのです。その難問をコンテスト時間いっぱい使って解けるようになるためには、どのような練習をすれば良いのでしょうか。
難問を時間かけて解く練習が重要
難しい問題をコンテストで解けるようになるためには、
- AtCoder Problems における橙後半相応（2600+）～赤色コーダー相応の難易度を、時間かけて解く
ことが練習として良いと思います。3
最初は 1 問当たり 2 時間くらいかかったり、2 時間あっても解けないことがあると思います。それは高難易度帯の考察をやったことがないので当然です。しかし、難問を 50 問くらい解いていくうちに、数問に 1 問の割合で解けるようになっていきます。
橙後半相応の難易度の問題を 1 時間以内で解ける確率が 2-3 割になると、橙色コーダーの実力が付いたといえるでしょう。
難問を解くにあたって重要なこと
最後に、難問を解くにあたって重要なことをいくつか紹介します。
1 点目
解説は見ないことをお勧めします。
そのくらいの難易度になってくると、たくさん考えた分だけ、考察力が付くからです。また、「どんな感じで解法が見えたのか」というのが分かれば復習などに役立てることができますが、それは自力で解けたときにしかわかりません。その点でも、自力で解くことは大切です。
2 点目
さて、どのタイミングで問題を解くのを諦めれば良いのでしょうか。
解法を考える時間だけで 120 分程度使っても解法が分からなかった場合は、この問題を諦めて別の問題を解くことをお勧めします。なお、2 週間～数カ月くらい経ってから、以前諦めた問題に再挑戦するのはとても良い方法です。それが解けたときの達成感はとても大きく、モチベーションの維持にもつながります。
3 点目
過去問を解くときに、集中するときと集中しないときでは効率が全然違います。
一方、難問を解くためには 2 時間や 3 時間など長い時間を使う必要があることが多いです。そのため、集中力が切れやすいです。集中力を維持する一つの手段としては、タイマーで時間を測ると良いです。難問を解く練習には、それほど早解き力は必要ないですが、集中力の維持という別の目的でタイマーが有効だと考えられます。
5. 「橙色コーダー」の先 ～ガチンコ競技としての競プロのはじまり～
日本で橙色コーダー以上の参加者は、僅か 104 人しかいません。4
しかし、そのような人にしか見られない景色があるのです。これは、「ガチンコ競技としての競プロ」をより強く感じ始めるということです。橙色コーダー以上の強い人は、
- 企業コンテストの本戦に行くことができる機会が多い
- 国際情報オリンピック (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 問それぞれの素敵な問題を提供してくださった方々、読んでくださった読者の皆さん、そして競技プログラミングに関わるすべての方々に感謝申し上げます。本当にありがとうございました。
-
2020 年 8 月 3 日時点。 ↩
-
ソースは 0214sh7 さんのツイートです。この統計資料は 2019 年 12 月 9 日に私（E869120）が調査したものであり、ここではその統計資料を全体に広めた 0214sh7 さんのツイートを引用しています。（2/20 08:11 PM. 追記） ↩
-
私が橙色コーダーから赤色コーダーになるために使った練習方法ですが、橙色コーダーにより高い確率でなりたい場合、黄色コーダーの時点でその練習方法を使うこともおすすめです。 ↩
-
2020 年 8 月 3 日時点。 ↩