0. はじめに
この記事を最初に書いたのは 2018 年春です。
その頃と時代の変化もあったので全体的に書き直しました！
AtCoder の始め方については
に記載しています。
1. AtCoder レーティングの相場について
AtCoder のレーティングは以下のように色分けされています。レベル感の説明については、AtCoder 社長による見解を参考にしました。
- AtCoder 社長による参考ツイート (茶・緑・水色のレベル感)
- AtCoder 社長による参考ツイート (青・黄色のレベル感)
- AtCoder 社長による参考ツイート (青のレベル感)
| レーティング | 色 | AtCoderJobs ランク | レベル感 |
|---|---|---|---|
| 2800- | 赤 | SSS | 世界レベルのトップ選手です。現在日本に 20人 前後しかいません。 |
| 2400-2800 | 橙 | SS | 各大学で数年に 1 人レベルのトップ選手です。 |
| 2000-2400 | 黄 | S | 各大学のエース級選手です。世間的にはアルゴリズム特化のリサーチャーなど、エキスパートとして活躍できる実力です。 |
| 1600-2000 | 青 | A | 世間的にアルゴリズムスペシャリストとして活躍できる実力です。 |
| 1200-1600 | 水 | B | 世間的にソフトウェアエンジニアとしてトップレベルの実力です。 |
| 800-1200 | 緑 | C | ソフトウェアエンジニアとして大変優秀な実力です。 |
| 400-800 | 茶 | D | 各大学の情報系学部でしっかりとプログラミングを勉強している学生さんの実力です。 |
| 1-400 | 灰 | E | レーティング 200 以上になるためには、プログラミングに十分に慣れる必要があります。 |
また、各レーティングの人数分布は以下のようになっています:
(AtCoderの参加回数が多い人ほどレーティングが高い？より引用)
これを見ることで各色のレベル感が大まかに掴めると思います。ただし灰色のコーダーが非常に多く見えますが、それについては注意が必要です。AtCoder レーティングは参加回数が少ないうちは実力よりも大幅に低い値がつくようになっています。それは AtCoder においてリセマラのような手が有効でなくなるように、参加回数に応じた下方補正がかけられているからです。そのため、参加回数が 1 回のみの方はほぼ全員が灰色となってしまい、灰色のコーダーが非常に多い結果になっています。
- AtCoder 社長による参考ツイート (リセマラ封じ)
- AtCoder 社長による参考ツイート (初回は圧倒的に良かった人のみ茶色でそれ以外の方は灰色)
- AtCoder 社長による参考ツイート (10回参加するまではレーティングが低く出ている可能性が高い)
なお、補正をなくした場合の平均レーティングは 600〜700 (茶色上位相当) と言われています:
このように、AtCoder レーティングは参加回数が少ないうちは低めに出る傾向が強いため、レーティングとは別にパフォーマンスという値が算出 & 公開されています。パフォーマンスとはざっくり「コンテスト１回分のみのレーティングのようなもので、毎回そのパフォーマンスを取るとそのレーティングに収束する」という値です。コンテスト参加回数が数回のみで実レーティングが感覚よりも大分低いと感じたならば、パフォーマンス値を確認するのもとても有益です。
2. AtCoder Beginner Contest (ABC) について
2-1. コンテストの成績とパフォーマンスとの関係
コンテストに初めて参加するときには、誰もが「どのくらいの成績をとればいいんだろう...」と不安な気持ちになると思います。回によって難易度が違うので一概には言えないですが、ざっくり相場を伝えたいと思います。まず ABC では、A 問題から F 問題までの 6 問が出題されます。凄まじい難易度差です。
- A 問題: スコア 100 点であることが多い、簡単な文法の確認
- B 問題: スコア 200 点であることが多い、簡単な for 文、if 文を含む処理, Fizz Buzz と同程度
- C 問題: スコア 300 点であることが多い、計算量を意識したコーディングが求められるようになります
- D 問題: スコア 400 点であることが多い、ここから先はアルゴリズムの勉強も必要になってきます
- E 問題: スコア 500 点であることが多い、本格的な難しい問題です
- F 問題: スコア 600 点であることが多い、一気に難しくなります。黄色を目指すなら解きたい問題です
という感じです。パフォーマンスの相場はざっくりと、以下のような感じです。
| 出来 | パフォ | 備考 |
|---|---|---|
| A の 1 完 | 0 - 100 | まずは 2 完を目指しましょう |
| A, B の 2 完 | 100 ～ 300 | C まで頑張って解くことを目指しましょう |
| A, B, C の 3 完 | 200 ～ 1000 | 3 完が安定したら、速度を上げるか、D 問題に挑んでいきましょう |
| A, B, C, D の 4 完 | 800 ～ 1600 | D 問題が解けると、アルゴリズムを考えている感が強くなって、とても楽しくなります |
| A, B, C, D, E の 5 完 | 1400 ～ 2200 | ここから先はもはや Beginner 向けではないですね |
| A, B, C, D, E, F の 6 完 | 2000 ～ 2400 | 6000 人以上が参加する中で、100 人程度しか達成できない難易度です |
もちろん回によって難易度は異なりますので、あくまで目安になります。
2-2. 茶色を目指すためには
AtCoder を始めて最初の壁が、茶色 (レーティング 400 以上) になることだと思います。「茶色」のハードルは、将棋ウォーズでいえば 1 級相当 (ソース) のようです。茶色になるためには、以下の 3 つのうちのいずれか 1 つを達成することが必要だと思います。
- A～C の 3 問を早く解けるようにする (3 問合計で 30 分が目安です)
- 数学的な問題を解けるようにする (ABC 131 C - Anti-Division のような問題を解けるようにします)
- DFS, BFS といった基本的なアルゴリズムの知識を適用すれば解ける問題を解けるようにする
これらすべてを達成すれば緑色、1 つを達成すれば茶色というイメージです。なお、C 問題には独特のコツがあります。最も重要なのは
- 全探索に慣れる！！！
ということでしょう。@e869120 さんの以下の記事の「1-6-4. 全探索に慣れる！」のところに、全探索の練習問題がたっぷりリストアップされています。これを解いていきましょう！
3. AtCoder コンテストに参加するときの tips
コンテストに参加するための豆知識をまとめます。
3-1. ABC は大体土曜の 21 時から 100 分間！
コンテストに参加する上で「参加するつもりだったけどうっかり忘れてしまった」というのはしばしば起こりがちです。
- [AtCoder コンテスト予定表] (https://beta.atcoder.jp/contests/)
- (AtCoder に限らない) コンテストのカレンダー
で確認ができるのですが、ABC は土曜の 21 時スタートであることが多いです。時々日曜になるケースもあります。
3-2. 事前参加登録はいつでも OK！
コンテストサイトに行くと参加登録ボタンがあります。それを押すだけで参加登録完了です！超お手軽！！
そして、うっかりコンテストが始まってしまった後からでも参加登録ボタンを押して途中から参加することもできます。
3-3. 順位表は 「順位表」 タブで
コンテスト中に刻一刻と変化する順位表を眺めることができます。コンテストサイトに「順位表」タブがあるのでそこから見ることができます。具体的にどのように順位がつくのかはコンテストによって様々ですが、AtCoder の場合はおおむね「AC した合計ポイントの高い順」 -> 「同点の場合は最後に AC した時刻の早い順」で順位がつきます。これに WA によるペナルティの影響が加わります。
3-4. コンテスト中は問題に関することをつぶやかない！
AtCoder Beginner Contest のコンテスト時間は大体 100 分間であることが多いです。長いと感じる方もいるかもしれません。そして解ける問題がなくなったとき、ついつい SNS を開いてしまいがちです。
そこまではよいのですが、コンテストが終了する前の段階で、コンテストの問題に関することを呟いてしまうと、他の方のヒントになってしまう恐れがあります。とてもやりがちではあるのですが、「就職時のスキルの証明としての側面も持つレーティング」の信頼性を低下させてしまうことになりかねません。
目安として「順位表を見ればわかる情報」については呟いても良いようです。したがって「C 問題まで解けたー！」などは大丈夫ですが、「C 問題はよく考えれば簡単だった」などはダメのようです。
AtCoder のコンテストページの下に「ルール」という項目がありますので、そこを見ることで公式案内を確認することができます (下図は公式案内より)
3-5. コンテスト終了後には解説放送あり！
コンテストが終了した後には公式解説が 2 つの方法で展開されます:
- YouTube AtCoder チャンネル (非常に丁寧でわかりやすいです)
- 公式 editorial pdf (多くの場合、コンテスト終了後にコンテストページに「解説」タブが新設され、下図のような pdf がダウンロードできます)
少なくともはじめのうちは、YouTube の公式解説放送を視聴するのがとてもわかりやすくてよいと思います。慣れて来たら、公式解説 pdf や Twitter での議論のみで済まして時間節約する方法をとるのもよいでしょう。
3-6. 解説がどうしても理解できないとき
コンテスト中に解けなかった問題を次は解けるように復習することは、上達のために極めて大切なステップです。コンテスト終了直後に、まず最初にやりたいことは
- Twitter で、みんなのつぶやきを見る (AtCoder によく参加している人をフォローすると、コンテスト後に活発な議論を見ることができます)
- 解説 pdf を読む
といったあたりです。ここまでは気軽にできるでしょう。しかし、みんなのつぶやきを見ても、解説 pdf を読んでも、わからないことも多いと思います。解説 pdf は必要なアルゴリズム知識についてはすでに知っているものとして書かれていることが多いです。それは仕方のないことです。もし知識部分までカバーして解説を書こうとすると膨大な分量となりますし、似た問題を繰り返すたびに同じことを解説に含めるのは大変です。「他に資料がたくさんあるから、そこで勉強してください」ということになります。よって「他の資料の探し方」を知ることが重要になります。
解説放送
上でも挙げましたが、YouTube を用いた公式解説放送は、問題を解くために必要な知識から丁寧に解説しています。解説 pdf を読んでわからずとも、解説放送を聞くことで理解できることも多いでしょう！
コードを読む
他の方の提出したコードを読むと、何をしているのかが分かってくることも多々あります！
コツは「コンテスト中での提出時刻順にソートして、それが早いものを読む」です。もしくは誰かのファンになってその人の名前で検索してもよいでしょう！
検索
世の中には、個別の問題についての解説から、アルゴリズムの解説まで、たくさんの資料にあふれています。注意点をいくつか挙げます！
- たとえば ABC 154 の D 問題についての解説を調べたいときは「AtCoder ABC 154 Dice in Line」と検索しましょう！
ポイントは「検索に AtCoder という文字列を入れる」「問題のタイトルも入れる」です。問題タイトルだけで検索してしまうと、解説記事が 1 本か 2 本しか見つからないことになります。しかし、AtCoder を入れるだけで、驚くほど多くの記事が出て来ます！！！
kyopro_friends さんも「よくわからないことがあったら、10種類くらい解説を読んでみると、そのうち1つくらいは自分にとって分かりやすいものがあるはず」と言っています！一つの解説を読んでわからなくても、たくさん読めばきっとピンと来る瞬間があるはずです！
4. AtCoder 以外のコンテストの紹介
世界的には AtCoder 以外にも様々なコンテストがあります。それらを紹介して行きます。
4-1. 世界三大定期開催コンテスト
現在以下の 3 つが世界的にも三大定期開催コンテストと言えるでしょう:
- AtCoder: みなさんご存じの日本発のコンテスト運営会社です。
- Codeforces: ロシア発のコンテストサイト。世界的には最大規模。
- topcoder: 世界三大定期開催コンテストの中では最も歴史が長いです。
日本人としては日本語で参加できる AtCoder が魅力的であり、世界的にも良質の問題が出題されることで有名です。毎回の参加者数でも topcoder を凌ぎ、Codeforces に次ぐ位置にいます。Codeforces は、とにかく開催頻度の高さが魅力的です。AtCoder コンテストだけでは飽き足らない方は Codeforces にも出ていきましょう！Codeforces について、ぴーよさんの記事がとても参考になります。
4-2. 他の有名なコンテスト
何と言っても歴史が長いです。アメリカの計算機科学学会 ACM が主催していることもあり、大会の権威は随一とされています。大学対抗チーム戦で、三人一組のチームで闘います。日本ではまず国内予選を出場し、勝ち抜くとアジア大会に参加でき、そこで上位の成績をとると世界大会に出場することができます。
Google 社が毎年開催している世界規模のプログラミングコンテストです。何ラウンドかの予選を勝ち抜くと世界大会に出場することができます。
Facebook が毎年開催している世界規模のプログラミングコンテストです。何ラウンドかの予選を勝ち抜くと世界大会に出場することができます。
topcoder は定期開催コンテストサイトでもありますが、毎年世界規模のコンテストを開催しています。やはり何ラウンドかの予選を勝ち抜くと世界大会に出場することができます。
情報オリンピックというのを聞いたことがあるかもしれません。高校生以下が参加できるプログラミングコンテストで、JOI は日本情報オリンピックを指していて、予選/本選/日本代表選抜春合宿を勝ち抜くと、世界大会である IOI (国際情報オリンピック) に出場することができます。
公開されている問題を解くことで、ポイントを積み重ねていくサービスです。定期的にコンテストも開催されています。HackerRank を世界四大定期開催コンテストに含める考えもあると思います。
インド発のプログラミングコンテストサイトです。それなりに知名度は高いです。数学が好きな方には楽しい問題が出題される傾向にあります。また、CodeChef では一週間規模の期間をかけてアルゴリズム問題を解くコンテスト (Marathon Match とは別) も開催されていますので、短期決戦型のアルゴリズムコンテストが苦手な方は、楽しめる可能性もありそうです。
数学系の方だと、Project Euler から競技プログラミングのことを知った方も多いかもしれません。AtCoder などには参加していなくても Project Euler だけをやっているという方も多いです。数学系の問題が定期的に出題されています。
中国発のプログラミングコンテストサイトです。コンテスト環境が充実している日本の競技プログラマがあえて利用する機会はあまりないと思いますが、「一般グラフの最大マッチング」を verify できる問題があります。
4-3. オンラインジャッジ
様々なコンテストの過去問を集めたサイトが多々あります。日本では有名なものとして会津大学の運営している AOJ (Aizu Online Judge) があります。
既に上でも挙げましたが、AtCoder 上で出題された過去問を集めたサイトです。非公式ながら非常に洗練されたサイトです。
会津大学の運営しているオンラインジャッジです。AtCoder Problems に並んで日本人がよく利用しているサービスです。JOI 予選/本選の過去問や、ICPC に関連する過去問などが集められています。
数年前に yuki さんの個人運営によってはじまった「問題を投稿できるオンラインジャッジ」サービスです。みなが気軽に勉強しあえる場を作ろうというのがコンセプトで、誰でも気軽に作問して投稿することができます。集まった問題たちでコンテストも開催されています。皆の「こういう問題があったらいいなぁ」というのが集まっているサイトだと言えるでしょう。
北京大学の運営しているオンラインジャッジです。大昔、まだ AtCoder もなく、AOJ も盛んでなかった時代には、POJ がメジャーな精進場所でした。しかし現在では「計算実行が遅い」「他に日本語メインのサイトがある」などといった理由により、あまり使われなくなって来ています。現在では AtCoder / AOJ でほぼ十分と言えるでしょう。ただし、USACO (JOI のアメリカ版) の過去問たちは JOI と同様、良問がとても多いので是非解いておきたいところではあります。
POJ がメジャーな精進場所であった時代よりもさらに昔は UVa がメジャーだった時代もあるようです。
まだまだ色々あります。SPOJ は極めてマニアックな問題もあり、日本にもコアなファンのいるオンラインジャッジです。