AtCoder 100days Challenge
コード練習の手段として始めたAtCoderであるが、途中からAtCoderの問題を解くことそのものが目的となり熱心に演習を行ってきた。
そしてふと思った。
人はアルゴリズムの勉強を始めて100日間でどれだけAtCoderのレートを伸ばせるのだろうか。
それを思いついてから「100日間でとにかくレートをあげる」を目標にアルゴリズムコンテストに参加し、2020年12月18日からはじめたAtCoderが2021年3月27日のABC197の参加をもってちょうど100日目になった。
多くのコンテスト参加者のブログを見る限り、レートを上げることそのものに興味はあっても、いかに最速でAtCoderのレートを上げるかに主眼を置いた人はいなかった。それならば私の経験も需要もあるだろう。
この100日の試行錯誤の成果や得られたことをここに残しておく。私と同じように最速でAtCoderのレートを駆け上がりたい初心者の方に参考になれば幸いだ。
§0. 前提：プログラミングコンテスト/AtCoderとは
プログラミングコンテストとはざっくりというとプログラミングを用いて数学の問題がどれだけ解けるかを競うコンテストである。
「100万個の数字を与えるのでその中から最大の数字を選びなさい」とか「迷路の最短経路を2秒以内に求めなさい」といった問題が出題されるので、プログラムを組んでそれらの問題を解答していく。
問題を解くためには、
・大学入試程度の数学の知識(数学的発想力)
・ある程度のプログラミングの知識
・データを効率よく処理する手法(アルゴリズムやデータ構造)の理解
の3つが必要となる。
国内ではAtCoderというサービスが有名で、AtCoderではほぼ毎週末、プログラミングコンテストが開催されている。AtCoderではレーティングが付与されていて、コンテストの成績に応じてレーティングが上下していく。このレーティングを上げていくことがコンテスト参加者の目標となる。
※国内外でも同様のサービスは存在するが、本記事で述べるプログラミングコンテストはAtCoder社のコンテストを前提としている。
AtCoderの説明に困ったらこれ使ってください pic.twitter.com/50s3czCxFy
— chokudai(高橋 直大)🍆 (@chokudai) July 9, 2018
▲もっと詳しく知りたい人は高橋氏(AtCoder社のCEO)のTwitterやブログを参照してください。
§1. AtCoder 100days Challengeの結果と演習量
まずは100日間アルゴリズム学習を行った結果の成績がこちら。
1) AtCoderの成績
・Contest参加回数 17回
AtCoderでは参加者のレベルに応じたコンテストが開催されいる。そのうち、AtCoder Beginner ContestとAtCoder Regular Contestに期間中すべて参加した（一問も解けなかったContestが1回だけあり、それは不参加扱いとなっている）。
・rate 1084
100日間で水色に乗せることを目標に後半はかなり追い込んで演習を行ったが目標であった水色に乗せることはできなかった。
はじめた当初はrate1000はすぐに到達して、その後どれだけ積み上げられるかの勝負と踏んでいたが、rate1000あたりの問題に壁があり、緑の問題が確実に解けるようになるまでに80日あたりまでかかってしまった。
という訳でAtCoder 100days Challengeの世界記録はrate1084である(参加者1名)。
（注：レートやランクの色については下記のブログを参照ください)
2) 毎日の演習量
100days Challengeを想定して以降、次のような目標を定めて演習に取り組んだ。
・平日は1時間（ただしMリーグが開催される日は1時間以下でも可）
・休日は3時間
・毎日1問以上問題を解く
あくまで目標なので平日3時間勉強した日もあれば、休日1時間も勉強していない日もあるが、平均すればおそらく目標の倍程度の時間の演習を行った。
▲日ごとの解いた問題数の推移。色が濃いほうが解いた問題が多いことを示してる。Mリーグが開催されない水曜日の列だけ解いた問題数が多い。
3) 演習の記録
・0~10日目
いろいろな人のブログを参考にAtCoderProblemsで過去の典型問題を解き始める。
・10~60日目
AtCoderProblemsの「Boot camp for Beginners」のMediumとHardの問題を順番に解く。年末年始の多くの時間を問題演習に充てたことで一気に理解度が深まった。グラフとかアルゴリズムが全く分からなかったため「アルゴリズムとデータ構造」を参考書として使用する。C++で書かれていて難しかったので10章くらいまでの流し見で終えた。
・60~85日目
「Boot camp for Beginners」が完了。残った緑問題を解きつつ「アルゴリズム実技検定公式テキスト」でまだ身についてない典型アルゴリズムや実装例を学ぶ。
・85~100日目
水色の問題を解き始める。理想的にはこのラインにもう10日早く到達できるとよかった。体感的にはrate1400くらいまで到達できた。
4) AtCoderProblems上の演習記録
・解いた問題数（Accepted）: 400(1日平均4問)
・最長連続継続日数（Longest Steak）:100日
AtCoderをはじめてから平均4問、毎日欠かさず演習に取り組んだことになる。
灰色から水色まで各難易度をまんべんなく解いたことを考えると、100日間で悪くない演習をこなすことができた。100日間で200時間以上の演習時間を確保できたのではないだろうか。
▲難易度別の100日間の演習数。
以上が私の取り組みの記録になる。
レートはついてこなかったが演習量としては個人的にかなり満足した量をこなすことができた（でなければこんな記事を書かない）。
§2.最速でAtCoderのレートを上げるためには
ここからはプログラミングコンテスト初心者が最速でAtCoderのレートを上げるにはどうすればよいかの個人的な推察に移る。
何をもって初心者と呼ぶかは人によって幅があるが、ここではプログラミングコンテストやそれに類するものに一度も参加したことがない人を初心者と呼ぼう。
プログラミング技術の有無、大学でアルゴリズムの講義をとったことがあるとか、そういうことは問わない。
なぜならプログラミングコンテストに必要な能力に占めるプログラミングの技術とかアルゴリズムの知識の割合は大した割合ではないからだ(※個人の見解です)。
もちろんプログラミングコンテストに参加するには最低限のプログラミング技術とある程度のアルゴリズムやデータ構造は知っておく必要があるが、より大事なのはプログラミングコンテストの出題傾向に応じた数学的発想力だ。
そして数学的発想力はAtCoderの過去問を大量に解いてAtCoderの出題傾向を知り、パターンを覚えていく演習が重要だ。プログラミングの技術とか、アルゴリズムの知識は演習の中で自然と身につく。
下記のブログの統計でも明らかなようにAtCoderのレートは解いた問題数（AC数）、特に難易度の高い問題を解いた数(Rated Point Sum)と強い相関を持つ。
このような事実から『自分のレベルで解ける、できるだけ難易度の高い問題を、とにかくたくさん演習すること』が、レート上げる最短なルートだと私は提唱したい。
①言語の選択
ではどのプログラム言語を使って演習するのが良いだろうか。
――― C++かpythonの2択だ。プログラミングコンテスト以外の理由があればpythonでも可だが、pythonをすでに学習済みでない限りC++が推奨だ。
理由は簡単で、解説記事のほとんどがC++で書かれているからだ。プログラミングコンテスト界隈ではC++がデファクトスタンダードで、AtCoderの公式解説では解答例にC++しか載ってないこともある。
さらにAtCoderの公式解説は淡白な説明なことが多く、解説を読んでも理解できないことが多々ある。そのようなときは問題が解説されているブログを探すことになるのだが、有名な解説ブログはC++で解説されていることが多い。
ただしpythonのアルゴリズム解説本が出たり、pythonの解説も充実してきたのでpythonを学習済みの人がC++を勉強しなおす必要まではないだろう。
pythonとC++以外の言語の解説の充実度は不明だが、参加者の大半がC++かpythonで参加していることを考えると、解説本や解説サイトが極端に少ないと思われる。やる気があれば行けると思うが、茨の道であることは確かだ。
▲上記ブログによるとコンテスト参加者の言語は2019年7月段階で圧倒的多数がC++。pythonがだいぶ引き離された二番目でC++を除いた半分程度を占めている。
②演習方法
言語が決まったら演習方法だ。まずAtCoder Problemsをお気に入りに登録する。AtCoder ProblemsはAtCoderで自分が解いた問題を管理してくれるサイトだ。非公式ながら参加者のほとんどが利用している事実上の公式成績管理サイトである。問題の難易度の推定や過去問へのアクセス、自分の演習量の管理など、AtCoderの演習を行う上で必要なものがほぼすべて入っている。
〇AtCoderProblems
最速レート上げにはBoot camp for Beginnersモードが最適だ。
このサイトの左上には、ひっそりと「Boot camp for Beginners」というモードがあり、難易度ごとに100問ずつ、計300問の問題が用意されている。
問題番号ごとにほぼ等間隔で難易度が上がっていく。Easyの100問目とMediumの1問目の難易度はほぼ同じで、Mediumの100問目とHardの1問目の難易度とほぼ同じになっている。
おおよその問題の難易度は次の通り
Easy 難易度 0 ~400 AtCoder rate 灰相当
Medium 難易度 400~800 AtCoder rate 茶相当
Hard 難易度 800~1200 AtCoder rate 緑相当
はじめてプログラミングを触る人は初心者向けのプログラミング本やサイトを参考にしながらEasyの問題をじっくりと取り組めばプログラムの書き方がわかってくだろう。
灰色難易度相当のプログラムが書けて数学の基礎力が高い人でも問題形式や典型アルゴリズムを知るために、茶色問題は30問程度、緑問題は50問程度の演習が必要だというのが私の見立てだ(私の場合、茶色50問、緑100＋α問が必要だった)。
そこで灰色難易度相当のプログラムが書ける人のおすすめの演習方法はEasyは10の倍数の問題、Midiumは3の倍数の問題、Hardは2の倍数の問題を演習していくことだ。
30分考えても解けない問題があったら解答や解説ブログを見て解法を理解する。そのまま理解した解答を提出してもよいが、あえて解答を提出せず1週間くらいした段階でもう一度解くようにすることもお勧めだ。すこし記憶から薄れてくるタイミングで解きなおすことで記憶への定着をはかる。
解説を見て回答を提出してしまうと、AtCoder Problems上で正答済み問題になってしまい、よほど丁寧に管理していないと見直すことがなくなってしまう。
この方法で、基礎力のある人なら最短でEasy10問、Medium33問、Hard50問でレート1200程度の問題に到達できる。ただしこれができる人は東大理系レベルの数学力があったり、プログラミングやアルゴリズムの予備知識を持っているなどのアドバンテージを持っているごく一部の人だけだろう。
とはいってもAtCoder参加者は旧帝大レベルの大学に偏っているので、上記に該当する世間で見れば「ごく一部」はAtCoder上では「そこそこ」いるはずだ。
「ごく一部」でない人も、自分が詰まるまでは上記のスタイルでおこなっていき、難易度上昇が厳しくなってきた段階で、1問づつ解いていくスタイルにけていけばよいだろう。そうすれば、自分の能力に応じて最低限の演習数でレートあげができる。
ただし演習でどれだけ効果が出るかは、その人の数学の基礎力や適性によっても大きく変わる。1問づつ解いていくスタイルでも厳しくなったら、AtCoderのlist機能を用いて詰まった難易度の問題を探して解いていくスタイルに変えていってもよいだろう。
Mediumまでは数学的発想力に任せて解ける問題も多いが、Hard問題に到達したあたりでほとんどの人が壁を感じるはずだ。幅優先探索やバイナリーサーチ、動的計画法のような初めて聞く単語が表れてくるようになる。また、問題を解いていく中でなぜか制限時間オーバー(TLE)が解消されない問題も出てくるだろう。
ここでアルゴリズムを体系的に学習するというタイミングが来る。pythonの場合、このアルゴリズム学習は「アルゴリズム実技検定公式テキスト」を1冊やればよい。およそrate1400までの問題に使用されるアルゴリズムはほぼ網羅されている。
〇アルゴリズム実技検定公式テキスト
2021年2月に発売されたばかりのこの本は「アルゴリズム実技検定」という検定のテキストという立ち位置だが、これ一冊で典型的なアルゴリズムの理解から実装までを学ぶことができる本になっている。
本書は他のアルゴリズム本に比べて、取り扱う内容を頻出アルゴリズムに絞るかわりにアルゴリズムの内容や実装方法に丁寧に解説を割いていて、かなり入門向けを意識している。
入門向けとは言えど、中級編に相当する6章以降が全体の2/3を占め、対象読者はAtCoderの茶色の問題がある程度解ける実力が必要だ。Boot camp for BeginnersのHard問題に詰まっているあたりの人にうってつけの本である。
電子版と紙版がある。紙版の場合、例題のwebページに行くためにはAtCoderProblemsを経由しないと面倒という裏ルールがある。
また、この本のために作られた新規問題はAtCoderProblemsにもアクセスが存在せずURLベタ打ちでしか見つけられなかった。購入者以外が容易に問題演習ができると本の価値が少なくなってしまうのでしょうがないところである。
私はPCを開きながら書籍をみたいので紙版を購入したが、電子版は問題のリンク先に飛べるそうなので、電子版でも問題ない人はそちらのほうがよさそう。
アルゴリズム実技検定公式テキストで典型的なアルゴリズムを学習しつつ、Hard問題の最後までたどり着くことができれば、おそらくレート1000～1200の実力はついているはずだ。
ここからは水色への道となるが、基本はBoot camp for Beginnersとやることは変わらない。
At Coder Problemsのlist機能を使ってレート1200以上の問題を難易度順に並べて易しい順に2つ飛ばしくらいで進めていく。ビーカーのついている問題は難易度推定が甘かったり、testcaseが公開されていない、などの点で問題の質にばらつきがあるため解かなくてよい。
ここあたりから1問あたりにかかる時間が平均30分を超えるとともに、出題パターンが複雑になっていき、プログラミングやアルゴリズムの比率より数学的な思考力の割合が増えていく。
そのため限られた時間内でレートを上げるには、解く問題数を水増しする必要がある。私は移動時間などに問題を眺めて解法を考えるまでは行うが、実装はしないという、解いたふり戦法を多用してた。
また水色あたりからUnion-Find、セグメント木、BITのようなデータ構造に関する問題が出てくる。データ構造は「アルゴリズム実技検定公式テキスト」には載っていないので、pythonの人はデータ構造の問題が出たときは以下のサイトで確認しよう。
〇いかたこのたこつぼ
プログラミングに関する個人メモを公開してくれているサイト。
アルゴリズムの良記事として推薦されている記事のほとんどはC++のため、pythonで各種アルゴリズムの解説と実装例がまとまっている本記事の希少度は高い。解説だけでなく、解説リンクも豊富で、リンク先の記事も分かりやすいものを選んでくれている。
1)サイト内解説やリンク先の解説を読んでアルゴリズムを大枠理解する
2)サイト内のコードを読む＋自分で写経してみる
という感じで利用できる。
ここまでくれば世界記録更新が見えてくるはずだ。これ以上のことは私には未知の領域なので記録更新した方はブログで報告してください。
§3.最速でレートを上げる際のTips
最後に雑多なtipsを残しておく。
〇自分の実力を正しく推定しよう
AtCoderのレートは1回の成績変動の影響は小さく、長期のパフォーマンスを反映している。特にコンテストに参加したての頃はレートが上昇しづらい仕様になっている。
また、一回のコンテストでは6問の問題が出題されるが、1問問題が解けるか解けないかでパフォーマンスが300くらい前後する。
従って、短期にレートを上げようとする場合、AtCoderのレートの上昇よりも自分の実力の上昇のほうが早く、コンテスト1回ごとのパフォーマンスではブレが大きく自分の実力を過大評価、過小評価してしまうことになりがちになる。
レートやパフォーマンスに左右されず、過去問の演習と対峙しながら、自分の実力を正しく推定し、実力相当+αの難易度帯の問題を多く解くことがレート早上げの要となる。
〇コンテストにはできるだけ参加しよう
上記の通りレートは長期のコンテストのパフォーマンスを反映するため、どんなに実力があってもその実力のレートを得るには何度もコンテストで実力通りのパフォーマンスを出す必要がある。
100日間で出場できるAtCoderのコンテストは20回前後しかない。短期でレートを上げるためにはとにかくコンテストに出場して、レートを上げる機会を逃さないようにする。
〇長期休暇を利用しよう
レートを上げるのに必要なのは(適切な)演習あるのみだ。そのためにはどうしてもある程度の時間が必要だ。
仕事や学業とのやりくりを考えることも大事だが、長期休暇期間を使って演習数をかせぐことも結構重要だ。GWをきっかけに最速レート上げを目指すのはお勧めだ。
〇 Streakを切らさない
どんなに忙しいときでも毎日続けること。疲れた日は簡単な問題一問解くだけでもよい。問題を解きstreakすることが明日のやる気につながる。
〇Mリーグの開催していないときを選ぼう
どうしてもほかの趣味があるとプログラミングコンテストと可処分時間の奪い合いになる。
私はMリーグ視聴とプログラミングコンテストでMリーグ視聴をとったわけだが、Mリーグのオフシーズンに取り組めばこんな悩みを抱えることはなかった。
人には趣味があり優先順位もある。できることならライフとプログラミングコンテストのバランスをプログラミングコンテストに傾けられる瞬間を選ぼう。
〇プログラミングコンテストを楽しもう
ここまで8000字以上いろいろ書いてきて何だが、プログラミングコンテストは人生の役に立たない。プログラミングという名称がついているから何か役に立つのだろうと思っている人がいるかもしれないが、私がアルゴリズムを理解してAtCoderContestでrateを上げて喜んでいるのは、世間の人々がウマ娘 プリティーダービーのパラメータを上げて喜んでいるのと変わらない。
面白いオンラインゲームの名前が「AtCoderプログラミングコンテスト」なのか「ウマ娘 プリティーダービー」の違いでしかないのに、なぜかウマ娘を仕事の役にたてようとする人はおらず、プログラミングコンテストを仕事の役に立てようとする。
AtCoderの参加者たちが自分のためになると思って苦しみながら耐えて演習を行っていると思ったらそれは大きな勘違いだろう。ただ楽しくてやっているだけだ。
だからあなたも楽しいと思わなければプログラミングコンテストをやる必要はない。もちろん苦しいタイミングがないわけではないが、その苦しみは最終的にレートになって返ってくると信じているから頑張っているのだ(繰り返すがAtCoderのレートはあなたに何も与えない。ゴールドシップのパラメータが何かあなたに与えているだろうか？)。
何十連ガチャでお気に入りのキャラクターを当てるのに苦しみながらもその先に喜びがあるように、どうかあなたにもAtCoderProblemsのAcceptedを苦しみながら積み上げた先の喜びが楽しめる日があらんことを。