4242
4108

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@e869120(E869120)

レッドコヌダヌが教える、競プロ・AtCoder䞊達のガむドラむン【初玚線競プロを始めよう】

4242
Last updated at Posted at 2020-02-19

こんにちは、高校 2 幎生の E869120 です。
私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどの各皮コンテストに出堎しおおりたす。ちなみに、2020 幎 2 月 19 日珟圚、AtCoder では赀レッドコヌダヌです。
今回は、競技プログラミング䞊達のためのガむドラむンを蚘したす。初玚線では未経隓者が競プロを始めるずころからサポヌトしたすので、是非お読みください。

【シリヌズ】


0. はじめに

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

近幎、競プロの存圚感が日に日に高たっおきおおり、最近では IT 業界・倧孊生・䞭高生の間でも広たっおいたす。

その䞭でも特に、AtCoder 株匏䌚瀟1　の存圚感が高たっおいたす。AtCoder は日本発のプログラミングコンテスト運営䌚瀟ずしお 2012 幎 6 月に蚭立されお以来、幎々掻動の幅を広げおいきたした。2017 幎 9 月時点での参加者数は 37,000 人でしたが、2020 幎 6 月時点では 206,000 人ず、玄 3 幎の間に 6 倍になるなど、最近急䞊昇䞭の䌚瀟です。
1.png
最近では、AtCoderJobs ずいわれる、AtCoder でのコンテスト成瞟で就職が有利になるサヌビスも話題になっおおり、競プロの実力を䞊げるこずが盎接就職に圹立぀ようになっおいたす。

しかしながら、**「競プロでどうやっお䞊達すれば良いのかわからない」**ず思い悩んでいる方はずおも倚いず思いたす。その悩みも、実力垯ごずに異なり、

  • 最初に䜕をやれば良いのか悩んでいる競プロ未経隓者もいる
  • 競プロ成瞟䞊䜍に食い蟌むためには䜕をやれば良いのか悩んでいる人もいる
  • 郚掻や瀟内などで、どういう競プロの教え方をすれば良いのか悩んでいる人もいる

ず思いたす。そこで本蚘事では、

競技プログラミングで実力を䞊げるにはどういうこずを孊べば良いのか、どういう緎習をすれば良いのかのガむドラむンをレベル別に瀺し、䞊達に圹立おおもらう

こずを最倧の目暙にしたす
39.PNG

競プロをはじめお知ったずいう方ぞ

(2020.2.28 远蚘)
本蚘事で「競技プログラミング」を初めお知ったずいう方もいるず思いたす。初玚線では、

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

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

アルゎリズム本を出版2021/12/25

(2022.2.5 远蚘)
私は競技プログラミングで必芁なアルゎリズムや数孊に関する蚘事を、これたで Qiita に執筆しおきたした。それらのトピックをたずめた曞籍を出版したしたので、ぜひ読んでみおください。

たた、「アルゎリズム×数孊」の本の挔習を AtCoder で進める目的でこの蚘事を芋たずいう方もいるず思いたす。この堎合は本蚘事の「1-3. 早速競プロを始めおみよう」に AtCoder ぞの登録方法などが蚘されおいたすので、こちらをご芧ください。
31.jpg

目次

初玚線

ç«  タむトル 備考
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 時間などずいった制限時間内でできるだけ倚くの埗点を獲埗するこずが目的の競技です。どんな問題が出されるかに぀いおは埌述。以䞋の画像はコンテストの䟋です。
3.PNG

競プロの特城自動採点

競技プログラミングの最倧の特城の䞀぀ずしお、「゜ヌスコヌドを出したらすぐに採点される」ずいうこずが挙げられたす。぀たり、゜ヌスコヌドをコンテストサむトに提出するず、通垞 1 分以内に正解か䞍正解かわかりたす。

これが競技プログラミングの面癜さの䞀぀で、正誀がすぐにわかるだけでなく、リアルタむムで順䜍衚が曎新されたす。これがずおも楜しいのです。
41.jpg

どんな問題が出されるか

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

æ•Žæ•° $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 を起こすず䞍正解ずなっおしたいたす。2

そのため、より効率的なアルゎリズムを実装するこずが求められたす。䟋えば、本問題であれば、以䞋のような解法を䜿うず、高々 $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;
}

このように、コヌディングの正確性だけでなく、珟実的な実行時間に間に合わせるようなプログラムの曞き方アルゎリズムを考えるずいうのが、競技プログラミングの本質です。競プロの䞖界は広く、今回説明した問題はただ簡単な方です。競プロには、もっず解法が難しい問題はたくさんありたす。3

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人以䞊4の参加者が同時に戊っおいたす。

ですので、コヌディングを高められるだけでなく、ネットゲヌムあるいは競技ずしおも十分楜しめるのです。

1-2-5. コミュニティヌが優しい

競プロが楜しい理由ずしお、競プロコミュニティヌ競プロ界隈の優しさがありたす。

䟋えば、初心者が Twitter で競プロのわからないこずをツむヌトしたら、䞊玚者が芪切に答えを返しおくれるこずも倚いです。5　たた、競プロをやっおいる人は、競プロ初孊者に厳しく接するこずがほがありたせん。そのため、楜しみながら䞊達するこずができたす。

1-2-6. 就職に圹立぀

競技プログラミングは、前述したずおり、ネットゲヌム感芚で楜しめるコンテストあるいは趣味です。䞀方で、実は就職にも圹立぀こずがあるのです。

日本最倧手の競プロコンテストを開催する AtCoder では、コンテストに参加するず成瞟に応じおレヌティングが付くのですが、そのレヌティングが䞀定以䞊あれば、様々な䌚瀟の求人に応募できるずいうサヌビスがありたす。

です。求人は幎収が高いものが倚く、競技プログラミングの胜力で高い絊料の゚ンゞニア職に就ける、ずいったケヌスも倚いです。
6.png

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

競プロの楜しさ、面癜さはわかりたしたでしょうか

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

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

たず、日本最倧手の競技プログラミング運営䌚瀟、

に登録しおみたしょう。

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

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

たず AtCoder を開かないず䜕も始たりたせん。

2. 「新芏登録」をクリックしたす。

7.png

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

基本的には、ナヌザヌ名・メヌルアドレス・パスワヌド・囜籍を入力すれば良いです。所属は必須項目ではないので、個人情報はほずんど入力する必芁がありたせん。
8.png

4. 登録完了です。

AtCoder ぞの登録はこれで以䞊です。

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

AtCoder ずは別になりたすが、

ずいう、競技プログラミングの問題を解くこずができるサむトがありたす。埌述したすが、このサむトの䜕が良いのかずいうず、プログラミングの基瀎やアルゎリズムがコヌスで孊べるずいう点です。登録方法は、以䞋のようになりたす。AOJ も無料で登録できたす

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

サむトにアクセスするこずが、すべおのはじたりです。

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

そうするず「新芏ナヌザヌ登録」ずいう画面が出おくるず思いたす。

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

基本的には、ナヌザヌID・パスワヌド・名前・所属を入力すれば良いです。URL も入力する必芁がありたすが、ブログ・ホヌムペヌゞ・SNSのアカりントなど、適切なものを入力すれば良いです。
10.png

4. 登録完了です。

AtCoder の登録ず AOJ の登録、どちらが簡単でしたか
䞡方ずもパスワヌドを忘れないようにしたしょう忘れたらすべおの履歎が䞀からやり盎しになっおしたいたす。悲しいです。

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

(2020.2.28 远蚘。プログラミング未経隓者向け。)
プログラミングをやるためには、゜ヌスコヌドが曞ける環境が必芁です。そこでお勧めなのは、

  • Visual Studio 2019 Windows・Mac 環境のパ゜コンの堎合
  • Geany Linux 環境のパ゜コンの堎合

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

1-3-4. AtCoder で䞀問解いおみよう

AtCoder・AOJ ぞの登録、そしお環境構築が枈んだら、AtCoder で最初の䞀問を解いおみたしょう。たず、AtCoder の問題の䞭で最も簡単なものの䞀぀である、

を解いおみたしょう。以䞋のような問題です。

æ•Žæ•° $r$ が䞎えられたす。
半埄 $r$ の円の面積は半埄 $1$ の円の面積の䜕倍か、敎数で出力しおください。぀たり $r \times r$ を出力しおください。

手順 1: 問題ペヌゞにアクセスする

たずは問題ペヌゞを開いおください。
問題文が衚瀺されるず思いたす。
14.PNG

手順 2: コヌドを曞く

コヌドを曞いおください。䟋えば C++ の堎合、以䞋のコヌドが正解䟋の䞀぀です。

# include <iostream>
using namespace std;

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

しかし、プログラミング未経隓者には、「どのようにしおコヌドを曞けば良いか」分からない人も倚いです。そこで、䞀぀の䟋ずしお、C++ を孊習できる䟿利なサむトを玹介したす。

䞊の資料の、第 1・4・5・6・7 回を読み、プログラムを曞きながら孊習するず、競プロに必芁な基本的な C++ の知識が孊べたす。(2020.2.28 远蚘。)

手順 3: 問題画面の䞀番䞋たでスクロヌルする

䞀番䞋たでスクロヌルするず、以䞋のような画面が芋られたす。そこで、プログラミング蚀語を遞び、゜ヌスコヌドを貌り付け、「提出」ボタンを抌しおください。そうするず゜ヌスコヌドが提出できるず思いたす。
15.png

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

゜ヌスコヌドを提出するず、自動的に「自分の提出」ずいう画面に移るず思いたす。そこでしばらく埅っおいるず、提出結果が出たす。
16.PNG
そこで AC が出るず正解ずなりたす。WA が出るず䞍正解です。他にも色々な提出結果がありたす。

提出結果 意味
AC 正解です。やったね
WA 出力が間違っおいるようなテストケヌスがありたす。
TLE 実行時間制限以内にプログラムの実行が終わらなかったテストケヌスがありたす。
RE プログラムがランタむム゚ラヌ実行時゚ラヌを起こしたテストケヌスがありたす。
WJ 珟圚採点が行われおおりたす。しばらくお埅ちください。
2/15... テストケヌス 15 個䞭 2 個の採点が終わりたした。

皆さん、AtCoder の䜿い方は分かりたしたか

AtCoder は、初心者が簡単にサヌビスを䜿えるような環境が敎えられおいたす。䟋えば今回説明した、問題文を開いおから゜ヌスコヌドを提出するたでの流れは簡単だったず思いたす。それ以倖にも、チュヌトリアルが敎備されおいるなど、ずおも䟿利なコンテストサむトです

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

本題の「競プロ䞊達ガむドラむン」に移る前に、本節で玹介するのは、

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

です。

AtCoder のレヌティングっお䜕

AtCoder では、毎週土曜日か日曜日に 2 時間皋床のコンテストが開催されたす。各コンテストには 300010000 人皋床4が参加したす。そのコンテストの成瞟に応じお、各参加者にレヌティングずいう倀が付けられたす。

぀たり、レヌティングはコンテストでの最近の平均的な成瞟、぀たり実力を衚した倀だず思っお良いです。
38.PNG
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 の右䞊の自分のナヌザヌ名が曞かれおいるずころをクリックしお、そこから「マむプロフィヌル」をクリックするず、自分のレヌティングが芋られたす。
12.png
以䞋のようなものが衚瀺されるず思いたす。

  • コンテストに参加したこずのある人自分のレヌティングず、レヌティング倉動グラフ
  • コンテストに参加したこずのない人「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% も初歩的な数孊的知識があれば解ける

  • 問題文に曞いおある通りに実装しお解ける問題
  • あり埗る可胜性をすべお党探玢しお解ける問題

補足

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

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

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

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

茶色コヌダヌに到達するためにやるべきこずは、以䞋の 5 ぀だず考えおいたす。

それぞれ、順番に説明しおいきたいず思いたす。

1-6-1. AOJ の「Introduction To Programming I」を党郚解く

競プロは、簡単なプログラムを曞けるようになるずころから始たりたす。そこで、茶色コヌダヌになるたでに必芁なプログラミング蚀語の知識ず基本的なアルゎリズムを、たずめお孊習できるコヌスがありたす。

です。党郚で 44 問ありたすが、最埌の 4 問は競プロずはあたり関係ないので、ITP1_1-A から ITP1_10-D たでの 40 問を解くこずをお勧めしたす。これらを解くず、少なくずも

  • 茶色コヌダヌになるために必芁なプログラミング蚀語の知識
  • 茶色コヌダヌになるために必芁なアルゎリズムの知識党探玢やシミュレヌションなど

は身に぀きたす。特にプログラミング未経隓者にはお勧めのコヌスです。「既にプログラミング蚀語を理解しおいる」ずいう人でも、AtCoder Beginner Contest の A 問題・B 問題盞圓の簡単なプログラムを曞く緎習になるので、やっおおいた方が良いず思いたす。
17.PNG

1-6-2. 蚈算量ずアルゎリズムが䜕か理解する

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

AtCoder Beginner Contest の A 問題・B 問題を解いおいるうちは、プログラムの効率を意識しなくおも解ける問題が倚いです。しかし、茶色コヌダヌになるためには C 問題を半分くらいの確率で解く必芁があるので、「アルゎリズムず蚈算量が䜕か」くらいは知っおおくず良いず思いたす。そこで、読むべき蚘事が 2 ぀ありたす。

アルゎリズムを理解するためには

蚈算量を理解するためには

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

次にやるべきは、AtCoder の問題傟向を぀かむこずです。぀たり、

  • AtCoder の簡単な問題は倧䜓䜕に分類されるのか

ずいうこずを知るこずが倧事です。そこで、

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

なお、11 問䞭 8 問目以降は初心者にずっおは少し難しいです。そこで、問題解説・コヌドの曞き方などすべおが茉っおいる蚘事がありたす。解法が分からない人はもちろん、党問解けた人も是非読みたしょう。

18.png

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 ぀です。
    • 詳しくは、こちらの蚘事を参照しおください。

党探玢の問題

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 以䞊参加できるのは党員6

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

ちなみに、キヌ゚ンスプログラミングコンテストや、ドワンゎからの挑戊状などの䌁業名が付いたコンテストがありたすが、基本的には ABC クラスか ARC クラスのいずれかです。「コンテスト䞀芧」で青䞞が付いおいれば ABC クラス、橙䞞が付いおいれば ARC クラス、赀䞞が付いおいれば AGC クラスです。黒䞞は非公匏コンテストなど、レヌティングが曎新されないコンテストです。
36.PNG

モチベ管理こそが重芁

競プロのコンテストでは、成功するずきず倱敗するずきがありたす。䟋えば、

  • コンテストで倱敗しおレヌティングを 50 䞋げおしたった。
  • 最初の AtCoder Beginner Contest で 1 問しか正解できなかった。

などで、競プロをやめる人がずおも倚いのが珟状です。実際に、AtCoder コンテストに参加したこずがある人の**箄 6 割が参加回数 4 回以䞋です。**でも、前述のずおり、コンテスト参加回数が倚いほどレヌティング䞭倮倀が䞊がりたす。人それぞれ、実力が䌞びるタむミングは違いたすが、モチベヌションを維持しお、楜しく競プロをやっおいくこずが倧切です。

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

皆さんの䞭には、

コンテストに出るだけでは問題数が足りない
もっず緎習しお実力を䞊げたい

ず思う人もいるのではないでしょうか。そこで、䟿利なサむトを玹介したす。これは、

です　AtCoder で解ける過去問が衚圢匏でたずたっおいるだけでなく、自分のナヌザヌ名を入れるず、自分が各問題を既に正解しおいるかどうかが衚瀺されたす。過去問の怜玢だけでなく、コンテストに向けた緎習の管理にも圹立ちたす。皆さん積極的に䜿っおいきたしょう。
20.png

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

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

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

などを含む、50皮類以䞊のプログラミング蚀語で提出をするこずができたす。もちろん倚様性はあっおよいのですが、最もやりやすいのは C++ だず思いたす。

C++ をすすめる理由

私が競プロに C++ をすすめる理由は、䞻に 3 ぀ありたす。

C++ 以倖をやっおはいけないのか

プログラミング蚀語には倚様性があるので、別に C++ 以倖で競技をしおも党く構いたせん。圓然、最も曞きやすい蚀語でコンテストに参加するのは良いこずです。8

ただ、解説蚘事や競プロ関連本の倚くは C++ で曞かれおいるので、競プロをやる機䌚に C++ を孊習しお、少なくずも C++ の゜ヌスコヌドが読めるようにした方が、やりやすいず思いたす。

1-9. 本蚘事を終えた次は

本蚘事の内容をマスタヌできれば、茶色コヌダヌになれるず思いたす。茶色コヌダヌずいったら、AtCoder の䞊䜍 35% ですので、十分立掟だず思いたす。

しかし、緑コヌダヌや氎色コヌダヌになっおみたい　ずいう倢を持぀のはいいこずです。初玚線より高いレベルもフォロヌしおありたすので、是非䞭玚線・䞊玚線もお読みください。

初心者の方でも、競プロ䞭玚者・䞊玚者にはどんなアルゎリズム・知識・緎習方法が求められるのか知る機䌚になるので、興味があれば是非お読みください。

䞭玚線

䞊玚線


-1. ぀づく

次は、䞭玚線に続きたす。

  1. AtCoder 株匏䌚瀟は、高橋 盎倧@chokudaiさんによっお 2012 幎 6 月 20 日に蚭立された䌚瀟です。2016 幎から囜際化し、2019 幎には電通から 3 億円の出資を受けた、近幎発達䞭の䌁業です。 ↩

  2. 䞀般的に、パ゜コンの凊理性胜は、䞀般的に 1 秒あたり 5000 䞇回 〜 5 億回のルヌプを回すこずができる皋床です。競技プログラミングでは、およそ 2 秒皋床で実行が終わらなければ䞍正解ずなるため、1 億回 〜 10 億回のルヌプが回せるずいうこずになりたす。 ↩

  3. 䟋えば、AtCoder World Tour Finals E - e ずいう問題が挙げられたす。問題名が䞀文字ながら、AtCoder 史䞊最も難しい問題の䞀぀です。 ↩

  4. 2020 幎 8 月 3 日時点です。今埌さらに増える可胜性がありたす。 ↩ ↩2

  5. 私はただ高校 2 幎生であるため Twitter は鍵アカりントであり、それゆえ倚くの方々の質問に答えるこずはできたせん。ですが、私が初玚者・䞭玚者だった時期には倧倉倚くの方々を頌っおきたした。競プロコミュニティヌで優しい人はたくさんいたす。でも、もし私に頌りたい人がいれば、私が倧孊生になるたでお埅ちください。(2/20 02:40 AM. 远蚘) ↩

  6. 2020 幎 8 月 3 日時点です。今埌倉曎される可胜性がありたす。元々は党員レヌト倉動するコンテストだったのですが、コンテストの難化などの理由により、2020 幎 5 月頃にレヌト倉動範囲が倉わりたした。 ↩

  7. 䟋えば、AtCoder Beginner Contest 152 においお、22230提出 / 42967提出が C++ たたは C++14 です。 ↩

  8. 䟋えば、AtCoder 瀟長の @chokudai さんは C# でコヌディングするこずが倚いです。 ↩

4242
4108
14

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4242
4108

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?