More than 1 year has passed since last update.

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

Last updated at 2022-02-05Posted at 2020-02-19

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

【シリーズ】

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

0. はじめに

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

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

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

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

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

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

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

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

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

競プロをはじめて知ったという方へ

(2020.2.28 追記)
本記事で「競技プログラミング」を初めて知ったという方もいると思います。初級編では、

「競技プログラミング」がどういうものなのか。
学習していくことによって、どういうメリットがあるのか。
どのようにして競技プログラミングを始められるのか

から紹介しておりますので、ご安心ください。本教材では、仮にプログラミング未経験者であっても、競技プログラミングが始められるよう、サポートしております。

アルゴリズム本を出版！（2021/12/25）

(2022.2.5 追記)
私は競技プログラミングで必要なアルゴリズムや数学に関する記事を、これまで Qiita に執筆してきました。それらのトピックをまとめた書籍を出版しましたので、ぜひ読んでみてください。

Amazon｜「アルゴリズム×数学」が基礎からしっかり身につく本

また、「アルゴリズム×数学」の本の演習を AtCoder で進める目的でこの記事を見たという方もいると思います。この場合は本記事の「1-3. 早速競プロを始めてみよう」に 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.	おわりに

1-1. 競プロとは何か

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

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

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

競プロの特徴：自動採点

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

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

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

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

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

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

テストケース番号	#1	#2	#3	#4	#5
$(A, B)$	(4, 5)	(1, 9)	(6, 7)	(31, 27)	(100, 100)
想定解	18	20	26	116	400
あなたの出力	18	20	26	112	400
正誤	〇	〇	〇	×	〇

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

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

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

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

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

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

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

$A_i \geq 101$ のカードはすべて無視する。
$A_i = 1, A_i = 2, ..., A_i = 100$ のカードの枚数を数える。それぞれ $c_1, c_2, ..., c_{100}$ とする。
そのとき、$(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 という日本最大手のコンテストサイトの場合、世界の10000人以上⁴の参加者が同時に戦っています。

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

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

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

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

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

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

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

AtCoderJobs (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 も入力する必要がありますが、ブログ・ホームページ・SNSのアカウントなど、適切なものを入力すれば良いです。

4. 登録完了です。

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

1-3-3. 競プロのための環境構築について

(2020.2.28 追記。プログラミング未経験者向け。)
プログラミングをやるためには、ソースコードが書ける環境が必要です。そこでお勧めなのは、

Visual Studio 2019 （Windows・Mac 環境のパソコンの場合）
Geany （Linux 環境のパソコンの場合）

です。その中でも、Visual Studio において、プログラムを C++ で実行するところまで詳しく解説された記事があるので、以下の記事をお読みください。

cp-1. Microsoft Visual Studio 2019 C++ の使い方

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

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

AtCoder Beginner Contest 145 A - Circle

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

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

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

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

手順 2: コードを書く

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

#include <iostream>
using namespace std;

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

しかし、プログラミング未経験者には、「どのようにしてコードを書けば良いか」分からない人も多いです。そこで、一つの例として、C++ を学習できる便利なサイトを紹介します。

非情報系学生のための C/C++ 入門

上の資料の、第 1・4・5・6・7 回を読み、プログラムを書きながら学習すると、競プロに必要な基本的な C++ の知識が学べます。(2020.2.28 追記。)

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

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

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

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

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

提出結果	意味
AC	正解です。やったね！
WA	出力が間違っているようなテストケースがあります。
TLE	実行時間制限以内にプログラムの実行が終わらなかったテストケースがあります。
RE	プログラムがランタイムエラー（実行時エラー）を起こしたテストケースがあります。
WJ	現在採点が行われております。しばらくお待ちください。
2/15...	テストケース 15 個中 2 個の採点が終わりました。

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

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

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

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

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

です。

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

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

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

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

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

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

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

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

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

を理解する。そうすると、明らかに制限時間内に実行が終わらないソースコードを出さなくなる。ちなみに、競プロでは $10^{8}$ ～ $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-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$ 枚の紙切れが袋に入っています。あなたはこの袋から紙切れを取り出し、数字を見て袋に戻すということを 4 回行い、4 回の数字の和が $M$ になっていれば、あなたの勝ちです。紙切れに書かれている数字が {$K_1, K_2, ..., K_N$} である場合、あなたが勝つような可能性はありますか。
制約：$N \leq 50, M \leq 10^{8}, K_i \leq 10^{8}$

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

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

4 種類の全探索

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

本当に全通り調べ上げる「全探索」
- 前述の問題の、計算回数 $N^4$ 回のアルゴリズムがそれです。
- 大体の場合、多重ループで解けます。
工夫して探索の通り数を減らす「全探索」
- 例えば、前述の問題であれば、$(a, b, c)$ の組を全通り調べ上げるとします。$(a, b, c)$ の組が決まったら、後は $A_d = M-K_a-K_b-K_c$ であるような $d$ が存在するか調べれば良いです。予め長さ $10^{8}$ の bool 型配列を定義し、$1$ 以上 $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 実力向上の最大の近道です。

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

参加回数	レーティングの中央値
1 回	15
2 回	62
5 回	241
10 回	521
20 回	884
100 回以上 (参考)	1657
※ 2020/2/17 時点でのデータ。

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

基本的に、AtCoder には 4 種類のコンテストがあります。
(2020/08/03 AGC のレート変動範囲を修正 (更新) しました)

コンテスト	問題数	時間	レート変動対象
AtCoder Beginner Contest (ABC)	6 問	100 分	0 ～ 1999
AtCoder Regular Contest (ARC)	6 問	120 分程度	0 ～ 2799
AtCoder Grand Contest (AGC)	6 問	150 分程度	1200 以上（参加できるのは全員）⁶

そのうち、初心者には「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 の上位 35% ですので、十分立派だと思います。

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

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

中級編

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

上級編

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

-1. つづく

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

AtCoder 株式会社は、高橋直大（@chokudai）さんによって 2012 年 6 月 20 日に設立された会社です。2016 年から国際化し、2019 年には電通から 3 億円の出資を受けた、近年発達中の企業です。 ↩
一般的に、パソコンの処理性能は、一般的に 1 秒あたり 5000 万回〜 5 億回のループを回すことができる程度です。競技プログラミングでは、およそ 2 秒程度で実行が終わらなければ不正解となるため、1 億回〜 10 億回のループが回せるということになります。 ↩
例えば、AtCoder World Tour Finals E - e という問題が挙げられます。問題名が一文字ながら、AtCoder 史上最も難しい問題の一つです。 ↩
2020 年 8 月 3 日時点です。今後さらに増える可能性があります。 ↩ ↩²
私はまだ高校 2 年生であるため Twitter は鍵アカウントであり、それゆえ多くの方々の質問に答えることはできません。ですが、私が初級者・中級者だった時期には大変多くの方々を頼ってきました。競プロコミュニティーで優しい人はたくさんいます。でも、もし私に頼りたい人がいれば、私が大学生になるまでお待ちください。(2/20 02:40 AM. 追記) ↩
2020 年 8 月 3 日時点です。今後変更される可能性があります。（元々は全員レート変動するコンテストだったのですが、コンテストの難化などの理由により、2020 年 5 月頃にレート変動範囲が変わりました。） ↩
例えば、AtCoder Beginner Contest 152 において、22230提出 / 42967提出が C++ または C++14 です。 ↩
例えば、AtCoder 社長の @chokudai さんは C# でコーディングすることが多いです。 ↩

3955

3898

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

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

0. はじめに

競プロをはじめて知ったという方へ

アルゴリズム本を出版！（2021/12/25）

目次

初級編

中級編

上級編

1-1. 競プロとは何か

競プロの特徴：自動採点

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. 登録完了です。

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

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

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

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

4. 登録完了です。

1-3-3. 競プロのための環境構築について

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

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

手順 2: コードを書く

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

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

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

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

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

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

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

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

条件 1

条件 2

条件 3

条件 4

補足

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

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

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

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

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

4 種類の全探索

全探索の問題

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

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

モチベ管理こそが重要

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

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

C++ をすすめる理由

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

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

中級編

上級編

-1. つづく