こんにちは、高校 2 年生の E869120 です。
私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどの各種コンテストに出場しております。ちなみに、2020 年 2 月 19 日現在、AtCoder では赤（レッドコーダー）です。
今回は、競技プログラミング上達のためのガイドラインを記します。初級編では未経験者が競プロを始めるところからサポートしますので、是非お読みください。

【シリーズ】

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

0. はじめに

皆さん、競技プログラミング (競プロ) をご存知でしょうか。

近年、競プロの存在感が日に日に高まってきており、最近では IT 業界だけでなく、大学生・中高生の間でも広まっています。

その中でも特に、AtCoder 株式会社¹　の存在感が高まっています。AtCoder は日本発のプログラミングコンテスト運営会社として 2012 年 6 月に設立されて以来、年々活動の幅を広げていきました。2017 年 9 月時点での参加者数は 37,000 人でしたが、2019 年 4 月時点では 110,000 人と、約 1 年半の間に 3 倍になるなど、最近急上昇中の会社です。

最近では、AtCoder Jobs といわれる、AtCoder でのコンテスト成績で就職が有利になるサービスも話題になっており、競プロの実力を上げることが直接就職に役立つようになっています。

しかしながら、「競プロでどうやって上達すれば良いのかわからない」と思い悩んでいる方はとても多いと思います。その悩みも、実力帯ごとに異なり、

• 競プロ未経験者が何をやれば良いのか悩んでいる人もいる
• 競プロ成績上位に食い込むためには何をやれば良いのか悩んでいる人もいる
• 部活や社内などで、どういう競プロの教え方をすれば良いのか悩んでいる人もいる

と思います。そこで本記事では、

競技プログラミングで実力を上げるにはどういうことを学べば良いのか、どういう練習をすれば良いのかのガイドラインをレベル別に示し、上達に役立ててもらう

ことを最大の目標にします！

目次

初級編

中級編

上級編

1-1. 競プロとは何か

競プロとは、以下のようなものです。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。

つまり、プログラミングで解ける問題が何問か出されて、それぞれの問題について「この問題を解いたら何点獲得できるか」というものが決まっていて、2 時間などといった制限時間内でできるだけ多くの得点を獲得することが目的の競技です。（どんな問題が出されるかについては後述。以下の画像はコンテストの例です。）

競プロの特徴：自動採点

競技プログラミングの最大の特徴の一つとして、「ソースコードを出したらすぐに採点される」ということです。つまり、ソースコードをコンテストサイトに提出すると、通常 1 分以内に正解か不正解かわかります。

これが競技プログラミングの面白さの一つで、正誤がすぐにわかるだけでなく、リアルタイムで順位表が更新され、とても楽しいです。

どんな問題が出されるか（１）

さて、競技プログラミングではどのような問題が出されるのでしょうか。まずは簡単な例から紹介します。

整数 A$A$ と B$B$ が与えられます。
そのとき、縦 A$A$ センチ、横 B$B$ センチの長方形の周の長さを整数で出力してください。
テストデータの制約：1≤A,B≤100$1\le A,B\le 100$

このような問題を、作問者側が用意した全てのテストデータ（ここでは (A,B)$(A,B)$ の組）に対して正解するようなコードを書けば正解です。以下の例のように、1 ケースでも間違った出力をした場合、この提出は不正解となります。

このように、競技プログラミングはコーディングの正確性が問われるコンテストです。

どんな問題が出されるか（２）

競プロは正確性だけではありません。例えば、以下の問題を考えてみてください。

N$N$ 枚のカードが一列に並べられています。左から i$i$ 番目のカードには、整数 Ai$A_i$ が書かれています。あなたは N$N$ 枚のカードの中から 2$2$ 枚同時に選び、取ることができます。取った 2$2$ 枚に書かれた整数の合計がちょうど 101$101$ となるような、カードの選び方の通り数を求めてください。
テストデータの制約：1≤N≤106,1≤Ai≤109$1\le N\le {10}^6,1\le A_i\le {10}^9$

一番最初に考えられる解法は、以下のように「何枚目と何枚目を選ぶか全探索する」という方法だと思います。つまり、1≤i<j≤N$1\le i<j\le N$ を満たすすべての (i,j)$(i,j)$ の組を全探索し、Ai+Aj=101$A_i+A_j=101$ となる通り数を数え上げるという方法です。

しかし、その解法の場合、N2$N^2$ 回程度のループを回す必要があります。 N≤106$N\le {10}^6$ なので、最大 1012${10}^{12}$ 回程度のループを回す必要があります。しかし、競技プログラミングにおいて、およそ 108${10}^8$ ～ 109${10}^9$ 回を超える回数のループをした場合、実行時間超過 (TLE) となり、1 ケースでも TLE を起こすと不正解となってしまいます。

そのため、より効率的なアルゴリズムが考えられます。例えば、本問題であれば、以下のような解法を使うと、高々 N$N$ 回程度のループでプログラムの実行が終わります。

• Ai≥101$A_i\ge 101$ のカードはすべて無視する。
• Ai=1,Ai=2,...,Ai=100$A_i=1,A_i=2,...,A_i=100$ のカードの枚数を数える。それぞれ c1,c2,...,c100$c_1,c_2,...,c_{100}$ とする。
• そのとき、(c1×c100)+(c2×c99)+(c3×c98)+...+(c50×c51)$(c_1\times c_{100})+(c_2\times c_{99})+(c_3\times c_{98})+...+(c_{50}\times c_{51})$ が答えである。

一応、C++ での実装例を載せておきます。(2/20 01:28 AM. 一部修正しました)

#include <iostream>
#include <cstdio>
using namespace std;

long long N, A[1000009];
long long cnt[109];

int main() {
    scanf("%lld", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
        if (A[i] <= 100) cnt[A[i]]++;
    }

    long long Answer = 0;
    for (int i = 1; i <= 50; i++) Answer += cnt[i] * cnt[101 - i];
    cout << Answer << endl;
    return 0;
}

このように、コーディングの正確性だけでなく、現実的な実行時間に間に合わせるようなプログラムの書き方（アルゴリズム）を考えるというのが、競技プログラミングの本質です。競プロの世界は広く、今回説明した問題はまだ簡単な方です。競プロには、もっと解法が難しい問題はたくさんあります。²

1-2. 競プロの 6 つの面白さ

競技プログラミングについて知っていただいたところで、競プロが如何に面白いかを紹介します。競プロというのは、実はとてつもなく学びがいがあり、とてつもなく広く、とてつもなく面白いことなのです。

1-2-1. プログラミングスキルが向上する！

競技プログラミングでは、当然プログラムを早く正確に書くことが求められます。競プロをやると、コンテストに出たり過去問を解いたりすることで沢山のコードを書くので、コーディングに慣れ、スキルアップに直接繋がります。

実際に、競技プログラマーは、とてつもなく速くコーディングする能力を持っています。例えば、1-1. 節で紹介した 2 つ目の問題を解くプログラムを 2 分程度で書ける人も多いです。

また、後で紹介しますが、競プロでは C++ という言語がメジャーです。そのため、C++ 未経験の人にとっては、C++ というプログラミング言語を新たに学習する良い機会にもなるのです。（もちろん C++ 以外の言語で参加しても構いません）

1-2-2. アルゴリズムが学べる！

先程述べたように、競技プログラミングでは

• 「ただコードを速く正確に書く能力」　だけでなく、
• 「実行時間に間に合うような、効率的に動くプログラムを書く」

能力も求められます。そこで、様々なアルゴリズムを学習すると、効率的に動くプログラムが書きやすくなります。競技プログラミングは、アルゴリズムを学習・復習・学び直しする良い機会にもなるのです。

1-2-3. 数学的考察力が向上する！

一般に、AtCoder の問題をたくさん解いていくと、数学的考察力・論理的考察力が向上します。つまり数理パズルのような問題を簡単に解けるようになるのです。(2/20 00:57 AM　表記を一部修正)

では何故 AtCoder などのコーディングコンテストで、数学的考察力が磨けるのでしょうか？　この答えは競プロで出題されている問題にあります。競プロでは、

• アルゴリズムによって計算回数を少なくできる問題　だけでなく、
• 数学的考察によって計算回数を少なくできる問題

も多く出題されるからです。

1-2-4. リアルタイムで戦える！

先程述べたように、競技プログラミングでは自動採点のシステムが使われているため、順位表がリアルタイムで更新されます。その間、例えば AtCoder という日本最大手のコンテストサイトの場合、世界の5000人以上の参加者が同時に戦っています。

ですので、コーディングを高められるだけでなく、ネットゲーム（あるいは競技）としても十分楽しめるのです。

1-2-5. コミュニティーが優しい！

競プロが楽しい理由として、競プロコミュニティー（競プロ界隈）の優しさがあります。

例えば、初心者が Twitter で競プロのわからないことをツイートしたら、上級者が親切に答えを返してくれることも多いです。また、競プロをやっている人は、競プロ初学者に厳しく接することがほぼありません。そのため、楽しみながら上達することができます。

1-2-6. 就職に役立つ！

競技プログラミングは、前述したとおり、ネットゲーム感覚で楽しめるコンテスト（あるいは趣味）です。一方で、実は就職にも役立つことがあるのです。

日本最大手の競プロコンテストを開催する AtCoder では、コンテストに参加すると成績に応じてレーティングが付くのですが、そのレーティングが一定以上あれば、様々な会社の求人に応募できるというサービスがあります。

• AtCoder Jobs (jobs.atcoder.jp)

です。求人は年収が高いものが多く、競技プログラミングの能力で高い給料のエンジニア職に就ける、といったケースも多いです。

1-3. 早速競プロを始めてみよう

競プロの楽しさ、面白さはわかりましたでしょうか？

皆さんも、早速今日から競技プログラミングを始めてみましょう。本節では、どのようにして競プロを始めればよいのかを分かりやすく解説します。

1-3-1. AtCoder に登録しよう！

まず、日本最大手の競技プログラミング運営会社、

• AtCoder：競技プログラミングコンテストを開催する国内最大のサイト

に登録してみましょう。

AtCoder は、毎週土曜か日曜の 21 時からコンテストを開催するだけでなく、3000 問以上の競プロ過去問を解くことができるコンテストサイトです。競技プログラミングをやるにあたっては最適といって良いサービスですが、無料で登録できます。

1. https://atcoder.jp/ にアクセスします。

まず AtCoder を開かないと何も始まりません。

2. 「新規登録」をクリックします。

3. 様々な情報を入力します。

基本的には、ユーザー名・メールアドレス・パスワード・国籍を入力すれば良いです。所属は必須項目ではないので、個人情報はほとんど入力する必要がありません。

4. 登録完了です。

AtCoder への登録はこれで以上です。

1-3-2. AOJ に登録しよう！

AtCoder ほど重要ではないのですが、

• AIZU ONLINE JUDGE (AOJ)

という、競技プログラミングの問題を解くことができるサイトがあります。後述しますが、このサイトの何が良いのかというと、プログラミングの基礎やアルゴリズムがコースで学べるという点です。登録方法は、以下のようになります。（AOJ も無料で登録できます）

1. http://judge.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja にアクセスします。

サイトにアクセスすることが、すべてのはじまりです。

2. 「登録・設定」→「登録・設定」をクリックします。

そうすると「新規ユーザー登録」という画面が出てくると思います。

3. 様々な情報を入力します。

基本的には、ユーザーID・パスワード・名前・所属を入力すれば良いです。URL も入力する必要がありますが、ブログやホームページなど適切なものを入力すれば良いです。

4. 登録完了です。

AtCoder の登録と AOJ の登録、どちらが簡単でしたか？
両方ともパスワードを忘れないようにしましょう！（忘れたらすべての履歴が一からやり直しになってしまいます。悲しいです。）

1-3-3. AtCoder で一問解いてみよう！

AtCoder・AOJ への登録が済んだら、AtCoder で最初の一問を解いてみましょう。まず、AtCoder の問題の中で最も簡単なものの一つである、

• AtCoder Beginner Contest 145 A - Circle

を解いてみましょう。以下のような問題です。

整数 r$r$ が与えられます。
半径 r$r$ の円の面積は半径 1$1$ の円の面積の何倍か、整数で出力してください。つまり r×r$r\times r$ を出力してください。

手順 1: 問題ページにアクセスする

まずは問題ページを開いてください。
問題文が表示されると思います。

手順 2: コードを書く

コードを書いてください。例えば C++ の場合、以下のコードが正解例の一つです。

#include <iostream>
using namespace std;

int main() {
    int r;
    cin >> r;
    cout << r * r << endl;
    return 0;
}

手順 3: 問題画面の一番下までスクロールする

一番下までスクロールすると、以下のような画面が見られます。そこで、プログラミング言語を選び、ソースコードを貼り付け、「提出」ボタンを押してください。そうするとソースコードが提出できると思います。

手順 4: 提出結果を確認する

ソースコードを提出すると、自動的に「自分の提出」という画面に移ると思います。そこでしばらく待っていると、提出結果が出ます。

そこで AC が出ると正解となります。WA が出ると不正解です。他にも色々な提出結果があります。

皆さん、AtCoder の使い方は分かりましたか？

AtCoder は、初心者が簡単にサービスを使えるような環境が整えられています。例えば今回説明した、問題文を開いてからソースコードを提出するまでの流れは簡単だったと思います。それ以外にも、チュートリアルが整備されているなど、とても便利なコンテストサイトです！

1-4. 競プロをやる前に| AtCoder のレーティングとは

本題の「競プロ上達ガイドライン」に移る前に、本節で紹介するのは、

• AtCoder のレーティングシステム

です。

AtCoder のレーティングって何？

AtCoder は、毎週土曜日か日曜日に 2 時間程度のコンテストが開催されます。各コンテストには 3000～7000 人程度が参加します。そのコンテストの成績に応じて、各参加者にレーティングという値が付けられます。

つまり、レーティングはコンテストでの最近の平均的な成績、つまり実力を表した値だと思って良いです。

AtCoder のレーティングには、もう一つの特徴があります。

• レーティングに応じて、そのユーザーに色が付く

ことです。例えば、灰色コーダーからはじまり、最も強い人だと赤色コーダー（レッドコーダー）となります。具体的には、以下のようになります。

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

AtCoder のレーティングが持つ意味

AtCoder のレーティングには、主に 3 つの意味があります。

• 単純に、そのユーザーの実力の証明になる。
• AtCoder Jobs において、応募できる求人が決まってくる。（例えば、緑色コーダー以上になると、掲載されているうち 7 割程度の求人に応募できる）
• レーティングが高いと、一部のコンテストでレートが付かなくなる。（例えば、AtCoder Beginner Contest という初心者向けコンテストの場合、黄色コーダー以上になるとレートが付かなくなる。）

どうやってレーティングを見られるのか？

意外と知らない人も多いのですが、AtCoder の右上の自分のユーザー名が書かれているところをクリックして、そこから「マイプロフィール」をクリックすると、自分のレーティングが見られます。

以下のようなものが表示されると思います。

• コンテストに参加したことのある人：自分のレーティングと、レーティング変動グラフ
• コンテストに参加したことのない人：「Ratedコンテストにまだ参加していません。」という表示

ちなみに、プロフィールにある「コンテスト成績表」のリンクをクリックすると、各コンテストでどれだけ成功したのか、どれだけ失敗したのか、どれくらいのパフォーマンスを残したのかが分かるので、コンテストに参加した後に是非クリックしてみましょう。（注：レーティングが反映されるのには 15 分 ～ 1 時間かかります。）

AtCoder レーティングに関する重要な注意

AtCoder では、コンテスト参加回数の少ないうちは、レーティングが低く表示されます。例えば、初回のコンテストで大成功して、青色コーダー相応の結果を残したとしても、コンテスト参加後のレーティングは茶色になります。

ですので、最初の数回にレーティングが全然上がらなくても気にすることはありません。実際に、AtCoder のレーティングが完全に実力通りになるには、15 回程度コンテストに参加する必要があります。

さて、AtCoder 始めたての人には、まず灰色コーダーから脱出して、茶色コーダーになりたい、と目標を立てるのがよいでしょう。初級編では、茶色に短い期間でなるための道筋が記されておりますので、引き続きお読みいただけると嬉しいです。

1-5. 「茶色コーダー」で要求される 4 つのこと

AtCoder で茶色コーダー、つまりレーティング 400 に到達するためには、

• AtCoder Beginner Contest の A, B 問題が確実に（大方 15 分以内で）解ける
• AtCoder Beginner Contest の C 問題も簡単なものなら解ける

ことが要求されます。そのためには、以下の 4 つのことができれば良いと考えます。

条件 1

簡単なプログラムが書ける。具体的には、以下の 7 つを含むプログラムが書ける。（実は競技プログラミングは、それほど多くのプログラミング言語の知識がなくても十分戦えます。）

• 入力、出力
• 代入、単純な四則演算処理（+, -, *, /, = など）
• 条件分岐（if 文など）
• 繰り返し処理（for 文など）
• 文字列（string）
• 浮動小数点（double 型など）
• 配列（二次元配列も含む）

条件 2

• アルゴリズムとは何か
• 計算量（計算回数）とは何か

を理解する。そうすると、明らかに制限時間内に実行が終わらないソースコードを出さなくなる。ちなみに、競プロでは 108${10}^8$ ～ 109${10}^9$ 回程度のループが回せるといわれている。

条件 3

AtCoder Beginner Contest の A, B 問題において、「問題文の通りに実装すれば良い」ということを意識してコードを書けるようになる。

条件 4

「全探索」を実装できるようにする。

※ 実際に、AtCoder Beginner Contest の B 問題（200 点）の 70% 以上が、以下の 32 (2/19 11:24 PM 修正しました) つに分類できる。（他の 30% も本当に簡単な数学的知識があれば解ける）

• 問題文に書いてある通りに実装して解ける問題
  • ABC155-B, ABC154-B, ABC152-B, ABC148-B, ABC146-B　など
• あり得る可能性をすべて全探索して解ける問題
  • ABC151-B, ABC150-B, ABC144-B, ABC143-B　など

補足

上の 4 つの条件を満たすようになれば、AtCoder Beginner Contest の B 問題までは 9 割以上解けるようになると思います。

1-6. 節のガイドラインで後述しますが、C 問題も、コンテストに出まくったりして AtCoder に慣れることで、確率的に解けるようになると思います。

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

1-6. 「茶色コーダー」になるためのガイドライン

茶色コーダーに到達するためにやるべきことは、以下の 5 つだと考えています。

• ステップ 1: AOJ の「Introduction To Programming I」を全部解く！
• ステップ 2: 計算量とアルゴリズムが何か理解する！
• ステップ 3: 「AtCoder Beginners Selection」を解く！
• ステップ 4: 全探索に慣れる！
• ステップ 5: コンテストに出まくる！

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

1-6-1. AOJ の「Introduction To Programming I」を全部解く！

競プロは、簡単なプログラムを書けるようになるところから始まります。そこで、茶色コーダーになるまでに必要なプログラミング言語の知識と基本的なアルゴリズムを、まとめて学習できるコースがあります。

• AIZU ONLINE JUDGE - Introduction To Programming I

です。全部で 44 問ありますが、最後の 4 問は競プロとはあまり関係ないので、ITP1_1-A から ITP1_10-D までの 40 問を解くことをお勧めします。これらを解くと、少なくとも

• 茶色コーダーになるために必要なプログラミング言語の知識
• 茶色コーダーになるために必要なアルゴリズムの知識（全探索やシミュレーションなど）

は身につきます。ちなみに、「既にプログラミング言語を理解している」という人でも、AtCoder Beginner Contest の A 問題・B 問題相当の簡単なプログラムを書く練習になるので、やっておいた方が良いと思います。

1-6-2. 計算量とアルゴリズムが何か理解する！

競プロの本質といえるものが、「アルゴリズム」と「計算量」です。

AtCoder Beginner Contest の A 問題・B 問題を解いているうちは、プログラムの効率を意識しなくても解ける問題が多いです。しかし、茶色コーダーになるためには C 問題を半分くらいの確率で解く必要があるので、「アルゴリズムと計算量が何か」くらいは知っておくと良いと思います。そこで、読むべき記事が 2 つあります。

アルゴリズムを理解するためには？

• アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ by @drken

計算量を理解するためには？

• 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 by @drken

1-6-3. 「AtCoder Beginners Selection」を解く！

次にやるべきは、AtCoder の問題傾向をつかむことです。つまり、

• AtCoder の簡単な問題は大体何に分類されるのか

ということを知ることが大事です。そこで、

• AtCoder Beginner Selection

というものを解くことをお勧めします！　AtCoder Beginner Contest の A, B, C 問題に出てくるような簡単な問題の傾向がたったの 11 問でわかる、という点でとても教育的です。

なお、11 問中 8 問目以降は初心者にとっては少し難しいです。そこで、問題解説・コードの書き方などすべてが載っている記事があります。解法が分からない人はもちろん、全問解けた人も是非読みましょう。

• AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ by @drken

1-6-4. 全探索に慣れる！

AtCoder Beginner Contest の B 問題を確実に解き、C 問題も簡単なものなら解けるようにするためには、全探索を学習するのが一番速いです。まず、全探索とはどのようなものなのでしょうか。

あり得る状態をすべて列挙して、それぞれ調べ上げる。
つまり、「全パターンを調べ上げる」ということ。

例えば、以下の問題を考えてみましょう。（プログラミングコンテストチャレンジブック（蟻本）の最初に出てくる問題です。）

数字が書かれている N$N$ 枚の紙切れが袋に入っています。あなたはこの袋から紙切れを取り出し、数字を見て袋に戻すということを 4 回行い、4 回の数字の和が M$M$ になっていれば、あなたの勝ちです。紙切れに書かれている数字が {K1,K2,...,KN$K_1,K_2,...,K_N$} である場合、あなたが勝つような可能性はありますか。
制約：N≤50,M≤108,Ki≤108$N\le 50,M\le {10}^8,K_i\le {10}^8$

これは、1 回目に Ka$K_a$、2 回目に Kb$K_b$、3 回目に Kc$K_c$、4 回目に Kd$K_d$ を取り出すとして、(a,b,c,d)$(a,b,c,d)$ のあり得る組を全通り調べる（四重ループをする）と解けます。N4$N^4$ 回程度の計算が必要ですが、N≤50$N\le 50$ なので、およそ 504≒6.25×106${50}^4\fallingdotseq 6.25\times {10}^6$ 回のループしか回す必要がなく、実行時間制限には余裕をもって間に合います。

そう、こういう感じで全探索の問題が解けるのです！

4 種類の全探索

実は、全探索は 4 つの種類があります。

• 本当に全通り調べ上げる「全探索」
  • 前述の問題の、計算回数 N4$N^4$ 回のアルゴリズムがそれです。
  • 大体の場合、多重ループで解けます。
• 工夫して探索の通り数を減らす「全探索」
  • 例えば、前述の問題であれば、(a,b,c)$(a,b,c)$ の組を全通り調べ上げるとします。(a,b,c)$(a,b,c)$ の組が決まったら、後は Ad=M−Ka−Kb−Kc$A_d=M-K_a-K_b-K_c$ であるような d$d$ が存在するか調べれば良いです。予め長さ 108${10}^8$ の bool 型配列を定義し、1$1$ 以上 108${10}^8$ 以下の各整数が存在するかどうかを最初に記録しておけば、高速に調べられます。
  • 大体の場合、多重ループで上手くいきます。
• ビット全探索
  • 多重ループではうまくいかない全探索の 1 つです。
  • 詳しくは、こちらの記事を参照してください。
• 順列全探索
  • 多重ループではうまくいかない全探索の 1 つです。
  • 詳しくは、こちらの記事を参照してください。

全探索の問題

• AtCoder Beginner Contest 144 B - 81　基礎の基礎です。
• AtCoder Beginner Contest 150 B - Count ABC　全探索というか、「全通り調べ上げます」。
• AtCoder Beginner Contest 122 B - ATCoder　これも基本です。
• AtCoder Beginner Contest 136 B - Uneven Numbers　これも基本です。
• AtCoder Beginner Contest 106 B - 105　これも基本です。
• AtCoder Beginner Contest 120 B - K-th Common Divisors　単純な考察が必要ですが、基本です。
• AtCoder Beginner Contest 057 C - Digits in Multiplication　探索通り数を頑張って減らします。
• AtCoder Beginner Contest 095 C - Half and Half　探索通り数を頑張って減らします。
• 三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN　探索通り数を頑張って減らします。
• AtCoder Beginner Contest 128 C - Switches　ビット全探索の基本です。
• AtCoder Beginner Contest 147 C - HonestOrUnkind2　ビット全探索の基本です。
• AtCoder Beginner Contest 145 C - Average Length　順列全探索の基本です。
• AtCoder Beginner Contest 150 C - Count Order　順列全探索で解けます。
• AtCoder Beginner Contest 054 C - One-stroke Path　順列全探索で解けます。

1-6-5. コンテストに出まくる！

最後に、最も重要なことを書きます。これは、コンテストに出場することです。

AtCoder では、最初のレーティングが 0 であるため、コンテストに出場しなければレーティングが上がりません。仮に、あなたの実力が茶色コーダーの条件であるレーティング 400 より少し上だとしても、およそ 10回程度コンテストに出場しなければ茶色になれません。そのため、毎週コンテストに出続けることが重要です。

また、コンテストに出場することで、AtCoder の問題に慣れたり、問題の感覚がつかめたりするので、結果的に実力向上に繋がります。

つまり、コンテスト出場は AtCoder 実力向上の最大の近道です。

実際に、以下の表のように、コンテストに多く参加したほうがレーティングの中央値は圧倒的に高いです。（伸びるタイミングは人によって違うので、実際に何回か参加してみて中央値行かなくても全然気にしないでください。）

※ 2020/2/17 時点でのデータ。

コンテストの種類 / 初心者出るべきコンテスト

基本的に、AtCoder には 4 種類のコンテストがあります。

そのうち、初心者には「AtCoder Beginner Contest」に出場することがお勧めです。その他のコンテストにも出場して良いですが、1 問しか解けなかったりしてモチベ管理が大変になる場合があります。

ちなみに、キーエンスプログラミングコンテストや、ドワンゴからの挑戦状などの企業名が付いたコンテストがありますが、基本的には ABC クラスか ARC クラスのいずれかです。「コンテスト一覧」で青丸が付いていれば ABC クラス、橙丸が付いていれば ARC クラス、赤丸が付いていれば AGC クラスです。黒丸は非公式コンテストなど、レーティングが更新されないコンテストです。

モチベ管理こそが重要

競プロのコンテストでは、成功するときと失敗するときがあります。例えば、

• コンテストで失敗してレーティングを 50 下げてしまった。
• 最初の AtCoder Beginner Contest で 1 問しか正解できなかった。

などで、競プロをやめる人がとても多いのが現状です。実際に、AtCoder コンテストに参加したことがある人の約 6 割が参加回数 4 回以下です。でも、前述のとおり、コンテスト参加回数が多いほどレーティング中央値が上がります。人それぞれ、実力が伸びるタイミングは違いますが、モチベーションを維持して、楽しく競プロをやっていくことが大切です。

1-7. Tips: AtCoder の過去問を解ける便利なサイト

皆さんの中には、

コンテストに出るだけでは問題数が足りない！
もっと練習して実力を上げたい！

と思う人もいるのではないでしょうか。そこで、便利なサイトを紹介します。これは、

• AtCoder Problems

です！　AtCoder で解ける過去問が表形式でまとまっているだけでなく、自分のユーザー名を入れると、自分が各問題を既に正解しているかどうかが表示されます。過去問の検索だけでなく、コンテストに向けた練習の管理にも役立ちます。皆さん積極的に使っていきましょう。

1-8. おまけ：競プロにおける C++ のすすめ

AtCoder では、様々なプログラミング言語で競技を行うことができます。実際に、

• C++14
• Java
• Python
• C#
• Ruby

などを含む、50種類以上のプログラミング言語で提出をすることができます。もちろん多様性はあってよいのですが、最もやりやすいのは C++ だと思います。

C++ をすすめる理由

私が競プロに C++ をすすめる理由は、主に 3 つあります。

• AtCoder ユーザーの半数以上が C++ を使っている。³
• AtCoder 公式解説のソースコード、解説記事のソースコードの大半が C++ である。
• プログラミングコンテストチャレンジブック（蟻本）、プログラミングコンテスト攻略のためのアルゴリズムとデータ構造などの競プロ関連の本のほとんどで、サンプルソースコードとして C++ が使われている。
• 実行速度が他の言語に比べて高速であるため、競プロに有利である。実際に、Python のプログラムより C++ のプログラムの方が 4 倍以上多くのループを回せる。

C++ 以外をやってはいけないのか

プログラミング言語には多様性があるので、別に C++ 以外で競技をしても全く構いません。当然、最も書きやすい言語でコンテストに参加するのは良いことです。⁴

ただ、解説記事や競プロ関連本の多くは C++ で書かれているので、競プロをやる機会に C++ を学習して、少なくとも C++ のソースコードが読めるようにした方が、やりやすいと思います。

1-9. 本記事を終えた次は？

本記事の内容をマスターできれば、茶色コーダーになれると思います。茶色コーダーといったら、AtCoder の上位 4 割ですので、十分立派だと思います。

しかし、緑コーダーや水色コーダーになってみたい！　という夢を持つのはいいことです。初級編より高いレベルもフォローしてありますので、是非中級編・上級編もお読みください。

（初心者の方でも、競プロ中級者・上級者にはどんなアルゴリズム・知識・練習方法が求められるのか知る機会になるので、興味があれば是非お読みください。）

中級編

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

上級編

• レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】
  

-1. つづく

次は、中級編に続きます。