AtCoderで緑コーダーになるまでにしたこと

###はじめに

　こんにちは、十六夜　龍という者です。

　先日の[ABC158](https://atcoder.jp/contests/abc158/tasks)（2020/03/07）にて晴れて**緑コーダー**になることができたので、その記念と、自分も何か競プロ界に貢献したいという思いで筆を持ちました。（まぁ、n番煎じな感はあるけれど……）


###目次（みたいなもの）

　以下の流れで書いています。

　自分の競プロ歴の振り返りという意も含んでいるので、その点はあしからず……。参考になるかもしれないところだけでも読んでみて下さい。

1.競プロはじめてから今までのレーティング変化
2.灰色と茶色の時に意識したこと
3.どんな精進をしてきたか
4.アルゴリズム、データ構造について


###1.競プロはじめてから今までのレーティング変化

　冒頭でも述べた通り、先日の[ABC158](https://atcoder.jp/contests/abc158/tasks)にて緑コーダーになりました。

　成績はABCDの4完28分＋ペナ5分×2で1406位、パフォも1227と水色で、ABCでは順位・パフォともに自己ベストでした。
![rate20200307.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/599106/3c5905dd-610d-c4fc-d1bb-b61026ecea07.png)
　これが僕のレーティング変化です。

　初コンテストが[ABC139](https://atcoder.jp/contests/abc139/tasks)（2020/09/01）なので、半年と1週間で緑に達しました。自分では今のところ停滞期もなく順調に来たな、という感じです。

　ただ以前「コンテスト参加回数が20回の人のレートの中央値は900弱」であるというデータを見た記憶があるので、それには及ばないくらいです。

 当面は4桁レートを目指します。（無論茶色に戻っているかもしれないけど…）


###2．灰色と茶色の時に意識したこと

　あくまで意識したことです。精進の内容などは後述です。

#####【灰色時代】
・とにかくコンテストに参加する

　知っての通り、AtCoderはコンテスト参加回数が少ないほどレートは下方修正されます。自分の実力を知るためにも、モチベーション維持のためにも、まずはとにもかくにもコンテストに参加するべきです。

　最近は月3~4回の頻度でABCがあるので可能なら毎回参加しましょう。

#####【茶色時代】
・問題を解くために最低限必要な知識を仕入れる

　これはとても大事だと思っています。というか大事です。

　ABCでいうと、A問題は入出力/ifが出来れば解けます。
　しかしB問題の一部（或いは大半？）からC問題、D問題の一部にかけては最低限の知識が無いと何もできません。

　ここで僕が言っている知識は、つまりは標準ライブラリのことです。
僕が必要だと考えるものをincludeファイルとセットで列挙してみます。
(関数の引数は省略してます。使い方は調べてください)

 **#include< iomanip >**　　 fixed,setprecision( )
　これを知らないと小数を出力するタイプの問題の大抵は落ちると思います。

**#include< vector >**　　　vector型
　int a[n]でも出来ますがvector< int > a(n)のほうがおすすめされます。

**#include< algorithm >**　　　max( ),min( ),sort( ),reverse( )など
　特にsort( )なんかは自分で実装するのはまどろっこしいので皆使っています。

**#include< string >**　　　string型,to_string( ),stoi( )
　string型はきちんと扱えるようになると便利です（整数の桁数を知るために一度string型に直してからsize( )をとったり）。

**#include< utility >**　　　pair型
　includeするときはpairじゃないので注意です。（これ、どうしてなんでしょう…？）

**#include< tuple >**　　　tuple型
　pair型やtuple型でvector型を使えば複数の値のセットを崩さずにsortしたりできるので便利です。というかこれが無いとまともに実装できる気のしない問題もあります。

**#include< set >**　　　set型
　所属判定が高速なので使い勝手が良いです。

**#include< map >**　　　map型
　setの上位互換みたいなものです。

**#include< math.h >**　　　sqrt( ),pow( ),ceil( ),floor( )など
　初めて使うと感動します。[ABC144](https://atcoder.jp/contests/abc144/tasks)なんかはこれのための回です。

　他にもqueue(及びpriprity queue)やdeque、stackなどがありますが、これは必ずしも必要ではない気がします（僕はコンテストで使ったことがないです）。

 #include< bits/stdc++.h >に今あげたのは全部入っています。使い方はAtCoderで説明されているので、[APG4b](https://atcoder.jp/contests/APG4b)を読んでください。

　これらを知っているかどうかで考察の幅も解ける問題も段違いなので、早めに習得したほうが良いと思います。


###3.どんな精進をしてきたか

　僕がしてきた精進の内容をまとめます。![Opera スナップショット_2020-03-08_180717_kenkoooo.com.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/599106/536929d3-45f2-d5a5-60c5-41f3fb39847d.png)
　これは[AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)のUser Pageから確認できる、過去のAC数などです。
　過去問学習に役立つサイトなので、僕はこのサイトを使って精進しています。![Opera スナップショット_2020-03-08_181548_kenkoooo.com.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/599106/a3fafdae-f600-009d-e155-8a5122d0186d.png)
　このようにいつどれだけ精進したかグラフで見れます。

　直近10日くらいで200問以上解いていますが、これはCOVID19によって中止になった期末テストへのやる気をABCのA問題埋めで消化した結果です。

（ところで”虚無埋め”と言われるA埋めだけど、埋めれるなら埋めといたほうが良い、というのが僕の考えです。見栄え良いし）

　さて、肝心の精進の内容ですが主に下の4つをやってきました。

・ABC過去問埋め
・AGP4bを履修する
・蟻本を読む
・AOJを解く

　ABCの過去問埋めは、先述した[AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)を主に使いました。

　[APG4b](https://atcoder.jp/contests/APG4b)には、先述した通り必要な知識が簡潔にまとめられています。僕は今でもちょくちょくコンテスト中にお世話になっています。

　蟻本は、大体の人が知っているかな……？典型問題やアルゴリズムがまとめられていて、とても役立つ本です。
　
　と言いつつ、僕はまだ初級編すら終わってません…。ただ、蟻本は読んで理解して解いたものがそのまま実力に加算できるくらい良質だと思います。

　最後にAOJについて。

　AOJ、正式には[AIZU ONLINE JUDGE](http://judge.u-aizu.ac.jp/onlinejudge/)にはLibraryとLessonからなるコースがあり、僕はその中の「プログラミング入門」を埋めました。![Opera スナップショット_2020-03-08_195420_onlinejudge.u-aizu.ac.jp.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/599106/80508a59-116c-03e4-5bcb-68dea6af4b32.png)
　math関数の使い方などは主にこのコースで勉強しました。

　僕はまだやっていませんが、「組み合わせ最適化」とか「グラフ」とか、内容ごとに詳しく学べる構造なのでAtCoderの過去問と合わせて解いてみると良いと思います。


###4．アルゴリズムとデータ構造について

　色と実力、求められる技術などは**chokudai**さんの[このブログ](http://chokudai.hatenablog.com/entry/2019/02/11/155904)が分かりやすいです。

　ただ、茶色や緑色に求められるアルゴリズムの技術あたりは僕の体感とはずれていたので、ここでは僕なりに使えたら良いアルゴリズムをまとめてみます。

・簡単めなDP
・順列列挙
・bit全探索
・素数判定
・累積和/しゃくとり法
・メモ化再帰
・modが出てくるような規模のコンビネーション計算

　僕は幅優先探索や深さ優先探索、最短距離算出（ダイクストラ法とか）を使えないので（勉強不足です…）、緑になるレベルではあまり「～～が使えないと無理」みたいなことをなさそうです。

　それよりも、丁寧なコーディング（WAになるケースを潰しておく）、素早いコーディング（ABCだったらCまで素早く解けるかどうかで大分違います）を心掛けたほうがいいのかな、とも思います。

　最善な状態を選択し続ける貪欲法が適用できる問題が多い印象なので、貪欲法で実装するためにも「2.灰色と茶色の時に意識したこと」で述べた最低限の知識を持っておくべきだと思います。


###さいごに

　緑になりたての僕が偉そうに「緑になるには～～したほうがいい」と述べていましたが、緑の下半分と上半分では大分差がある気もするのであくまで「茶色上位～緑下位」レベルのある人の考え方、くらいの認識で大丈夫です。

　想定よりも大分内容が増え、文も少し長めになりましたが、現在の僕の考えはまとめられた気がします。

　もし「茶色になった」「緑になった」という人がいたら、n番煎じだろうと是非記事を書いてみて下さい。自分の中でも整理がつきますし、競プロ界の裾野を広げることに貢献出来れば最高だと思います。

　それでは、ここまで読んでいただきありがとうございました。