🟤Atcoder茶色になったので備忘録

　茶色になる前のことは茶色になった今のうちしか書くことができないと思うので備忘録として残しておく。

Atcoderを始める前のレベル

C言語にて簡単な文字列操作ができる(atoi, itoa等の再実装)。
再帰を使ってフィボナッチ数列作れる。
計算量を考慮しない多重ループによる探索の実装ができる。
高校数学程度の基礎知識がある(permutation, combination, 三次関数, 微積分, etc...)。
線形リストや木などの構造は実装できなくはない（要時間）。
 C言語のみなのでSTLを知らない。

Atcoderを始めてから一年弱の取り組み方

　ABCではB問題までは詰まらずに実装できており、C問題は体感３回に１回落とすくらい。早解きはできない。C言語で実装しており、C++の他人の解説コードはあまり理解できなかった。
Cで解くことにこだわりを持っておりquicksortやbinary_searchなどは手書きで実装していた。
Atcoderに関わることを辞めなければ少しずつでも上達していくだろうと考え、少なくともABCにはなるべく参加するようにしていた。
やる気があるときはレートよりもAtcoderに対するモチベを保つという目的から、Atcoder probremsにて簡単な灰diff埋めをしていた。埋めるの気持ちいい。

１年後

　そろそろ茶色になった方が良いのではないかと焦り始める。この頃から人の色変記事、競プロの取り組み方、茶diffまでのアルゴリズム集などの記事を読み始める。
具体的にはけんちょん氏の記事全般、E869120氏の記事全般。
まずはC++を読めないことには解説を読むこともできないということでCへのこだわりを捨ててAPG4bを解き始め、ついでにプログラミングコンテスト攻略のためのアルゴリズムとデータ構造を買う(通称らせん本？AOJ本？)

やったこと

　E869120氏の目指せ水色コーダー記事を参考にSTLのリスト、アルゴリズムのリストを作る。それについての問題を集めて一つのSTL、アルゴリズムについて5~10問ほど練習する。
15分ほど考えて思いつかない場合は解説を見て、コードが載っていない場合は人の提出コードを読む。提出の早いコードの方がシンプルで分かりやすいことが多い気がする。翌日リベンジ。
上記何も見なくても提出できるようになるまで繰り返す。
目指せ茶色コーダーの内容は最近ではよっぽど早解きできない限り灰色上位くらいではないだろうか？(2021/07/19時点)

vector, string, dequeue, set(multiset), map(multimap), sort, lower_bound, upper_bound, next_permutation, bitset, stack, queue, priority_queue, __gcd
二分探索, 深さ優先探索, 幅優先探索, 素数判定, べき乗計算, 累積和, いもす法
動的計画法
この辺の練習をした。グラフ理論はyoutubeにて早稲田大学 早水桃子研究室channel等を参考にした。

　なるべく早く解くよう意識し始めた。目指せ水色コーダーにも書いてあるが、ABCコンテストのCからDには難易度の開きがあることが多く、Dを解けるようになるというよりかCまで早く解けるようになることが重要、今まで意識していなかったが茶色になるにはやっぱり必要な気がしたので。
安定してDを解けるようになると茶色から飛んで緑、水色くらいになれるはず。

 #include  <bits/stdc++.h>
using namespace std;
int main()
{
    
}

とりあえずvscodeにて上記コードを張り付けたa.cpp b.cpp c.cpp d.cppくらいまでのファイルを予め作ってみたり、二乗判定、素数判定あたりの関数をコピペできるように集めてみたりしている。

その他と所感

　全探索と一息に行っても色々なパターンがある。全然簡単じゃない。つらい。まだまだC問題が解けなくて灰色との間をうろうろすると思う。Cが解けないとへこむので、今は名前付けして○○(解法として使用するアルゴリズムやSTL)のコレクションが一つ増えたのでまぁ良しとするか、くらいに考えるようにしている。
　気分の上下が激しくなると落ちた時のストレスでよりつらくなるので、なるべく植物のような心で受けつづけたい。でも嬉しいものは嬉しい。
　問題を分類して練習するという方法を気に入っている。個人的にはdiffだけを指針に解き続けるよりかは、一つ一つできることが増えてレベルアップを実感できるので良い。
　深さ優先探索を使えるようになってから一つレベルアップした気がする。bit全探索とかも深さ優先探索でどうにか実装できたりするので、汎用的で便利。いろいろとカバーしてくれてる。
　参考書は買えば買うほど良い気がしてきている。分野ごとの問題を集めるときにその方が便利なので。けんちょん本とかPAST本とかも買うつもり。

とりあえず、今年の目標であった茶色になる、を達成できてよかった。