はじめに
こんにちは、ken と申します。趣味は競技プログラミングです。
先日、 4 年間続けてきた AtCoder のレートがついに水色になりました。1
レートが灰色のころから水色コーダーになることを目標としていたので、ようやくといった感じです。
水色レートというのがどの程度の実力なのかについて触れておくと、Chokudai さんのブログ2に次のような記述があります。
水色 (B ランク R1200~1599 上位 15%)
水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。
半数以上の IT 企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。
自分がこのレベルになれてるのかどうかはわかりませんが、上位 15%のところまで到達できたというのは素直に嬉しいですね。
目標にしていた水色レートに到達したということで、この機会に私が AtCoder を始めてからレートが水色になるまでを時系列順に振り返りたいと思います。この記事がだれかの競プロのモチベを上げることに繋がれば幸いです。
自己紹介
- 昔から数学が好きで大学時代は数学を専攻（学部卒）
- 現在新卒一年目で、 Web 系の企業にバックエンドエンジニアとして勤務
- 使っているプログラミング言語は Python
AtCoder を始めた大学一年の春まではプログラミング経験は一切ありませんでした。
つまり私は AtCoder をきっかけとしてプログラミングを始め、現在エンジニアとして働いているというわけです。
そう考えると AtCoder は私の人生を変えたといっても過言ではないですね。もし AtCoder に出会わなかったら私は今頃何をしていたんでしょうか…
振り返り
灰色 → 茶色（2019/5/26~2019/9/15）
大学一年の春のこと、友達から「AtCoder っていう面白いサイトがあるんだけどやってみない？」というお誘いを受けました。前述したようにそれまでプログラミング経験は皆無でしたが、一度始めるとその奥深さにどんどんハマっていきました。
1 番初めは C++でコードを書いていて、途中から初心者向きであるという Python に乗り換えました。灰色時代は高度なアルゴリズムを覚えることはなく、ただただ簡単な問題を解いてプログラミングのイロハを覚えていきました。
そのうち ABC3 の C 問題くらいまでは解けるようになりプログラミングを始めてから 4 ヶ月後に茶色に上がることができました。
（ただ最近は競プロ er の実力がインフレしてきていているので、今は灰色から茶色に上がるだけでも二分探索や動的計画法のようなアルゴリズムを習得する必要があるかもしれません。）
先述したようにこの頃すでに目標とするレートを水色にしていました。（というのも AtCoder に誘ってくれた友達というのが水色コーダーだったため）
このころに覚えたアルゴリズム
特になし
茶色 → 緑色（2019/9/15〜2020/4/26）
この頃から、どうやらアルゴリズムを改善して計算量を削減することが競技プログラミングの醍醐味らしい ということに気づき、より競プロにのめりこむことになります。
この時期はよく出題される基本的なアルゴリズムについて勉強しました。勉強に使ったのはけんちょんさんの記事です。(これが無料で読めてしまっていいんですか？)
アルゴリズムを覚えたことで計算量という概念も知り、実装時には、思いついた解法の計算量が十分小さいかを意識するようになりました。
このころに覚えたアルゴリズム
- 深さ優先探索（DFS）
- 幅優先探索（BFS）
- 基本的な動的計画法（DP）
- 二分探索
- 累積和
停滞期（2020/4/26〜2022/2/5）
一度緑色に上がったもののその後再度茶色に落ちてしまい、そこからしばらくくの間茶色と緑色の間をいったりきたりすることになりました。
この時期が一番競プロのモチベが下がっていた時期になります、正直もうここが自分の限界なんじゃないかとさえ思いました。
安定して緑色になるためには ABC の D 問題の正解率を 8 割程度にする必要がありましたが、この頃の自分にとってその D 問題はなかなか鬼門で、コンテスト中に解ける確率というのは体感 3 割といったところでした。
どうしたものかと頭を抱えていたときに、次のメソッドを実践したところ、D 問題の正答率を大きくあげることが出来たのでここで紹介しておきます。
それは 「アルゴリズム列挙法」 です。4
問題が解けない時というのは、多くの場合視野が狭くなっています(個人の意見)
「え、これどうやんの.......」と思った瞬間解ける自信がなくなり、何となく思いついた解法に固執してイタズラに時間を消費していきます。そのようなドツボにハマるのを防ぐのが「アルゴリズム列挙法」です
問題に行き詰まったらまず知っているアルゴリズムを思いつく限り列挙します。そして上から順に「このアルゴリズムが使えそうにないか」を検討します。すると思ってもみなかったようなアルゴリズムがその問題を解く鍵になっていることに気づき、解に辿りつけることがあります。これは狭くなっている視野を広くするという狙いがあります。
実際 D 問題にもなると一見数列の問題かと思いきやグラフの問題に帰着できたり、全探索の問題だと思いきや構築ゲーだったりするのでこの対策はかなり効果的だったように思います。
そして D 問題の正解率が上がっていったころ、ようやく長かった停滞期を抜け出すことができ競プロへのモチベを取り戻すことになります。
緑色時代（2022/2/5〜2023/7/29）
競プロへのモチベを取り戻したものの、当時（大学 4 年の春！！）の私は就活をしないといけなかったので一旦競プロをお休みして就活にフルコミットしました。
（私は就活をするのが嫌で就活解禁まではほとんどなにもしていなかったのでこのときかなり焦っていました、みんな就活は早めに始めよう！）
そして就活が一段落した 2022 年の 5 月頃から本格的に競プロに復帰することになります。
そのときは大学の授業も週に 1 回とかだったので比較的時間に余裕があり、一日一問は競プロの問題を解くようにしていました。
下の画像で赤枠で囲っているのがその当時の精進量です（縦軸はその日解いた問題数を表しています。）
また、一日一問解くというのも、自分の実力より少し難し目の問題をチョイスして解くようにしていました、今振り返るとこの精進がレート上げに大きく貢献したのだろうなと思います。朝に今日解く問題を選び、大学への移動中やスーパーへの買い物中に考察し、夜に家に帰ったら実装をするというルーティンで生活していました。
するとその努力が功を奏して、みるみるうちにレートが上がっていきました。
（やはり精進‥‥!! 精進は全てを解決する‥‥!!）
この調子で水色いけるのでは…？と思っていたのですが、2023 年になると上京の準備やら卒業研究やらで次第に時間が取れなくなっていき、あっという間に大学を卒業し社会人になりました。
社会人になると案の定可処分時間が減り、学生の頃のように一日一問解くというルーティンはできなくなりましたが、できるだけコンテストには参加するようにし普段勉強できないぶんコンテストの復習はしっかり行いました。
社会人デビューしてから約 4 ヶ月たった 2023 年 7 月 29 日、ついに目標としていた水色コーダーになることができました。
このころに覚えたアルゴリズム
- ダイクストラ法（最短経路問題）
- ワーシャルフロイド法
- クラスカル法
- imos 法
- しゃくとり法
- トポロジカルソート
- ダブリング
- 座標圧縮
- Union-Find
- セグメントツリー
- 遅延評価セグメントツリー
効果的だと思った精進の方法
このセクションからは私が水色になるまでに色々精進してきた中で、特に効果的だと感じた方法について書いていこうと思います。
レートを上げたいなら難しい問題に挑戦するべき
緑コーダー時代、毎日 1 問解く習慣を持っていましたが、その当時、ただ毎日問題を解くだけでは実力向上が感じられませんでした。そこで気づいたのは、簡単な問題を連続して解くのではなく、自分の実力を少し超えるような問題に挑むこと が重要であるということです。
この挑戦を繰り返すことで、自分に負荷をかけ、成長の機会を増やすことができます。簡単な問題ばかりを解いていると、実力が上がった気になることがありますが、それだけだと高難度の問題に対応できるようにはならないと思います（ここは人によるところがあると思いますが…）。
復習をしっかり行う
受験勉強のような話になってしまいますが、やはり復習を行うことは大切です。コンテスト後、未解決の問題はしっかりと復習し、同じタイプの問題に再び遭遇したときは確実に正答できるように練習することが、レート向上への近道になると思います。そして復習の際は次の見出しで述べることを意識すると良いと思います。
解法を思いつくまでの思考プロセスをできる限り言語化する
問題の核心となるアルゴリズムや解法がどのようにして導き出されるのかを明確に言語化することは、他の問題への応用にも役立ちます。例として、二分探索を採用する問題における思考プロセスを考えてみましょう。
- 問題では数列が提示される。この数列はソートしても構わない。
- ソートすると、ある特定の数字までが条件 A を満たし、それを超える数字では満たさない。
- この状況は、二分探索によって効率的に解決できる。
このように解法を導く背後の思考を明確にすることで、理解が深まり応用力も高まります。
思い出の問題たち
C - HonestOrUnkind2
難しいで有名な C 問題です、当時茶色コーダーだった私はこの C 問題の難しさに唖然としました。。でも今見ると非常に教育的な問題で良問だなあと思います。
E - Packing Potatoes
この問題、解法がわかってもそれを実装するのが大変で何時間もウンウン頭を悩ませた思い出があります。こういうのをスルッと実装できるようになりたいですね
E - Warp
この問題はコンテスト終了 5 分前に AC して脳汁ぶちまけました、しかもそのとき実行時間制限 3sec のところ 2979ms で通したのでなおさら脳汁がやばかったです。これがあるから AtCoder はやめられません！！
最後に
本記事では私が水色コーダーになるまでの歩みを振り返ってみました。
短かったようですが、いつのまにか競プロを 4 年間も続けていることに驚きました、次は青コーダーを目指して頑張っていきたいところです。
最後にAtCoder Problemsから確認できる Achievement のタブを載せておきます。
ほとんど自分語りの記事でしたが、ここまで読んでいただきありがとうございました。