AtCoder（競技プログラミング）の色・ランクと実力評価、問題例

 

最新の情報はAtCoder公式情報サイトAtCoderInfoに記載されています

info.atcoder.jp

 

以下、古い記事の内容となります。

 

近頃「AtCoderの色を就活等でアピールしたい時に上手く出来ない！」と言われるので、「どれくらいのレベルの人なの？」という説明と、エンジニアさん向けに「実際どういう問題が解けるの？」というまとめを書いておきたいと思います。解き方のヒントが書いちゃってあるので、自分で解きたい人は、ヒントを読む前に解いてください。

 

 

 

Update履歴

• 2020/6/22 茶色・緑色に関する評価を書き足しました。参加人数を更新しました。
• 2022/10/02  アップデート要求が多くありますが、現状でも大きな変化はありません。（この文章を追記しました）
• 2023/12/09　公式サイトへのリンクを冒頭に追加しました。この記事は昔のものになります。

大前提：AtCoderについて

AtCoderは、プログラミングのコンテストを開催している企業です。「もの作りのアイデアを競う」だとか、「製品を作る」という部分から少し乖離した、「複雑な処理を正しく記述する」だったり、「計算時間のかかる処理を、数学的/情報科学的にスマートに処理する」だったりを競うコンテストになります。多くの人が参加できるようにするため、専門分野に対する知識等は出題されず、ベースとなるアルゴリズムに関する問題が出題されます。コンテストは毎週開催され、10000人ほどが同時に参加しております。

採点は完全に機械的に行われ、想定通りの答えが出力されていれば正解となります。人間の好みに左右されることがない、確かな評価となります。

 

このようなコンテストであるため、エンジニアに必要な、全ての能力が測定できるわけではありません。必要な項目は、以下の資料（AtCoderの営業資料の一部）をご確認ください。

AtCoderJobsでの参加者の説明

 

AtCoderの色・ランクと、その実力

さて、AtCoderのコンテストに参加すると、コンテスト成績に応じてレーティングが変化します。これによって、AtCoder上における、レートの色が変化します。

下の画像は自分のレーティングの変化です。

AtCoderのユーザーページ(chokudai)

これは僕のレーティンググラフなので異常に高いんですが、400ごとに色がついていて、赤・橙・黄・青・水・緑・茶・灰・黒、という順番になってます。

誤解を恐れずに超ざっくりとイメージでの評価をするなら、

• 灰色は参加すれば誰でもなれるので意欲以外の保証はなし。
• 学生で茶色なら優秀だがエンジニアとしてはちょっと物足りない。派遣とかで来たエンジニアが茶色あれば一安心。
• 緑あれば大抵の企業でアルゴリズム力は十分。AtCoder的には決して上位ではないが、他社評価サイトなら最高評価。
• 水色だと基礎的なアルゴリズム処理能力については疑いのないレベル。
• 青以上は一部上場のIT企業でも、一人もいないことが結構あるレベルになる。
• 黄色からは化け物。競プロの問題を解く機械だと思っておけば良い。
• 橙はあたまおかしい。
• 赤はもうなんか世界大会とかに招待されたりする。

って感じに思っておけばいいです。誤解をしたくない人は、以下に詳しい説明があります。

 

灰色　（Eランク Rating ~399）

灰色になる条件は、AtCoderに1回参加する、です。ということなので、AtCoderが保証できる実力は全くありません。灰色な人はもうちょっとたくさんコンテストで出たり、実力を上げたりして頑張ってください……＞＜

なお、Rating200以上であれば、他社サイトであれば十分なランクがつくくらいの実力はあります。ですので、AtCoderJobs上でなにか評価を出来る仕組みなどを準備することを検討しています。

（AtCoderのコンテストが足りなくてレーティングが上がりきってない、って人はごめんなさい＞＜）

 

茶色　（Dランク Rating 400~799　上位50%）

茶色になる条件は、Ratingが400以上になることです。茶色で保証できる実力ですが、正直、AtCoder内ではあまり高いレベルではありません。ただ、ここにたどり着く前に辞めてしまう人が多いので、十分にやる気がある人であるとは言えるでしょう。

なお、他社転職サイトと比較すると、このレーティングでも上位1~2%の最高ランクに到達出来る人が数割いるため、一般的には十分高いレベルであると言えます。

個人的な印象としては、

• 情報系の学生が茶色であれば、ちゃんと勉強してるなって印象になる
• 派遣で来たプログラマがAtCoder茶色だったら結構安心する
• 茶色があればエンジニアとしてアルゴリズム面においての安心感があるかと言われたら、正直物足りない

みたいな印象があります。スキル的に確実に保証出来る点は、

• 標準入出力、if、forなどの単純な操作はできる
• 問題文を正しく理解し、計算量を考えない仕様通りの実装をすることが出来る

の２点です。ただし、完全に上の能力しか持っていないと茶色になることはできず、

• MARCH理系学部以上に入れる程度の数学力や論理的思考力があり、数学的な工夫が必要な問題を正解出来る
• 典型アルゴリズムに関する知識を多く持ち、探索による全列挙や単純な動的計画法など、典型的な問題に正解することが出来る。
• コーディングや読解速度が早く、単純な問題を早く正確に実装することが出来る

などの特徴を持っていなければ、茶色になることはできません。このレート帯に達する人は本当にバラバラなので、保証出来る点は少ないですが、何かしらの強みを持っていなければ、茶色に到達することはできません。

もちろん、保証出来る点が少ないと言っても、コーディング試験でおなじみFizzBuzzなんかは全員が当然一瞬で組める水準です。

茶色の人の半数が解ける問題と時間を並べます。

 

B - Polygon 要求タイム：５分

整数の配列を受け取り、配列が条件を満たすか（Max, Sumが絡んだ計算式。計算方法自体は問題文に記述あり）を求める問題です。

C - Grand Garden 要求タイム：８０分

要素数Nの0埋めされた配列が初期状態として与えられ、区間を指定してその区間の要素を1増やす操作が出来るときに、与えられた整数列を作るために必要な最小手数を求める問題です。

多少の考察を要求する問題です。いわゆる「数学」や「アルゴリズム」というレベルの問題ではなく、「やりたいことを実現するにはどういう手順を踏めば良いか」を考えるタイプの問題です。（僕自身は、こういう部分が「アルゴリズム」の本質的な部分であり、○○法みたいなものよりよっぽど大切だと思っていますが。）

 

緑色　(Cランク R800~1199　上位30%)

緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。要求レベルも決して低くなく、出場回数が足りないとマイナス補正がかかるため、運だけで到達することはまず出来ないラインです。他社アルゴリズム力判定サービスだと、上位１％の最高ランクが付く実力です。（あくまで「アルゴリズム力部分だけであることに注意してください）

印象としては、

• 学生ならかなり優秀。
• エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう、くらいには思える。データ量が多い現場など、計算量の多い処理が要求される現場でなければ、このレート帯以上を求める必要はほぼない。

くらいの印象です。もちろんアルゴリズム力しか計ってないので個人差があります。

技術的な部分では、

• if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
• 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。

という感じです。

 

緑色の人の半数が解ける問題と時間を並べます。

C - ID　１時間

データが与えられるので、グループごとに順序を整理し、ID番号を生成する問題です。素直な実装力を求められる問題はAtCoderでは多くないですが、普通に書くと30行くらいの機能を実装する能力があることが分かります。

C - Streamline　２０分

簡単な一人ゲームが与えられるので、最小手数を求める問題です。どちらかというとAtCoderのこのランクの問題は、こうした基本的な論理的思考力の方が求められることが多いです。

 

水色 (Bランク R1200~1599　上位15%)

水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。

半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。

技術的なスキルで言うと、

• 計算量に関する感覚が体に染みついており、複雑な処理でも苦もなく実装出来る
• 深さ優先探索や幅優先探索、順列の全列挙やパターンの全列挙などができる。そこから動的計画法やメモ化再帰などの計算量改善につなげることも多少出来る。
• 貪欲・DP・しゃくとり法・二分探索などの計算量を改善するテクニックをある程度使い分けることが出来る。
• 累積和やUnionFind(競プロ外ではDisjoint Set)などのデータ構造を使いこなすことが出来る。
• ダイクストラ法やワーシャルフロイド法、クラスカル法などの、基本的なグラフアルゴリズムが扱える。木構造やグラフ構造に対して適切に処理を行うことが出来る。
• 一定以上の数学に関する素養がある。素数などの性質や、それを利用した素数判定や列挙、約数の列挙等、最小公倍数や最大公約数、組み合わせの計算など、競プロにありがちな典型数学問題に対処できる。

みたいな感じになります。水色になると急に要求水準が上がってるのは分かると思います。

水色の人の半数が解ける問題と時間を並べます。

D - Xor Sum 2　60分

数列が与えられるので、XorとSumが一致する区間の数を求める問題です。Xorなどのbit演算の基礎知識が与えられた上で、効率的に処理するデータ構造とアルゴリズムを考える必要があります。このあたりから、アルゴリズムの勉強をしたことがない人には手が付けられない問題になってきます。

 

D - AtCoder Express 2　60分

最初に区間がN個が与えられ、その後Q個の区間クエリが与えられるので、完全に内包している区間がどれだけあるかを求める問題です。入力される値が小さいので、例えばWavelet Treeなどの複雑なデータ構造を用いなくても解くことができますが、区間を二次元上にマッピングする発想を出すこと自体が少し難しいです。

 

青色 (Aランク R1600~1999　上位7%)

 青は超優秀です。学生時代を競技プログラミングに注ぎ込んでも、ここにたどり着けない学生は大量にいます。競技プログラミング未経験者では、このレベルと競技プログラミングで戦うことは殆どの場合は無理です。8割以上のIT企業において、アルゴリズム力はカンストです。一部企業においては、少し持て余してしまうかもしれません。

技術的な要素は以下の通りです。

• 複雑な処理でも難なく高速に実装出来る。
• 水色のアルゴリズム知識に加え、最大流やSegment Treeなど、高度なアルゴリズム、の知識がある。
• データ構造やアルゴリズムを知っているだけでなく、適切な場面で活用することが出来る。
• どういう問題の時にどういう計算量改善の方法があるか、というような、典型テクニックを多く知っている。
• 複雑な計算量改善を要求された際に、紙などを用いてきちんと考察を進めることが出来る
• その他、水色で書いたことのレベルが一段階上昇している

って感じでしょうか？水色や青あたりで、競技プログラミングで必要な知識はほぼ揃ってしまうので、そこから先は応用力の違いになってきてしまいます。

青色の人の半数が解ける問題と時間を並べます。

 

C - Alternating Path　20分　（1時間だと水色）

グリッドグラフが与えられるので、白黒の頂点を交互に辿ってたどり着ける頂点のペアの個数を求める問題です。基本的な幅優先探索が出来るのはもちろん、そこからペアの数を纏めて数えるための考察などが必要になります。時間を掛ければ解ける問題ではありますが、この考察を短時間で解けるのがこのランクの強みです。

 

D - Equal Cut　60分

数列を切り分ける問題です。（数列が多く出題されていますが、データ構造やアルゴリズム等をシンプルに問うのに、数列は非常に便利です）

４つの区間の和の最大値と最小値の差が出来るだけ小さくなるように区間を切り分ける問題です。こちらも一筋縄で解ける問題ではありませんが、特別なアルゴリズムの知識は全く必要なく解けるAtCoderらしい問題です。深い考察力が要求されます。

 

黄色 (Sランク R2000~2399　上位3%)

九割以上のIT企業において、このレベルのアルゴリズム構築能力は必要ありません。研究職・研究開発などや、高度なアルゴリズムを要求される開発現場で重宝されます。 

といいつつ、普通にプログラマとして役立つので来て欲しい、みたいな発信はSoundHoundさんとかがしてたりするので、エンジニアとして役立つ場面も多々あるのかな、と思ってます。「うちでは役立つ！」って言ってる企業さんもたくさんあるので。

能力的には、数学的な思考力、論理的な思考力、アルゴリズムに関する知識、正確で高速な実装力に関して、大幅なアドバンテージがあります。別にエンジニアリング力は全然保証してませんが、賢い人が多いので統計を取ったら高い可能性はあるかもしれません。このランクになると、新卒採用においてはポテンシャル採用という意味でめちゃくちゃ評価されている印象です。

 黄色の人の半数が解ける問題と時間を並べます。

 

D - Nearest Card Game　60分

二人ゲームで、カードを取る順序が与えられるので、先攻プレイヤーが取るカードの和を答える問題です。愚直に計算すると当然間に合わないので、上手く処理を高速化してあげる必要があります。処理の高速化自体のアルゴリズムは、非常に難しいというわけではないですが、境界の処理とかがかなり面倒で、見た目以上に実装に苦労するタイプの問題です。

 

D - Median of Medians　60分

数列が与えられるので、その数列で考えられるすべての区間に対する中央値を列挙し、その値の中央値を求める問題です。かなり数学的な問題ですが、アプローチ自体はかなり情報科学的な定跡を用いて解いていくタイプの問題です。大抵の人にはとっかかりすらつかめない難問です。

 

橙色 (SSランク R2400~2799　上位1%)

ここまで来ると、検索サービスとかの滅茶苦茶アルゴリズムが大切な会社さんとか、研究開発とか、そういうところじゃないとこのアルゴリズム力は生かせない気がします。

といいつつ、普通のエンジニアの新卒採用でもかなり優遇されています。やっぱりポテンシャル採用なのかなあと思っています。ただやっぱりこのランクの能力めっちゃ生かせる！って言ってる企業もちょこちょこあります。

橙色の人の半数が解ける問題と時間を並べます。

 

E - Weights on Vertices and Edges　60分

グラフに関する問題です。まず基本的な貪欲法でO(N^2)まではすぐ見えるかと思います。（水色くらいの水準）　ここからいかに計算量を落とすかの問題です。例えば永続UnionFindやDynamic Connectivityなど、連結成分を管理する難しめのデータ構造が見えますが、考えをきちんと整理すると、計算順序を上手く整理すればUnion-Findなどの簡単なデータ構造だけで比較的簡単に書くことができます。

 

D - Reversed LCS　40分

文字列Sが与えられる。このSをK文字まで変更した文字列をTとして、Tと、Reverse(T)の最長共通部分列の長さを最大化する問題です。そもそも最長共通部分列の知識があるものとして、まずこの最長共通部分列がどのような特徴を持つかを考察するパートをこなした上で、適切な動的計画法の式に落とし込めるかどうかが問われる難問です。

 

赤色 (SSSランク R2800~3199　上位0.3%)

この辺から化け物しかいないので説明をサボります。僕もここです。

問題

E - Wandering TKHS　80分

木構造が与えられた時に色々する問題です。難しいです。

銀王冠 (SSSランク R3200~3599　上位0.1%)

頭おかしいです。ここに行きたいです。最早意味もない気がするので問題も貼りません。

金王冠 (SSSランク R3600~　上位0.03%)

化け物です。そもそも日本に一人しかいないです。世界でも九人しかいません。

 

 

 

 おおよそのレベル帯が分かりましたでしょうか？何かこれも書いておくべき！みたいなのがあればコメントやブクマ等で書いてもらえるとありがたいです！