AtCoder青色になりました. [色変記事]

初めてのQitta記事になる.　簡単な自己紹介をする.
* 名前:Kazun
* 大学4年生 大学では数学を勉強してる.

今回はコロナ渦の影響により以前から存在を知っていた競技プログラミングにおいて, AtCoder で<b><font color="blue">青色</font></b>になったので, <b><font color="blue">青色</font></b>になるまでの簡単な経歴と習得した事柄をまとめてみた.

#競技プログラミングの歴史

##競技プログラミングとの出会い
　競技プログラミングという存在を知ったのは大学1年生で, 大学の掲示板に競技プログラミングへの案内があった(サークルとは別物). 当時は「こんなものがあるんだ程度であった.」

##意識していなかった準備
 大学のアルゴリズムの講義で計算量におけるオーダー記法の定義から, 動的計画法, グラフの最短距離, 部分和問題などといった多くのことを学んだ. 当時は興味からとった講義だが, 今見てみるとこれによって全くの初心者から半年で<b><font color="blue">青色</font></b>になった大きな要因の一つではないかと思う.

##競技プログラミングの世界へ
 競技プログラミングの世界に踏み入ることになったのは, 2020年5月17日である. この日に開催された AtCoder Beginner Contest 168 の [C問題 :(Colon)](https://atcoder.jp/contests/abc168/tasks/abc168_c) において, 余弦定理がTwitterのトレンド入りし, それを見て, 問題に興味を持ち, 競技プログラミングの世界に入ることになった.

##いざ,初参戦
 競技プログラミングの世界へ入ることを決めた翌週から早速コンテストに参戦することになった. しかし, ABCとAGCの違いすらわかっていなかった当時のデビューコンテストは [AtCoder Grand Contest 044](https://atcoder.jp/contests/agc044) であり, [A問題](https://atcoder.jp/contests/agc044/tasks/agc044_a) から(変更後の)Diff <font color="blue">1828</font> という超難問回である. その結果当然成すすべなく, 0完 Performance <font color="blown">540</font> でRating <font color="gray"> 28 </font> という残念な結果になってしまった.[^1]

[^1]: 実際, この難しさの影響か, 次の[AtCoder Grand Contest 045](https://atcoder.jp/contests/agc045) から<font color="cyan">1200</font>-Ratedになった(この回の[A問題](https://atcoder.jp/contests/agc045/tasks/agc045_a)が更に難しかったのだが...).

##いざ,初参戦2
 あまりに残念すぎるデビュー戦の次もやや適正ではない AtCoder Regular Contest 級の [NOMURA プログラミングコンテスト 2020](https://atcoder.jp/contests/nomura2020) であった. この回は奇跡的に[C問題](https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c) を正解することができ, Performance <font color="cyan">1341</font> で Rating <font color="gray">299</font> にジャンプアップした. (この後の2回のコンテストでRatingは<font color="gray">299</font>→<font color="brown">729</font>→<font color="green">1087</font>と変化した.)

##青色への挑戦
 <font color="cyan">水色</font>を達成し, 次は<font color="blue">青色</font>へ挑戦することにした. とりあえずAtCoder ProblemsのRecommendationのうち, Easyを中心に解いていった. というのも, Diff $X$ であることの定義がRating $X$ の人が半分解けるという意味なので, 半々で解けるか解けないかの問題よりも, もっと確実に取らなくてはいけない問題を確実にした方がいいのではないかという考えがあったためである. 実際, AtCoder Problemsによる推測で80%を超えるような問題でもわからないということがあり,[^2] もし本番だとPerformanceが悲しいことになっていたので, この考え方にしてよかったのではないかと思う.

[^2]: 100%でないのだから当たり前だと言われてしまったらそれまでだが...

##青色の達成
 2020年10月から2年ぶりに復活したAtCoder Regular Contestが自分にあっているらしく, 開幕5連続でRatingが上昇した結果, 青色リーチに手を付ける事ができた. そんな中迎えた [AtCoder Beginner Contest 184](https://atcoder.jp/contests/abc184)で[F問題](https://atcoder.jp/contests/abc184/tasks/abc184_f) が非常に簡単な回であったこともあり, 悲願の初パーフェクトを達成し, Performance <font color="blue">1956</font> (個人的ベスト2)でRating <font color="blue">1617</font>となり,<font color="blue">青色</font>になることができた.

#習得済みの事柄
以下で自分がある程度は習得したと思われる事柄を列挙する. ただし, 自分の興味によって習得したものもあるので, 必ずしもここに書かれているものが青色になるために必要なことではない. また, ★があるものはライブラリー化した.

##アルゴリズム, テクニック
* 全探索 ★
* 素数判定 ★
* 素因数分解 ($O(\sqrt{N})$ バージョン) ★
* 剰余環 (加減乗除, 累乗, 平方根, 原始根)★
* 行列 ★
* グラフ(グラフの有向性,辺の重みの有無それぞれ計4通り) ★
* 二部探索 ★
* Imos法 ★, 累積和
* Doubling
* 尺取法
* Flow ★, 最小費用流 ★
* Grundy数
* 畳み込み ★
* 2-SAT ★
* 形式的ベキ級数
* 動的計画法

##データ構造
* Union Find ★
* (Lazy) Segment Tree ★
* Binary Indexed Tree ★

#解いた問題数
* AtCoder:661問
* yukicoder:310問
* AOI:数問(Verify専用)
* Library Checker:(Verify専用)

#これから
せっかく<b><font color="blue">青色</font></b>になったのだから, 次の目標としては AtCode Beginner Contest 卒業となる<b><font color="yellow">黄色</font></b> (Rating 2000)である. これまで以上に厳しい戦いになると思うが, マイペースに着実に Rate を稼いでいきたいと思う.