atcoderで入緑しました
こんにちは。sekiです。
タイトルの通り、つい先日atcoderで緑ランクになりました。
最初にお断りしておくと、自分はプログラミング未経験の状態からatcoderに参加したわけじゃないし、３〜４ヶ月での緑ランク到達は、別に目を見張るような記録ではないです。
ですが、競技プログラミングに触れたことないごくふつうのエンジニアが、緑ランクになるまでの学習の記録として、記事に残しておこうと思います。
atcoderとは
わざわざここで説明するまでもないと思いますが、atcoderについて簡単に説明します。
atcoderとは、web上で「競技プログラミング」のコンテストを開催しているサービスです。
競技プログラミングというと敷居が高そうで、ものすごく頭のいい人たちが、我々の想像を超えるレベルでしのぎを削っているイメージがありますが、atcoderでは問題の難易度のレンジが広く、プログラミング初心者でも取り組める問題があります。
atcoderではコンテストに参加することで自分のレートを上げていくのですが、そのレートの区分けが「色」で行われています。
詳しくは以下のatcoder社長の記事を参考にしていただくとして、簡単に説明すると、今回到達した「緑」は、開始地点の「灰色」の２段階上のランクになります。
（上記の記事に各色のレベル感が書かれていますが、執筆されたときより参加人数が増えたことで、全体的に各色に対して求められる内容が一段階あがっているような気がします。体感ですが、、、）
はじめる前の自分の状態
atcoderをはじめる前の自分はだいたいこんな感じでした。
エンジニア歴２年ちょっと（情報系の専攻じゃなくて、未経験から新卒入社でweb系エンジニアに）
pythonはある程度書ける
キューとスタックは基本情報技術者試験の勉強でやったなあ、くらい
並び替えにいろんなやり方があるっていうのは大人のピタゴラスイッチで見たことある
計算量でO(N)みたいな表記を見たことあるけどよくわかってない
学習のポイント
自分が緑ランクに到達するまでの取り組みを振り返って、こういうふうに学習を進めるのがよさそう、というのを簡単にまとめてみます。
1. 全体を理解するために本を買う
自分が大学時代に情報系専攻ではなかったということもあり、これまでアルゴリズムやデータ構造を体系的に学ぶ機会がありませんでした。
なので最初に、競技プログラミングではどういったことが求められるのか、というのを知るために、以下の本を購入しました。
正直内容を全部完璧に理解しているわけではないですが、これで求められるもののイメージをつけられたのは非常によかったと思います。
これまで競技プログラミングに取り組んだことがない人は、まずは基礎的な内容を網羅した本を買い、全体感を掴むことをおすすめします。
2. 過去問をひたすらやる
何事も結局実践の繰り返しがレベルアップの一番の近道なので、ひたすら過去問をやるのがいいです。自分もこれが一番レベルアップの実感がありました。
atcoder problemsというサービスがあり、こちらでは各問題の難易度を、「あるレートの人が50%の確率で解ける」という観点で算出したdifficulty（みんなdiffって呼んでる）という指標で表しています。
個人的な感覚として、自分の現在のレート+400以内のdiffの問題を一通り解くとよいと思います。
3. 芋づる式にテクニックを学ぶ
過去問を解いていくと、わからない問題の解答を調べるために検索することが多くあると思います。
その中で知らないアルゴリズムやデータ構造が紹介されていたり、解き方が複数存在するような場合に、出てきた新しい知識を簡単なメモとして残しておきます。
そしてあとでメモした内容を調べてさらに学習を進めるのですが、このときに関連した知識としてまた新しいアルゴリズムやデータ構造が出てくると思うので、それをメモに残し、また調べる、というのを繰り返していきます。
こうやって蓄積されたメモによって自分のできたこと/できていないことが可視化されることは非常に大事で、今後の学習の指針が掴みやすくなるし、やったことに対する達成感にもつながります。
4. 頻出アルゴリズムはテンプレを用意しておく
頻出のアルゴリズムやデータ構造を問題のたびに実装するのは面倒なので、コピペしてすぐ使える状態のものを手元に用意しておくのがおすすめです。
前述した芋づる式に学ぶ学習の中でこれを作成していくと、それなりの量できあがるはずです。
たいていはネットにそのまま使える状態で貼ってあることが多いのですが、ポイントとして、これを手元にコピペするときに実装の意味をちゃんと理解するようにしましょう。
いざコンテストで問題を解くというときに、実装を解釈するのに時間がかかってしまうのでは結局意味がなくなってしまうので、概念と実装をしっかりと結びつけて理解するとよいです。
5. ARCはやらなくていい
atcoder上ではさまざまな種類のコンテストが開催されていて、その中でも一番基本的なAtcoder Beginner Contest（ABC）と、中級者以上向けのAtcoder Regular Contest（ARC）がよく開催されています。
はじめははやくレートを上げたいと思って、コンテストの参加回数を増やすためにARCにも挑戦していたんですが、A問題も完答できず、逆にレートが下がりました。
よく考えればわかることなんですが、ARCの点数配分的に、A問題は300点であることが多く、これはABCのC問題と同じ点数です。
同様に、ARCのB問題は400ないし500点で、これはABCのD問題やE, F問題と同じです。
あくまで単純な点数という観点での話ですが、ABCでそもそもDやE問題まで安定して解ける状態にならなければ、ARCで苦戦することは上記の考え方からすると当たり前で、緑ランク以前では基本的にそういう状態でない人がほとんどだと思います。
（もちろん、同じD問題でも難易度が毎回一緒なわけではないし、ABCとARCでは問題の性質が違うので、必ずしも単純に比較できるわけではないんですが、、、）
そのため、参加するコンテストは基本的にABCのみで十分だと思います。
6. 計算量の感覚を身につける
計算量とは、簡単にいうとアルゴリズムの効率の良さです。
atcoderでは実行制限時間があり、ただ答えが出せればいいだけでなく、この制限時間以内に答えを出すようにプログラムを書く必要があります。
出題される問題の制約を見たときに、「これはO(N^2)は間に合わなそうだからこの方法は無理で、O(NlogN)とかO(N)ならいけそう、てことは使えそうな方法はこれだな」とか、言語組み込みのものを使うときに「この関数はO(N)だからこのforの中では使えないな」というように、事前にダメな実装を防ぐことができます。
特に言語組み込みのものに関しては、一度調べておくとよいです。
自分はpythonで取り組んだので、以下記事を参考にしました。
参加してよかったと思うこと
自分がweb系のエンジニアということもあり、学習したアルゴリズムやデータ構造が業務でそのまま使えることはあまりないのですが、緑ランクになるまで学習を続けてきて、自分がよかったと思う部分を挙げてみました。
1. コードを書く機会を確保できた
最近業務のほうで上流側に移りつつあり、コードを書く機会が少なくなってきていました。
コードを書く機会を増やすために個人開発をするでもいいんですが、それだとちょっと労力大きいなあ、と感じていたので、そういった意味ですごく手軽にコードを書く機会が増やせるのはすごく助かっています。
（まあいずれはちゃんと個人開発もやりたいし、むしろやんないといけないんですけどね、、）
2. アルゴリズムにビビらなくなった
前述の通り、ことWeb系の開発では、特殊なデータ構造を用意したり、難解なアルゴリズムを適用することはあまりないのですが、新しく登場した技術について調べたり、パフォーマンスを意識した開発の際に出てくるいろんな概念を理解するハードルが、以前に比べて低くなったように思います。
（最近だとB-Treeとか、ガベージコレクションのアルゴリズムとかを調べて、ある程度わかるようになってきました）
原理、基礎を知ることは汎用的な知識の獲得のために大事なので、ここがやりやすくなったのは、エンジニアとしてスキルアップしていく中で非常に大きいと思います。
次の目標
緑を達成したので、順当にいけば次は水色（緑の１つ上）が目標です。
ただ、これまでまだ１回も水色パフォ（1200以上）を出せたことがないので、正直時間はかかりそうだな、と思っています。
できれば今年度中に達成して、会社での評価にうまくつなげられたらいいな、とは思いつつも、当面はこれまでの学習をゆるーく継続して、着実にレートを上げていくことを意識していきたいと思います。
この記事が気に入ったらサポートをしてみませんか？