EAFP

~ Easier to Ask for Forgiveness than Permission ~

自分のこと、それなりのエンジニアだと思ってたけど、緑コーダーになるのに1年かかった話

Atcoder Coding Interview 競技プログラミング

はじめに

2021年2月6日(ABC191) からAtcoderに参加し、2022年3月12日に緑色になりました

その後も、無事なんとか緑色で維持し続けています(2022年4月23日 rate 817)

atcoder.jp

巷では、数ヶ月で水色等になる人もいる中で、時間かけてるし、結構頑張っているけどなかなか結果が出ない人も多いのではないかと思います。 そういった人に対して「こういう人もいるんだ」とか「もう少し頑張って続けてみよう」とか思っていただければいいなと思って書きました。

進歩の速度は人それぞれで、かけられる時間も環境によってマチマチの中で、自分なりにやってきたことを共有し、1人でも多くの人に参考になることがあれば嬉しいです。

スペック

著者のスペックに関しては下記になります

  • エンジニア歴 約8年

    • NW & Securityの研究開発
      • インフラ構築や運用も経験
    • 様々な事業会社で開発(基本Web系)
      • Tech Leadも経験
    • SRE チームも立ち上げ、SRE & DRE(Data Reliability Engineer) として業務に従事
      • チームリーダも経験
    • MLエンジニアとしていくつかのProjectを経験
      • マーケティング関連(バイオ関連のデータソース)で、必要な予測モデルを生成し、納品
      • セキュリティ観点でのモデルを作成し、不正ユーザや、bot検知するモデルを作成し、実際に運用
    • PM/PL業でのマネジメント経験も少々

  • プログラミング

  • 家族構成 子供2人

    • 妻との共働きで、家事育児もあるため、エンジニアリングの勉強時間は限られている

取り組んだキッカケ

Atcoderに取り組んだのは、数年前に外資系の会社でSoftware Engineerの面接を受けたことがキッカケになりました。 自分自身、様々な業務でエンジニアとして働いてきて、それなりに自分のスキルに自信を持っていましたが、全く何も通用せず散々たる結果になりました。

qiita.com

有名なOSS commiterでも試験が解けずに落ちてしまうことがあるようです。 自分の場合は、一応情報系のことを大学で勉強しましたが、例えば「木構造」がどういうものなのかは知っていても、0からフルスクラッチで書いたことはなかったですし もし必要があれば、組み込みや3rd partyのライブラリを使って解決してました。

また、アルゴリズムに関しても、「ダイクストラ法」を知っていて、机上の手計算しながら説明はできるが、実際コードに短時間で落とし込むのは難しいといった感じでした。 計算量や、メモリ効率に関しても、そこまでシビアな中で開発しなかったのでその辺りも結構なんとなくできてしまったのかな？とも思います。

itnews.org

コーディングテストに関しては賛否があるようですが、シリコンバレーを中心としたIT企業では現状実施されていますし、自分自身「データ構造やアルゴリズム全然わからん」ってことに気づけたので、ちゃんと勉強したいな！と思うようになりました。

Atcoder 緑色のレベル感

過去、Atcoder社 社長のchokudaiさんは下記のように述べています

chokudai.hatenablog.com

緑色　(Cランク R800~1199　上位30%) 緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。 if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。

が、近年の参加人数の増加により、全体の底上げが図られているような気がしており 下記でも述べられていますが、若干上振れしていると自分も思っています

zenn.dev

個人的には、chokudaiさんのブログで言うところの緑と水色の中間くらいかな？と思ったりします

緑色になるまで

ratingの遷移は下記の通りですが、3つのステージに渡って、やったことを紹介できればと思います。

  1. 第一時成長期(約 3ヶ月)
  2. 伸び悩み期(約 8ヶ月)
  3. 再成長期(約 1ヶ月)

図1. Atcoderのratingの遷移

当初の計画

qiita.com

まず、上記の記事を見てどのように勉強していくかの計画を立てました。 正味、結構エンジニアやってきてるし、半年くらいで水色くらいにはなれるだろ！って思ってました(笑)

プログラミング言語としては、C++でいくか、Python3(pypy)のどちらを使うか迷いましたが、自分の使い慣れた言語がいいと思い、Python(pypy)でやることにしました。 C++と違い、速度面、競プロでよく使う標準ライブラリがない(ex. python では multisetがない) などの問題はありましたが、緑になる分にはそれほど大きな問題はないかなと、現時点では思っています。

第一時成長期(約 3ヶ月)

やったこととしては

  • 毎週 Atcoder Begineer Contest(ABC) に参加する

    • 下の子が0歳児の中、妻にはだいぶ迷惑をかけたが、なんとか時間を確保した
      • お風呂入れる時間が押してしまって、参加が遅れたりしたこともあったり、旅行先のホテルで寝かしつけた後、参戦したりしたこともあった

  • コンテスト以外の時間での、勉強時間の確保

    • なるべく毎日1時間以上コードを書く(2時間程度が理想)
    • 空き時間の確保や、他の趣味の時間を削る等で対応

  • 参加したコンテストの解説記事を書く

    • 結構時間とられるので、今はやめてしまってますが、近いうち再開しようと思っています。。。

kazu0716.hatenablog.com

github.com

github.com

github.com

qiita.com

この辺りは、 レッドコーダーが教える、競プロ・AtCoder上達のガイドライン で紹介されているものを踏襲した感じになります。 ただ、あまり勉強せずともABCのC問題くらいまでは解けることが多かった。が、D問題から先はさっぱりという感じでした。

図2. 茶色コーダになるまでのコンテスト結果

ABC Likeなコンテストでミスをしてratingを下げたこともありましたが、順調にrating を上げていき茶色になることができました。 また、基本データ構造の計算量に関しては知らないと、正しく計算量の見積もりができないので、下記を頭に叩き込みました。

wiki.python.org

伸び悩み期(約 8ヶ月)

茶色になってからですが、rating が伸び悩みます。ABC で C問題までしか解けないというのもあり、パフォーマンス相当のrating になったというのが大きな原因かと思いました。 なので、方針としては下記の2つを進めていくことにしました。

  • 早く、正確に現在解ける問題を解けるようになる
    • AtCoder Problems で、C問題までを早く、正確に解くことを進めた
    • 対象は、現行の形式になった、ABC126 よりも新しいものとした
      • 3ヶ月程度で完了した(2021/8/23 commit)

github.com

D問題以上特には、競技プログラミングでよく用いられるアルゴリズムやデータ構造が理解し、使いこなせる必要があるので、分野別　初中級者が解くべき過去問精選 100 問を解き進めるのですが、新しいアルゴリズムを勉強して理解して、例題を解くのは自分にとっては大変でした。

英単語や文法の暗記系と違って、アルゴリズムという取っ付きにくいものを理解して、使いこなせるようになるには、まとまって集中する時間を確保しないと難しく、隙間の30分やって、別の時間60分という形で進めると非常に効率が悪かったです。 子持ちで、フルタイムの仕事もあるので、平日/休日で決まった時間を確保することが難しく、特に育児は突然予期せぬことが起こるので、その都度対応する必要があったので、その度にストレスを感じてました。

また、「自分が解けなかった問題の復習」に関してもそうですが、解説読んでも理解できないし、考えているときに中断して、また再開して・・・という感じで、非常に苦しかったです。

停滞期に突入する

Atcoder ProblemでのD埋めも終盤に差し掛かり、必要なアルゴリズムも一通り勉強終わったけど、中々D問題がコンテスト中で解けないといったことが続きました。 正直、結構問題解いてるし、自分で解く分には解けることもあったので、なんでなのかなーと思ってましたが、そこまで深く考えてなかったです。

が、いよいよABCのD埋めも終わったところで、解いている問題量に対して、結果が伴ってきてない実感が強くなりました。 結論言うと、解いて終わりで復習してないってのが原因だと思うのですが、2度同じ問題解く気がしなかったので、競プロ典型 90 問を解くことにして、さらに演習を進めると言う選択をしました。 今思うと、勉強法を見直すべきだったかなーと思うので、今後取り組む人は、一度解いた問題も復習すると良いと思います。コンテスト後に解けなかった問題解いて、さらに1週間後解いてみるとかすると良いかなと思います。

また、解けなかった時に、解説見てもわからない時に、Youtubeでの解説動画を見てましたが、これをみて分かった気になっていたと言うのもつまづきの原因かもしれません

www.youtube.com

ガムシャラに問題を解き進める

競プロ典型 90 問を進めていきます。最初は★5以下の問題を解いていましたが、まずはD問題をコンテスト中に解けることが目標なので、★4以下にして、90問解きました。解いた問題に関しては、READMEにまとめてみたので、興味ある人はみていただけると良いかと思います。

github.com

また、DPが苦手だなーと思ったので、Educational DP Contest / DP まとめコンテストにも取り組みました。あまり難しい問題までやっても解けないので、J問題までやりました(「最適化問題」以外にも使えることがわかるという説明があったので。)。

github.com

非効率かもしれないですが、Dを埋めた後取り組んだのもあって、それなりにスムーズに解き進められて、かつ過去問の類題もあったので良い復習になったのかなと思います。

定期的にCでコケるが続く

ratingは長期的に見ると、少しづつ上がっているのですが、上がっては下がるを繰り返していました。これが、停滞期の原因であることに気づくのがとても遅かった気がします。

下記をみると顕著なのですが、定期的に -30 前後を食らっています。これは、C問題が解けなかったり、めちゃくちゃに時間かかったコンテストになります。

図3. 停滞期のコンテストの結果

コンテスト中に解けなかった問題で、かつ灰色difficulty(rate: 400以下の人で50%の確率で解けると思われる問題)を見返してみると、基本的な数学/ 情報科学の基礎力があれば解けるような問題でした。

なおかつ、コンテスト中に全く歯が立たない！と言うことではなく、サンプルは通ったけど、WAが取れずに終了してしまうという傾向があることがわかりました。 ミスの傾向としては、下記がある気がしています。

  • 問題文の読み間違い/ 勘違いをしている(ex. 前提となっている条件を見落として、勝手に問題を複雑にしている)
  • コーナーケースを想定できていない(ex. N=0の場合の場合分けなど)
  • 単純な実装ミス

debug 力は一朝一夕では身につかないので、この辺りの記事も見ながら気をつける！ということを続けました。

qiita.com

また、Cコケは不可避で起こったら、復習して周辺知識深め、また次頑張ればいい！と言う風に割り切ることにしたことも良かった気がします。 あまり、rating に拘らず、楽しんでやる心を改めて思い出して取り組むようにしました。

ここまで、勉強したアルゴリズム/データ構造に関して触れていないですが、2 個の基本アルゴリズムをマスターする！で触れられてるもの以外、特に勉強していないです。強いてあげると、

from pypyjit import set_param
set_param("max_unroll_recursion=-1")

といったことを +a で勉強しました。

再成長期(約 1ヶ月)

停滞期ながらも、ひたすら精進を続けていたら急にD問題が解けることが続くようになりました。 原因はわかりませんが、今まで解いてきた問題が身になったということに尽きるのかなと思います。

図4. 再成長期のコンテスト結果

また、停滞期であっても続けられたのは、前職のOB/OGのSlackで競プロやるメンバーのチャネルがあって、そこで結果を報告しあったり、教えてもらったりしたこと。 現在の会社でも、毎週競プロの勉強会を主催し続けてきたこと、その中で自分より遥か上の人たちの知識や、考え方を吸収したり、教えてもらえたこと。 が大きかったなーと思います。結構1人でやると、辛いし、なにやってんだろ？って思うことも多かったんですが、仲間がいることで乗り越えられたような気がします。

まとめ

1年以上の時間をかけて、合計600問以上の問題(取り組んだ問題は、下記にまとめています)を解くことで、緑色コーダになれました。進歩の速度は人それぞれで、他の人のブログをみると3ヶ月とかでなっている人も多い中だと、自分は相当遅い方かな？と思います。

github.com

ただ、アルゴリズム/ データ構造の自力だったり、かけられる時間だったりで、この期間は大きく変わるかな？と思うので、他人と比べず、自分のペースで精進続けられればいいかなと思います。 もし「全然茶色から抜けられない」とかって人がいれば焦らずコツコツ続けるのがいいかなと思います。モチベーション管理が難しければ、友達や職場で勉強会立ち上げて取り組んでみるのは1つ選択肢としてあるかもしれないです。

競プロって、データ構造/ アルゴリズム仕事にしたりしない場合、使わないし意味ないんじゃないか？みたいな議論もあります。が、個人的には、下記の点において大きく能力が向上したと感じるので、1エンジニアとしてやってよかった、今後の実務に生きる！と感じています。

  • 計算量/ メモリ効率も見積能力の大幅な向上
  • 問題を考察し、実装に落とす速度の大幅な向上
  • 基本ライブラリや言語仕様に詳しくなった
  • 実装速度の大幅な向上
  • コーナーケースの想定考察力向上(テスト書くときとかに役立ちそう)
  • コードを実行しない中でのdebug能力(静的解析)の大幅な向上

今後ですが、水色になるにあたっては、問題の考察力がたらないので、しっかり考察して筋の良い実装方針立てる力を磨いていければと思います。 水色いつなれるかわかりませんが、色変したらまた記事を書こうと思います。

長文にもかかわらず、最後まで読んでくださりありがとうございました。