AtCoderで青になるまでにやったこと
年末のAGC030で、AtCoderで青になることができました。2018年中に青になれたのが嬉しいので、青になるまでにやったことをまとめていこうと思います。
・過去問を解く
ABC-D、AGC-Bの400〜600点問題を積極的に、７割くらい埋めました。400を埋めきってない人でも、解きやすい500~600点問題はそれなりに存在するのでやっていくといいと思います。
・バチャをやる
AtCoder Virtual Contest様にて、何度か「青になりたい！」というタイトルのバーチャルコンテストを開きました。近いレベルの人をたくさん集めて難しめのバチャをやると、ライバルの存在やコンテストの戦い方が意識できて良かったと思います。参加してくださったみなさま、どうもありがとうございました。
・蟻本を買う
大学の教科書に蟻本が置いてあったので、つい買ってしまいました。今のところ辞書的な活用法しかしていませんが、すごく便利で良い本だと思います。
・標準的な機能を学ぶ
水色には300点早解きor時々400点に成功で上がれますが、青を狙うにあたって400点問題は落とせません。ですが、400点以上の問題になると、さすがにif文とfor文、配列だけで実装しきるのは（不可能ではないはずですが）難しい問題が増え、プログラミング初心者には厳しいものがあります。
ここでは、「私が」知って見える世界が変わった標準的な機能を紹介していきたいと思います。ちなみに私はJavaを使ってるので、みなさんの言語には似たようなものがないかもしれません、なかったらごめんなさい。
・HashMap
学んだのは緑時代ですが、これは最強クラスのデータ構造と思います。値の範囲が大きいデータを、何回出てきたか数えられたり、座標圧縮をしたり、Objectから整数への対応などを簡単に作ったりすることができます。神。
素因数分解なんかもやりやすい。
・TreeMap
キーを取り出すときに、ソートがされていて嬉しいHashMapです。
・Queue、Stack
幅優先探索や深さ優先探索に使うイメージが強そうですが、これもめちゃくちゃ便利です。道中でものを拾って、「古い」or「新しい」ものから順に使うというようなことがしたいときに便利です。
・Deque
一番古いのも新しいのもすぐ取り出せます。時々使いたくなる問題があります。
・Priority_queue
Queue、Stackの上位互換（計算時間を除けば）。かなり強いと思います。これがないと解けない問題、多いんじゃないでしょうか。便利すぎて「いいの？」ってなりがちです。
・ListやSet、Map型の配列
グラフ系の問題などを解くにあたっては半分必須っぽい気がします。
・拡張for文
これもグラフ系の問題には必須っぽいです。ある頂点から伸びてる辺を全部見るなどできます。MapのKeySetなども全部さらえます。嬉しみ。
・bit演算
bit系の問題を解いたり、bitDPをするときに、「うーん、2のi乗で割って、それを2で割ったあまりを...」みたいなのがめちゃくちゃ簡単に書けて、しかも高速に動作します。
・Class
Pairなどを作れます。Pairが欲しくなることはめちゃくちゃ多いので…
・Comparator
整数を逆順にソートしたいくらいなら−１倍したものをぶち込んで、実際に使うときに元に戻せばいいのですが、Objectをソートしたくなる時があります。そんなときにComparatorが使えるといいですね。
・基本的なアルゴリズム、データ構造を学ぶ
AtCoderは典型そのままはあまり出ませんが、問題を言い換えていくと典型になることは無数にあります。そんなとき、解けたのに書けない…ってなると悲しいし、上がるはずだったレートをみすみすドブに捨てる行為になることも多々あります。そんな悲劇を回避するために、典型アルゴリズムは書けるようにしたほうが良さそうです。
・二分探索
書けると嬉しいです。値の検索だけでなく、何かを決め打ちすると可不可を判定するだけの問題になったりするときにも使えます。
・最短経路アルゴリズム
ワーシャルフロイド、ベルマンフォード、ダイクストラ全部使えるようになっておくと良いです。400点問題に全部あったはずです。茶色の頃の話ですが、ダイクストラで簡単に解けるとわかった問題が、全く何も書けずに虚無をしたことがあります。
・Union-find木
これも400点程度でも時々使う問題が出ます（良く考えるとBFSやDFSでも良かったりするものもありますが）。経路圧縮だけなら割と書きやすいです。
・他
BIT、セグ木、平衡二分探索木、フローなども勉強（写経）しましたが、AtCoderで青になるのに使うことはあまりなさそうではあります。当然やっておいて損はないと思います。
最後に
黄色目指して頑張ります！！！！！！！！！！！！！！！！！！！！！！！！
