AtCoder水色になるまでにやったこと

自己紹介

はじめましてKotaroです．競プロのアカウント名はoctoにしています．AtCoder，Codeforces，LeetCode，Kaggleを暇な時間に解いています．
私は現在19歳，高専という５年制の専門学校の電気情報工学科５年です．
電気情報工学科とは言いますが，その実態は電気９：情報１ぐらいのほぼ電気科です．そのため授業ではほとんどコードを書くことがなく，４年の段階でクラスの半数程度の人間しかFizzBuzzを書かけない程度の悲惨な状態…。私もその１人で，プログラムが書けるようになりたくて高専に入ったのに４年たってすっかり電気に染まっていました．

競プロを始めたきっかけ

そんな電気に染まった私が競プロを始めたきっかけは高専プログラミングコンテストでした．第29回大会の課題部門で提出する作品の，元となる研究のお手伝いをしていたことから，急遽メンバー入りが決定し，全国大会に出場できることが決まったのです．研究のお手伝いをしていたとはいえ，やっていたことはICカードのシール貼りや簡単な資料作成などの雑用でした．
もちろんプロコンで戦力になれるはずもなく，同級生がスラスラとコードを書いていく中で，僕は資料作成や教員たち，市役所の方との仲介役を担いました(苦笑)．
学校の授業では上位にいることができたので，自分は人並みにプログラムができると思い込んでいたのですが，同級生とこれほども差があるのかと愕然としました．そして，卒業までに強くなりたいと思い，プログラミングを独学することを決めました．

紙ベースで勉強するのは違う気がしてWebサービスを中心に勉強を進めていくことにしました．ProgateとドットインストールでWebについての勉強を，AtCoderでアルゴリズムの勉強をしコーディングに慣れる．このように勉強を進めていく中で，AtCoderにはまり，Codeforces，LeetCode，Kaggleにも手を出し，完全に競プロerになりました(笑)．

水色になるまでにやったこと

チーター本で勉強

競プロで強くなるためにはコンテストに参加して，解説を見て解ける問題を増やしていくことも大切ですが，最初からそのやり方で進めていくのは難しいと思います．灰色の内はコンテストに参加しても２問解けるか解けないか，頑張って勉強する前にやる気を失ってしまいます．
はじめはチーター本や蟻本などの教科書で勉強することが手っ取り早いと思います．
私のレートを見てください．線で示す部分がチーター本を使い始めたタイミングです．

成長の差が一目瞭然かと思います．チーター本をやることでABCで善戦できるようになり，AtCoderがより楽しくなります．蟻本は少しレベルが高いので，チーター本を終わらせてからやることをお勧めします．私は緑になってから蟻本を始めました．

水色になるまでに身に着けた知識

１．vector, set, map, priority_queueを使えるようにする

それぞれ，配列，集合，辞書（二分探索木，ハッシュリスト），ヒープに対応します．多くのアルゴリズムではこれが使える前提で考えられています．これらのデータ構造を使いこなすことによって問題を簡単に解くことができます．ABCのA~C問題でデータ構造の使い方に慣れることが成長への第一歩です．

2．全探索を書けるようにする

DFS，BFSがすべてのアルゴリズムの基本です．高度なアルゴリズムは全探索を高速化したものであることが多いため，全探索が書けないことには次に進むことができません．逆に，BFS，DFSが分かればすぐに簡単なDPが書けるようになります．

3．高速化のテクニック（累積和，二分探索）

累積和は３行あれば実装できる簡単なアルゴリズムですが，その効果は絶大です．計算量を1/n倍にできるのです．簡単に高速化できるため，出題されることが多いです．計算時間が間に合わない場合にはまず累積和を疑うことも一つの手です．
二分探索もよく出てきます．簡単に書けて，O(n)をO(log n)に改善できるため非常に有用です．身に着けておかないと解けない問題が多くあります．

４．Union Find Tree

これは時々出てくるテクニックです．集合を扱う際に，Union Find Treeを用いると，同じ集合に属しているかどうか，集合の大きさはどれぐらいかの計算をほぼO(1)で行うことができます．ですが水色になるまでに必須ではないでしょう．私はこれまでに１回しか使いませんでした．

５．DP

私はDPがまだ苦手で，勉強中です．基本的なものは書けるようにしておく方がよいでしょう．DPを勉強することで，思考力を身につけることができます．また，400点以上の問題はDPで解けることが多いため，青や黄色になるためには必須といえるでしょう．私もこれから頑張って勉強します．

まとめ

私が水色になるまでに取り組んだことは以上です．Union Find TreeとDPは必須ではないと思うので水色になるまでに要求される知識は実質３つだけです．これらの技術を身に着けたらあとは精進あるのみ！アルゴリズムの考え方は問題を多く解いていく中でしか身につかないと思います．
はじめはFizzBuzzがなんとか書ける程度の実力しかなかった人間でも水色になることができました．皆さんも頑張って一緒に強くなっていきましょう！