アルゴリズム
AtCoder
競技プログラミング
プログラミングコンテスト
新人プログラマ応援

長くなったので

から一部分けました。

AtCoder レーティングの相場について

AtCoder のレーティングは以下のように色分けされています。レベル感の説明については、AtCoder 社長による見解を参考にしました。

レーティング AtCoderJobs ランク レベル感
2800- SSS 世界レベルのトップ選手です。現在日本に 20人 前後しかいません。
2400-2800 SS 各大学で数年に 1 人レベルのトップ選手です。
2000-2400 S 各大学のエース級選手です。世間的にはアルゴリズム特化のリサーチャーなど、エキスパートとして活躍できる実力です。
1600-2000 A 世間的にはアルゴリズムスペシャリストとして活躍できる実力です。
1200-1600 B 世間的にはソフトウェアエンジニアとしてトップレベルの実力です。Paiza の S ランクと同等とされています。
800-1200 C ソフトウェアエンジニアとして申し分ない実力です。
400-800 D 各大学の情報系学部でしっかりとプログラミングを勉強して上位 3 割の成績を収めている学生さんの実力です
1-400 E 初心者ですが伸びしろがたくさんある状態です

また、各レーティングの人数分布は以下のようになっています:

AtCoderレーティング分布.png
(AtCoderの参加回数が多い人ほどレーティングが高い?より引用)

これを見ることで各色のレベル感が大まかに掴めると思います。ただし灰色のコーダーが非常に多く見えますが、それについては注意が必要です。AtCoder レーティングは参加回数が少ないうちは実力よりも大幅に低い値がつくようになっています。それは AtCoder においてリセマラのような手が有効でなくなるように、参加回数に応じた下方補正がかけられているからです。そのため、参加回数が 1 回のみの方はほぼ全員が灰色となってしまい、灰色のコーダーが非常に多い結果になっています。

なお、補正をなくした場合の平均レーティングは 600〜700 (茶色上位相当) と言われています:

このように、AtCoder レーティングは参加回数が少ないうちは低めに出る傾向が強いため、レーティングとは別にパフォーマンスという値が算出 & 公開されています。パフォーマンスとはざっくり「コンテスト1回分のみのレーティングのようなもので、毎回そのパフォーマンスを取るとそのレーティングに収束する」という値です。コンテスト参加回数が数回のみで実レーティングが感覚よりも大分低いと感じたならば、パフォーマンス値を確認するのもとても有益です。

ABC でどの程度解けるとどの程度のパフォーマンスが出るか

初めて参加するときには誰もが気になることだと思います。回によって難易度が違うので一概には言えないですが、ざっくり相場を伝えたいと思います。まず ABC は A 問題から D 問題までの 4 問が出題され、

  • A 問題: スコア 100 点であることが多い、簡単な文法の確認
  • B 問題: スコア 200 点であることが多い、簡単な for 文、if 文を含む処理, Fizz Buzz と同程度
  • C 問題: スコア 300 点であることが多い、一気に難易度が上がります
  • D 問題: スコア 400 点または 500 点、ここまで来ると大分難しいです

という感じです。パフォーマンスの相場はざっくりと

出来 パフォ 備考
A の 1 完 -600 ~ 0 まずは 2 完を目指しましょう
A, B の 2 完 0 ~ 600 C が解けるようになると楽しくなります
A, B, C の 3 完 600 ~ 1200 スピードに依ります、幅が広いです
A, B, C, D の 4 完 1200 ~ 1600 D が解けるなら ABC は卒業です

という感じです。もちろん回によって難易度は異なりますので、あくまで目安になります。

AtCoder コンテストに参加するときの tips

ABC は大体土曜の 21 時から 100 分間!

コンテストに参加する上で「参加するつもりだったけどうっかり忘れてしまった」というのはしばしば起こりがちです。

で確認ができるのですが、ABC は土曜の 21 時スタートであることが多いです。時々日曜になるケースもあります。

事前参加登録はいつでも OK!

コンテストサイトに行くと参加登録ボタンがあります。それを押すだけで参加登録完了です!超お手軽!!
そして、うっかりコンテストが始まってしまった後からでも参加登録ボタンを押して途中から参加することもできます。

スクリーンショット 2018-03-09 23.23.16.png

順位表は 「順位表」 タブで

コンテスト中に刻一刻と変化する順位表を眺めることができます。コンテストサイトに「順位表」タブがあるのでそこから見ることができます。具体的にどのように順位がつくのかはコンテストによって様々ですが、AtCoder の場合はおおむね「AC した合計ポイントの高い順」 -> 「同点の場合は最後に AC した時刻の早い順」で順位がつきます。これに WA によるペナルティの影響が加わります。

スクリーンショット 2018-03-09 23.22.05.png

コンテスト終了後には解説放送あり!

コンテストが終了した後には公式解説が 2 つの方法で展開されます:

  • YouTube AtCoder チャンネル (世界大会で何度も優勝しているレジェンドなりんごさん達による解説です)
  • 公式 editorial pdf (多くの場合、コンテスト終了後にコンテストページに「解説」タブが新設され、下図のような pdf がダウンロードできます)

少なくともはじめのうちは、YouTube の公式解説放送を視聴するのがとてもわかりやすくてよいと思います。慣れて来たら、公式解説 pdf や Twitter での議論のみで済まして時間節約する方法をとるのもよいでしょう。

スクリーンショット 2018-03-09 23.24.38.png

ABC を卒業して ARC へと移るタイミング

意見が分かれるところだと思います。目安として、茶上位 (600〜800) から緑 (800〜1200) になった辺りのタイミングで ARC への移行が薦められ、水色 (1200〜1600) になったらもう ABC は完全卒業 (水色以上は ABC に参加してもレーティングがつかない) です。ただ 1 つ注意点として、


  • ABC ではどれほど順位がよくてもパフォーマンスの上限が 1600 に設定されている
  • 初回参加時につくレーティングの上限は 400 である

というのが挙げられます。つまり本来なら AtCoder 青色以上に相当するパフォーマンスをとったとしても、初回の ABC では 400 以下のレーティングしかつかないです。

もし初回で 400 近いレーティングが得られたならば、次回以降は ARC に参加するのがよいと思います。

AtCoder 以外のコンテストの紹介

世界的には AtCoder 以外にも様々なコンテストがあります。それらを紹介して行きます。

世界四大定期開催コンテスト

現在以下の 4 つが世界的にも四大定期開催コンテストと言えるでしょう:

  • AtCoder: みなさんご存じの日本発のコンテスト運営会社です。
  • Codeforces: ロシア発のコンテストサイト。世界的には最大規模。
  • topcoder: 世界四大定期開催コンテストの中では最も歴史が長いです。
  • CS Academy: 新しいです。四大コンテストの中で問題の質は高めです。

日本人としては日本語で参加できる AtCoder が魅力的であり、世界的にも良質の問題が出題されることで有名です。毎回の参加者数でも topcoder を凌ぎ、Codeforces に次ぐ位置にいます。

他の有名なコンテスト

何と言っても歴史が長いです。アメリカの計算機科学学会 ACM が主催していることもあり、大会の権威は随一とされています。大学対抗チーム戦で、三人一組のチームで闘います。日本ではまず国内予選を出場し、勝ち抜くとアジア大会に参加でき、そこで上位の成績をとると世界大会に出場することができます。

Google 社が毎年開催している世界規模のプログラミングコンテストです。何ラウンドかの予選を勝ち抜くと世界大会に出場することができます。

Facebook が毎年開催している世界規模のプログラミングコンテストです。何ラウンドかの予選を勝ち抜くと世界大会に出場することができます。

topcoder は定期開催コンテストサイトでもありますが、毎年世界規模のコンテストを開催しています。やはり何ラウンドかの予選を勝ち抜くと世界大会に出場することができます。 

情報オリンピックというのを聞いたことがあるかもしれません。高校生以下が参加できるプログラミングコンテストで、JOI は日本情報オリンピックを指していて、予選/本選/日本代表選抜春合宿を勝ち抜くと、世界大会である IOI (国際情報オリンピック) に出場することができます。

公開されている問題を解くことで、ポイントを積み重ねていくサービスです。定期的にコンテストも開催されています。HackerRank を世界四大定期開催コンテストに含める考えもあると思います。

インド発のプログラミングコンテストサイトです。それなりに知名度は高いです。数学が好きな方には楽しい問題が出題される傾向にあります。また、CodeChef では一週間規模の期間をかけてアルゴリズム問題を解くコンテスト (Marathon Match とは別) も開催されていますので、短期決戦型のアルゴリズムコンテストが苦手な方は、楽しめる可能性もありそうです。

数学系の方だと、Project Euler から競技プログラミングのことを知った方も多いかもしれません。AtCoder などには参加していなくても Project Euler だけをやっているという方も多いです。数学系の問題が定期的に出題されています。

中国発のプログラミングコンテストサイトです。コンテスト環境が充実している日本の競技プログラマがあえて利用する機会はあまりないと思いますが、「一般グラフの最大マッチング」を verify できる問題があります。

オンラインジャッジ

様々なコンテストの過去問を集めたサイトが多々あります。日本では有名なものとして会津大学の運営している AOJ (Aizu Online Judge) があります。

既に上でも挙げましたが、AtCoder 上で出題された過去問を集めたサイトです。非公式ながら非常に洗練されたサイトです。

会津大学の運営しているオンラインジャッジです。AtCoder Problems に並んで日本人がよく利用しているサービスです。JOI 予選/本選の過去問や、ICPC に関連する過去問などが集められています。

数年前に yuki さんの個人運営によってはじまった「問題を投稿できるオンラインジャッジ」サービスです。みなが気軽に勉強しあえる場を作ろうというのがコンセプトで、誰でも気軽に作問して投稿することができます。集まった問題たちでコンテストも開催されています。皆の「こういう問題があったらいいなぁ」というのが集まっているサイトだと言えるでしょう。

北京大学の運営しているオンラインジャッジです。大昔、まだ AtCoder もなく、AOJ も盛んでなかった時代には、POJ がメジャーな精進場所でした。しかし現在では「計算実行が遅い」「他に日本語メインのサイトがある」などといった理由により、あまり使われなくなって来ています。現在では AtCoder / AOJ でほぼ十分と言えるでしょう。ただし、USACO (JOI のアメリカ版) の過去問たちは JOI と同様、良問がとても多いので是非解いておきたいところではあります。

POJ がメジャーな精進場所であった時代よりもさらに昔は UVa がメジャーだった時代もあるようです。

まだまだ色々あります。SPOJ は極めてマニアックな問題もあり、日本にもコアなファンのいるオンラインジャッジです。