この記事では、AtCoderで緑コーダー（800-）になるために必要な勉強について話そうと思う。 緑になった時に書くと言ってたのだが、色々あって書くのが遅れてしまった。
なぜ私がこれを語るにふさわしい人間か
もし私が、一回目のコンテストでいきなり橙パフォを出して緑に上がるような人間だったら、 誰も私が緑コーダーになるために何かいうことに価値を感じないと思う。
緑コーダーになるための勉強法を茶色で躓いている人たちに語るためには、 やはり自身も茶色で躓いた経験が必要であると思う。
まず私は、35歳のプログラマである。 過去には、
のようにちょっと知れたソフトウェアも書いたことがある。 たぶん、私のことをコードの書けない雑魚という人間はたぶんあまりいないのではないかと思う。
緑コーダーというのは、一般的な大学の学生で優秀なレベルであると AtCoderの高橋氏は述べている。
AtCoder（競技プログラミング）の色・ランクと実力評価、問題例
- 他社評価サイトなら最高評価
- エンジニアとしてもある程度の安心感がある
- 学生ならかなり優秀
緑コーダーというのは、学校のデータ構造とアルゴリズムで 習うような話題について基本的に理解し、 基本的なコードについては確実に書ける能力があると考えることが出来る。 実際に、Githubには素晴らしい自作ソフトウェアが並んでいて、 博士号まで持っているのにAtCoderでは緑という人もいる。
緑というのは、一般的なソフトウェア開発をするには十分なレベルであり、 決してバカに出来るほど低いわけではないのだ。 だから、きちんと勉強しないと躓くことになる。
私がそうだった。 実際私は、緑くらいは一瞬でなれるものと思っていたが、 かなり時間がかかった。
NTTからグーグルに転職したことで話題になったkumagi氏も、 そもそもが分散システムやロックフリーで大変知識のあるプログラマであり、 当然、Jubatusなど、コーディングの経験なども多かっただろうから、 私以上に優れたプログラマということが出来るが、 やはり緑まですんなりというわけではなかったようだ。
もちろん彼の場合は私のように競プロにフルコミットしてるわけではないが、 それにしても緑というのが超簡単ではないことはわかってもらえると思う。
おそらく、ある程度企業の研究所やOSSなどでコーディングをしている人でも、 それなりに勉強しないとすんなりとは到達出来ないだろう。
この記事は誰にとって価値があるか
ソフトウェア開発の経験がある人間でも、 緑まで行くのに決して順調ではなかった二例を紹介した。
そのうち一例は私であり、 私は少し躓いた時に、kumagi氏の勉強法を参考にして 自分の勉強法を改めて、レートを伸ばした。
従って、この記事はまず、 ある程度のソフトウェア開発の経験がある人間にとって 有益になるといえる。
もちろん、そうでない場合（学生など）にも、 茶色から緑色に上がりたいという場合には、 参考になることを書くつもりである。 この場合、コーディング経験自体がそもそも足りない場合もあると思うが、 それは、AtCoderの勉強をしていくうちに積めるものであるし、 教育的な観点からいうと、AtCoderの一番の価値はそこにあるものと私は思っている。
緑に確実に上がるにはABCのDまで解く力が必要
ABCで3完や4完というのは、多くの参加者がそこに収まるレンジだから、 早解きをすることで大きく順位を上げて、結果として大きなパフォを得ることが出来る。 が、まずはこの考え方はやめて、ふつうの速度でふつうに問題を解いて上がることを考えよう。 その方が将来性もあるし、競技プログラミングをアルゴリズムの勉強と捉えた時には より本質的でもある。
この場合、今の相場だと3完で800点か900点くらい、4完だと1000から1400くらいがつくことが多い。 AtCoderのレーティングはELOレーティングをベースにしているため、 現レーティングとパフォーマンスの差分を基準にしてレートの差分が計算されることになる。
あなたのレートが700として、仮に3完してパフォが800だとすると、 大体10かそこらしかレートは上がらない。こうして首尾よく750、780と上がっていくとよりレートは上がりにくくなり、 万が一3完すらとれなかった場合に、レートががくんと下がり、振り出しに戻ることになる。 これを繰り返すのが、どのレート帯でも上のレート帯に上がれない人の特徴だ。
だから、一つ上のランクの4完をとることをベースに考えた方が、よりスムーズに上がることが出来るようになる。 実際に、私が茶色から緑色に昇格した直近2回のコンテストでは4完している。
ここでは、AからDまで解くことを前提に話をする。
Dを解くにはどうすればよいか
Cまでというのは、 問題を正しく理解して正しく実装出来ますかという場合が多く、 それほどアルゴリズム感はないのだが、 Dになって来ると少しアルゴリズム感が出てくる。
Dというのはどういう問題かというと、 データ構造をうまく使って問題を解いたり、 グラフの簡単な問題を解いたり、 時にはUnion Findなど初等的なデータ構造が必要になることもある。 DPのようなものも出る。
競技プログラミングの初等的な範囲については 一通り網羅していて、実際に問題を解くことが出来るというレベルだ。 グラフの問題でも、ただダイクストラ法を使うとか、ワーシャルフロイド法を使うとか いうレベルではなく、そのアルゴリズム自体の理解と応用が求められることがある。
だから、Cまでは解けたがDが解けないという人は、 コンテスト後にTwitterで検索すれば死ぬほど出てくる。
私がやった明らかに意味のあった勉強を紹介する。
400埋め
AtCoderの400点問題を全部埋める。 400点というのは、基礎を学ぶ場なので、少し大変かも知れないが、 やっておいて損はないと思う。 全部やれば、競プロにはこういう問題があるという全体像も見えてくると思う。
また、AtCoder自体の癖にも慣れる必要があるので、 実際にAtCoderの問題をたくさん解くという行為自体はどこかしらで必要になってくる。 400埋めは良いトレーニングになるのでやってしまおう。 これは先述のkumagi氏もやっていたようだ。
私は、AtCoderを始める前にAOJのコースでアルゴリズムを網羅的に学んだり、 その時点で強連結分解やChu-Liu Edmondsなども実装していたが、 いざAtCoderのコンテストに出てみるとボロボロだった。 AtCoder自体に慣れていなかったからだと考えている。
ACした問題の管理には、私は
を使っている。他にもサービスがあるようだから、好みのものを使うと良い。
AtCoder Problemsというサービスは、独自に問題の難易度も計算しているのだが、 これがあまり正しいとは私には思えなかったので、それがないシンプルなAtCoder Scoresを使っているという理由がある。
蟻本
をやった。これは、競技プログラミングの範囲を知る意味でも大変な意味があった。 この中には難易度の高い問題も混ざってしまっているから、400以下のものに絞って解くようにした。
蟻本は、難しいことで知られているが、初級と中級くらいの範囲であれば抑えておくべきだと思う。 上級の高度なグラフの話（LCAとか）は、Dではまず出てこないので今は無視してよい。
BIT、セグツリー、Union Findあたりはライブラリでもっておいても良いのではと思うが、 まずは標準ライブラリをきちんと理解する方が良い。 ライブラリがなくて解けないという問題は、そこまで多くはない。
標準ライブラリでは、プライオリティキュー、セット、multiset、二分探索などは良く使う。 基本的にはこれらが揃っているC++を使うのが一番良いだろうと思う。
蟻本が難しい場合はまず、
社会人がAtCoderに参加する時に読むと良い本で紹介する本で学ぶと良いと思う。
ARCやAGCには出なくてよい
AtCoderにはレート2000未満向けのABCの上のコンテストとして、 2800未満向けのARC、天井なしのAGCが存在するが、 この2つはどちらもめちゃくちゃ難しいため、 参加はしてもモチベ維持くらいの効果しかないだろうし、 場合によっては0完してしまい灰色パフォが出てしまうことがあるから、 おとなしくABCだけに出ることをオススメする。 ABC以外にもyukicoderやCodeforcesなども存在するため、 モチベを維持するためのコンテストに出る必要があるならば、別のものに出ることが出来る。 500点以上の問題は完全に無視して、400点をちゃんと解くことを極めよう。
400点から500点は、順位表を見るとわかるが、 解ける人が極端に少なくなる。 つまり、400点が厳しいというレベルでは絶対に太刀打ち出来ないし、 あまり役に立たないから今は無視してよい。
私は今Eのコンテストでの打率は5割くらいだが、 緑になって以降はDを落としたことはない。
言語は何にすれば？
Rustは正直にいって、競プロには向かないのでオススメしない。 sorted setは標準ライブラリにあるのだが、処理系が古いため必要なAPIが実装されていないし、 multisetは存在しないからだ。 私は、自作したスキップリストを使っている。
その他にも、Rustが競プロに向かない理由はあるが、それは別途書くかも知れない。
言語のチョイスでいうと、最善はC++で、次善は、PythonかJavaだと思う。 Pythonだと、問題によっては時間が厳しいことがあるが、書きやすい分でトータルでいうと十分に回収出来ると思う。
次回予告
次は、水色に上がった時に「緑色から水色に上がるにはどうすればよいか」という 記事を書くことになるだろう。乞うご期待。