AtCoder青色になるまでにやったこと
記事を書くにあたって...
北大B4のN_haraです。
昨日行われたM-SOLUTIONS プロコンオープン 2020に参加し、レートが1600を超えAtCoder青色を達成しました。
今回は節目として、これまでに競プロでやったことをまとめてみたいと思います。
今までにやったこと
1.競プロを始める～AtCoder茶色まで
この頃はアルゴリズムに関する知識がほぼほぼ皆無であったので、とりあえず自力でも解けそうな問題を探して解いていました。やった内容としては、
- AtCoder Beginners Selection(ABS)
- (ABC042~の)ABCのA,B問題
がメインになっています。特にABSはたった10問でAtCoderの感覚がやんわりつかめるので、もしまだ埋めていない人は全部解いてみることをおすすめします。
アルゴリズムの知識として理解していたのは
- （計算量を減らした）全探索、貪欲法
くらいだったと思います。（現在だと、もっと要求レベルが高いと思います。）
2.AtCoder茶色～AtCoder水色まで
このあたりから（特に緑以降）アルゴリズムの勉強を少しずつ進めていきました。
やった内容としては、
- (ABC042~の)ABCのA,B問題すべて
- 上に加えて、C問題半分くらいと簡単めなD問題
になります。C問題、特にD問題以降は計算量を意識しないとACできないことが多いので、アルゴリズムの知識（&計算量のある程度の見積もり）が必要になります。
この頃にアルゴリズムの知識として新たに理解したのは
- bit全探索、順列全探索
- 二分探索
- 深さ優先探索(DFS),幅優先探索(BFS)
- （比較的易しい）動的計画法
- ベルマンフォード法
- ワーシャルフロイド法
- 高速な素数判定法
- べき乗、逆元の高速計算
- 累積和
です。
データ構造として、
- Union-Find
も勉強しました。
ダイクストラ法やクラスカル法はこの時点では勉強していませんでしたが、これが原因でコンテスト中に詰まることはなかったように思います。（もちろん勉強して使えるようになるのに越したことはないと思います。）
3.AtCoder水色～AtCoder青色まで
この頃になるとAtCoderのレートが伸び悩んできたのであまりレートを気にせずいろいろな問題に取り組むようになりました。
例えば、ABCの埋め具合は以下のようになりました。
ABCにはいわゆる「典型問題」が多く出題されており、問題を解いたり、あるいは解けず解説ACをしたりする中で知らなかった知識に出会うことが多々ありました。特にE問題埋めをしたときは並のF問題よりも難しい問題があり、1題1題に集中して取り組んでいました。
この時点で新しく勉強したアルゴリズムは
です。
このようなアルゴリズムを扱う問題を含め、とにかくいろいろな問題を解いていました。
レートが伸びない人へ
ここまで淡々と競プロでやってきたことを書きましたが、思うようにレートが伸びない人もいると思います（むしろ停滞期のない人のほうが少ないと思っています）。実際、僕自身も水色で1年ほど停滞していて、4か月間highestを更新できない時期もありました。以降、備忘録も兼ねて、自分がレートが伸びないときにやっていたことを振り返ってみたいと思います。
I.レートを上げる意識を持ちすぎない
AtCoderに限らず、レーティングのつく競プロのコンテストサイトではより高いレートを目指したくなると思います。コンテストの結果レートが上がれば、やはり嬉しくなります（多分）。しかし、思うようにレートが上がらないときもあります。「レートを上げる、〇色になる」という目標を掲げて競プロに取り組むのは大事ですが、強く意識しすぎるとかえってプレッシャーになったりします。
ではレートが伸びないときどうするかというと、問題を解きます。問題を解く際には、もしかしたら知らないアルゴリズムの知識が必要になるかもしれません。あるいは、既知のアルゴリズムだったとしても、自分の考えでは簡単に思いつかないような使い方をする場合もあります。そういった新しい問題に取り組み、ACすることで自分の考えの引き出しを増やすことができます。
こうして問題を解くことを繰り返していくと、「問題を解く」こと自体が楽しくなります。これは自分にとって難しい、解くのに苦労した問題ほど解けたときの嬉しさも上がります。レートが停滞したとき、レートを上げることに固執せず、「問題を解く」ことに楽しさを見出すことで競プロを楽しく続けられると思います。
II.自分の力量を把握する
自分の力量を把握する、というのは競技プログラミングに限らずいろんな分野で大切なことだと思います。レートが伸びなくなったら、直近数回のコンテスト結果を振り返ってみるとよいかもしれません。
例えば「ABCのE問題が解けた回が少ない」という人がいたとき、これは「D問題までで時間を取られすぎた」からなのか、それとも「時間はあっても解法を思いつけなかった」からなのか、ということを考えます。前者であれば簡単な問題を短時間で解けるようになり、後者であればまず時間をかけてでも難しい問題を解けるようになることを目標とするのがよさそうです。
この設定した目標によってコンテストでより上位になるにはどんな問題を解くのがよいかということが見えてきます。ほかにも、「ダイクストラ法を使った解き方が分からない」のであればダイクストラ法を利用する問題を練習し、「桁DPが苦手」であれば、桁DPの問題を解くのがいいと思います。
とにかくたくさん問題を解く、という精進の仕方もありです（実際その方がうまくいく人もいると思います）が、自分に足りないものは何か（知識か、解く速度か、発想か、など）、それを補うには何をしたらよいかということを考えて精進してみるのもいいと思います。
III.誰にでも冷え（停滞期）はある
これが一番大事だと思います。
Twitterなどで見かけるつよつよな青コーダーや黄コーダー（あるいはもっと上）の方々がいますが、その人達も今の段階になるまでに冷え、あるいは停滞期を経験しているはずです（初回からABCでパフォーマンス2400を出すような方もいますが...）。実際、あるコンテストの順位表から「レーティング変動」を「差分」の昇順で見てみると下のような感じになっています。
ここで言いたいのは「誰でもレートが冷えたり、うまくいかなかったりすることがある」ということです。自分が冷えたときに、「自分はダメなんだ」と抱え込まず、「誰だって冷える、次のコンテストで温まるためにしばらくはこの分野の問題を解こう」とポジティブに考えることが大事だと思います。
まとめ
記事を書くにあたり過去の自分のsubmitを見返しながら記事を書いていたのですが、Rated初参加のAGCで0完していたり、昔のコードの書き方が変だったりで見返してみると面白く、けれど同時に自分の成長を実感していました。
競プロはやはり楽しいですし、色変ツイートをするとたくさんいいねを貰って嬉しくなり、競プロ界隈あったけえなぁ、と日々感じています。これからも競プロは続けていきたいです（研究・・・）。
それではよい競プロライフを～。
