Atcoderで緑色になった件について
はじめまして。slyly1373と言います。主に自分の備忘録として記事を書きました。茶→緑なので需要はないです！（断言）
1, 自己紹介
競プロ歴：５か月（現時点）
Twitter：@slyly1373（普通の垢）@slyly1373_2（精進日記）
８月半ばからAtcoderのコンテストに参加し始めました。始めたきっかけは、同じクラスに競プロを熱心にやっている人がいたからです。パソコン自体は小学3年生の時から使用しています。大学受験の化学を極めたことがあります。好きな科目は化学なので化学系の学科に進学したいと思います。大学に入ってから将棋ウォーズをしています。(最近好調なので一気に勝ち上がりたい！)
2, 使用言語
・Ruby（主に灰色→茶色）・・・簡潔なので好きです
・PyPy (Python)（主に茶色→緑色）・・・速さを理由に乗り換えました
・C++、Crystal(Rubyの上位互換) ・・・勉強中
基本的に自分の好きな言語を選べば良いと言われていますが、PythonやRubyのように遅い言語だとO(10**7)あたりの厳しい計算量が通らずにTLEすることがあるので、C++やRustのように速い言語が「便利」なのは間違いないと思います。
私がそうだった(今でもそうです！)のですが、遅い言語を用いた上で計算量を落とす工夫をするのは、初心者にとってかなり難しかった(できなかった)ので、茶色で停滞した時にRubyからPyPyへと乗り換えました。O(10**7)が余裕を持って通るのは安心感があるので、この選択は間違いではなかったと思っています。
なぜC++にしなかったかって？？？ それは、私が逆張りだからであってPythonとRubyの構文がよく似ていて移行がしやすかったからです！
3, 精進
グラフの通りです。精進した割には結果がついてこないのが現状ですね...(ﾟoﾟ;...精進グラフからすると今頃水色らしい。(本当か？)
現時点でどれも中途半端ですが、４月が終わるまでに灰、茶、緑、水を全部埋めるつもりです。１日茶以上を最低３問解けば実現できるので頑張ります。(←新歓の時期は忙しいぞ！！)
灰色の虚無埋めは人により好みが分かれますが、少なくとも灰色から茶中位までは早解きの練習だと思って頑張ってやってみました。文字列の問題は特に実戦で役立った気がします。
茶色上位までは比較的すぐ上がったにも関わらず、なかなか緑になれなかった（２ヶ月くらい無駄にした！）理由と関係あるかどうかは分かりませんが、茶色を全部埋めた方が良かったと思います。ABCのA~Cでよく出る問題が結構混ざっているので茶色は大事です！
4, 勉強したアルゴリズム・手筋
私が灰色・茶色で勉強したものです。
（リンクからは私が学ぶきっかけとなった問題に飛べます。ネタバレを避けたい方はクリックしないでください...）
1, 灰色時
・累積和（一番最初に遭遇したTLEの壁、計算量の重要さに気づく）
・二分探索（条件を満たす個数を求める簡単なやつ）
・繰り返し２乗法（逆元）（Pythonだとpow関数で）、ダブリング
・ワーシャル-フロイド法（全点最短経路）
・尺取法
・UnionFind（これが使えるようになったのが大きかった！）
2, 茶色時
・いもす法
・クラスカル法、プリム法（最小全域木）←Atcoderでは未遭遇
・ナップサックDP（←この問題自体は難しい）
・xor全般の勉強（xorは知らないと手が出なかった）
・dequeを用いたグラフのDFS・BFS（これが使えるようになったのが大きかった！）
3, 勉強はしたが十分に身についていないもの...Σ(ﾟﾛﾟ;)
・貪欲法（正しい貪欲を見つけるのは難しい）
・シュミュレーションする問題（いつでも大事な基本だと思う）
・一部のDP
・座圧（！？）
特に役立ったのは、Atcoder Typical Contest(ATC)（←１回目、２回目）とAtcoder Educational DP Contest(EDPC)です。全部はできていませんが、前半部分だけでもかなりの学習効果がありました！
蟻本にも上記のことは載っていますが、蟻本は気になったところを適宜読むという感じでした。何よりC++ベースの解説なので苦しい ...s(・・;)
5, 辛うじて身についたコツ
1, 制約の活用
PyPyならばO(10**7)、RubyならばO(10**6)以内に収まるようにアルゴリズムを考える力がつきました。特に遅い言語だと計算量を見誤るとすぐにTLEが飛んでくるので気をつけなければいけません。私の場合、いわゆる嘘解法で無理やり通すことは初めからやろうとは思いませんでした。C++だとN=1000でもO(N**3)でACできることを聞いたことがあるような、、、
よくあるパターンでは、N<=10**5であれば線形シュミュレーションO(N)やソート込みの貪欲O(NlogN)が想定解、逆にN<=18あたりだとbit全探索や半分全列挙のような指数時間のアルゴリズムが想定解、といったところです。数問を除いて茶色以降の問題は、最大ケースで計算量を余らせることはなかったので、制約からアルゴリズムを逆読みできると思います。（予想が裏切られることはほとんどなかった！）
2, 入力の活用
入力の書き方がグラフ問題の入力に似ていたら、とりあえず隣接リストを用意して辺を張ってみようかな？と思えるようになりました。
6, 環境構築
当初はテストコードやAtomというエディターを使っていましたが、拡張機能の充実さなどから現在はVScodeを使っています。特にPythonはRubyと比べてコードが長いのでスニペットの登録にも力を入れました。また、入力やリストの生成・ソートなどはあらかじめ関数化して、その都度調べることのないようにしました。
7, 今後の抱負
これからも一つ先の色で要求されるような難解なアルゴリズムもどんどん勉強していきます。これまでを振り返っても、解ける問題の幅が広がったのはグラフに関する問題に対応できるようになってから、そしてDPとは何かを理解できるようになってからだと思います。だから、最初は難しく思える分野に勇気を出して足を踏み入れることが飛躍のきっかけになったといえます。次は、形式的冪級数とか高速フーリエ変換とか多項式のジャンルを身につけていきたい！！！
特にグラフとDPは問題の幅が広く、勉強することがたくさんあるので頑張ります！(≧◡≦)
また、茶・緑・水を埋めるため、最低１日３題はこれらの難易度の問題を解くことを絶対条件にして、コンテストはABCのみ出るつもりです。（ARCに対応する力がついていないのであまり学習効果が得られないかと、、、）まだまだ下級者ですが、今は精進あるのみ！
【重要】今後の方針
— slyly1373の進捗日記 (@slyly1373_2) 2021年1月11日
・茶、緑、水diffを全埋めするまではABCのみ出る。
（これでレートが下がるようなら仕方がない）
・現時点で残り300問なので1日3問は最低限解くと最高でも100日で終わる。
ここまで読んで下さって、ありがとうございました！！！
