【AtCoder】プログラミング未経験からのんびり続けて青コーダーになった話

はじめまして、chimakiです。先日のARC167にて念願の青コーダーになれたので、今までやってきたことなどをまとめて書いてみました。


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1888415/9aaf1930-7e6b-5531-1c9b-584bace60be0.png)

# 簡単な自己紹介

- Twitter: [chimaki_yama821](https://twitter.com/chimaki_yama821)
- 数学系の学科に所属している学部4年生
- 競プロ以外はプログラミングをほぼしない
- 使用言語：C++

競プロの存在は高校生の時にTwitterで知りました。「なんかめっちゃすごそうな人たちが難しそうなことツイートしててかっこいい！！」みたいなことを思いながら、大学受験終了後にAtCoderに登録して競プロの世界に飛び込みました。

# 水色になるまでにやったこと

あまり正確ではないかもしれませんが、各種色変のタイミングまででやっていたこと・できるようになったこと・できなかったこと　などを簡単にまとめました。


### 〜茶
競プロやるぞ！と意気込んでいたはいいものの、高校の授業でBasicに触れた程度で何も知らなかったので基本的なところから勉強する必要がありました。やってよかったのはこの辺のはず：
- [APG4b](https://atcoder.jp/contests/APG4b)の1, 2章と3章の一部
- [AtCoder Beginners Selection](https://atcoder.jp/contests/abs)
- [けんちょんさんの記事](https://qiita.com/drken/items/fd4e5e3630d0f5859067)

特に、APG4bについてはとてもわかりやすくてしばらくはこのページを辞書がわりに使いながらコードを書いていました。

<details><summary>できるようになったこと</summary>

- __```if```, ```for```文の記述__
FizzBuzzがさらっと書ける程度には。APG4bの演習問題もやったのが良かったです。
- __配列の扱い__
APG4bに載っていた関係でずっと```vector```を使ってました。
- __計算量の考え方__
APG4b-2.06を参考に、製薬に対してどのような計算量での解法が求められているのか考えられるようになりました。TLEになった時に原因がわかるようになりました。
- __```sort```__
APG4b-1.14では標準ライブラリの関数紹介があるのですが、このうち```sort```が非常に便利でした。```sort```がどのような実装になっているのかは今も知りません。

個人的な感触としては、```sort```と計算量の話のおかげで頑張って考えればABCのCくらいまで解けるようになりました。
</details>

<details><summary>できなかったこと</summary>

競プロに限らず、「難しい本を読めば効率よく勉強できる」「難しい問題を解けば色々吸収できる」~~「難しいことやってる自分かっこいい」~~ と思いながら**背伸びをし過ぎて何も得られず**...ということをよくやってしまいます。ここでは、
- 蟻本を買って読んでみる
- [EDPC](https://atcoder.jp/contests/dp)に挑戦してみる

ということをしていたのですが、あまり身につきませんでした。
</details>

---

### 〜緑
茶色になるまでのコンテストで緑中盤くらいのパフォーマンスが出ていたので、あっさり緑までいけるかな〜と思っていたらなかなか苦戦しました。やったこととしては、
- [AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)で茶・緑の問題を解く
- DPの問題を色々解く
- ABCの過去問を解いて解説放送をみる

という感じでした。

<details><summary>できるようになったこと</summary>

- __簡単目なDFS, BFS__
DFS（というか再帰関数）が苦手だったので集中的に特訓しました。
- __bit全探索（APG4b-3.05）__
- __```set```, ```map```__
これかなり大きくて、ABC-C,Dあたりの問題の勝率が```set```覚えてからとても上がりました。
- __UnionFind__
蟻本で学んで、使いやすいデータ構造だなぁと感じていました。
- __超基本的なdp__
コンテスト中に自力でdpが書けた時はめちゃくちゃ嬉しかったです。
- __combination__
解説放送でsnukeさんが書いていたのをコピペして使ってました。高校数学が行かせて嬉しい。
</details>

<details><summary>できなかったこと</summary>

茶色までの欄に書いたことと基本的には同じです。あとは、グラフ問題に対して全くアプローチできませんでした。Dijkstra法とか、何もわからず。
</details>

---

### 〜水
緑に入ってからしばらくして、少しモチベが下がってしまったのであまり競プロに時間をかけなくなりました（レートのグラフを見ると明らか）。途中で少し復帰したのを除くと約1年ほどは休んでいたと思います。復帰したきっかけは、

- 応用情報の試験勉強からの逃避
- 大学の友人がやっていた蟻本の勉強会への参加

です。やらなきゃいけないことから逃げてやることが一番楽しいのだ。

で、水色になるまでには色々なことをやったのですが、
- グラフアルゴリズム（ダイクストラ、最小全域木　など）の勉強
- bitDPなどの少し難し目のDPの勉強
- [典型90問](https://atcoder.jp/contests/typical90)の一部
- 水diff問題にチャレンジしてじっくり考える
- [E8さんの記事](https://qiita.com/e869120/items/eb50fdaece12be418faa)：特に精選100問

というのがメインかな、と。特に、**水diffの問題をじっくり考えて解く**のが楽しくて、ためになったと思っています。Highestが黄色の友人に問題を出してもらって解いたりしました。典型90問に関しては、難しい問題が多くて挫折......

<details><summary>できるようになったこと</summary>

- __再帰関数などでバグらせずパパッと書ける__
何度も苦しんだ結果、スムーズに書けることが多くなってきました。まだ伸び代はあるけれど。
- __```priority_queue```, ```multiset```などが使えるように__
この辺の便利なコンテナを少し使えるようになってきました。
- __半分全列挙、しゃくとり法、二分探索__
問題に応じて適切な解法を考えることと、その実装をスムーズに行うことができるようになってきました。

この頃にようやく蟻本初級編と中級編の一部を理解できるようになってきました。
</details>

<details><summary>できなかったこと</summary>

- __バグらせずにダイクストラを書く__
なんとなくのノリで書いていたので、無限ループにしてしまったり、正しい解が出てこなくなってしまったりすることが多々ありました。（というか毎回やらかしていた）
- __セグ木の理解とACLの使用__
ACLは環境構築が全くわからずに使えませんでした。自分でセグ木を（蟻本を写して）実装したりもしたのですが、問題を解くのに使えるほどには理解できていませんでした。
- __大量の問題演習__
これはどの時期でも言えることなのですが、適正難易度の問題を解く量が少な過ぎて典型的なテクニックを知らないので苦戦することが多かったです。

</details>

# 青になるまで
### 水〜青までにやったこと
#### 1. 水・青Diffの問題を解く
この期間は今までに比べてたくさんの問題を解きました。水色になった2022/8/27と青色になった2023/10/15での解いた問題数がこの画像のとおりです。
![スクリーンショット 2023-10-26 9.38.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1888415/9b14198d-6aac-14b3-c4aa-b3b621ab0f33.png)
![スクリーンショット 2023-10-26 9.38.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1888415/abc383d2-91d4-8bc1-93ee-a8d95ed4671d.png)
青・水Diffの問題をたくさん解くことを意識していました。約1年で500問ほど解いていて、その中でも特に<font color="Yellow">黄</font>16問・<font color="Blue">青</font>52問・<font color="SkyBlue">水</font>97問で力がついた気がします。<font color="Yellow">黄Diff</font>の問題はほとんどが解説AC、<font color="Blue">青Diff</font>の問題は7割ほど解説AC、<font color="SkyBlue">水Diff</font>の問題は約半分が解説ACでした。解説ACした問題の解き直しなどは基本的にしていません。

また、この頃は<font color="Green">緑Diff</font>の問題は安定して解けるようになってきたのですが、速度が足りないと感じていたため青・水の問題で詰まった時などに取り組むようにしていました。

#### 2. [AtCoder Library(ACL)](https://atcoder.github.io/ac-library/document_ja/index.html) を使えるようになる
全ての機能ではなく、```modint```, ```segtree```, ```dsu```, ```fenwicktree```を使いました。```modint```と```dsu```(UnionFind)は元から自分で用意していたのであまり変わらなかったのですが、```segtree```と```fenwicktree```には非常に助けられました。内部の仕組みについては全く理解せず、使い方だけを覚えました。

個人的に、```fenwicktree```は「```set```を使って```st.find(key) - st.begin()```みたいなことをしたい（これは```set```だとできない）」時に使えるという印象があります。

#### 3. 勉強会・バチャ
「蟻本の輪読をする」ということで始まった自主ゼミで、過去のABCのバチャをやったり典型90問やその類題を互いに解説し合うなどしました。これをやって一番良かったのは**モチベーションを保ち続けることができた**ことで、毎週大学に集まって競プロ関連のことをやることによってその時間だけでなく1人でも問題を解こうという気持ちになりました。

---

### できるようになったこと・まだできないこと
現時点で**そこそこ**使えるようになったアルゴリズム・データ構造は次の通りです：

:::note info
全探索, 二分探索, 動的計画法, ダイクストラ法, ワーシャルフロイド法, クラスカル法, 累積和・imos法, 座標圧縮, 半分全列挙, 行列累乗, modint, combination, UnionFind, SegmentTree, FenwickTree
:::

ダイクストラへの苦手意識があったり、二分探索の問題がうまく思いつけなかったり、bitDPが思いつかなかったり、桁dpでバグらせたり......と課題はまだありますがそれは今後頑張ります。


一方で、現時点で**少し勉強したけど実際に使えるほど理解していない**ことは次のとおりです：

:::note warn
フロー, Grundy数, ダブリング, 強連結成分分解
:::

蟻本の解説を読んだり、問題の解説で知ったりしたのですが、まだ初見の問題に対してこれらを使って解くということができていません。


また、**全くわからないけど今後勉強していきたい**というのは次のとおりです：

:::note alert
LazySegmentTree, Mo's Algorithm, 文字列アルゴリズム（Z-algorithmなど）, Rolling-Hash, 形式的冪級数, 幾何
:::

これらはコンテスト終了後のTwitterなどでよく見るので早めに勉強していきたいです。

# 総括

### とにかく問題を解くのが大事！
振り返ってみて、**大量の問題を解くこと**の大切さを再認識しました。正直、始めた頃は「あまり問題を解かずに高いレートに到達できると地頭良さそうでかっこいいだろ」みたいなことを考えていたりもしましたが、今思うとほんとバカだな〜って感じです。

一番しんどかったのはDP・グラフアルゴリズムなどを新しく勉強した時。まともに使えるようになるまでは余計なことを考えてしまうようになって、勉強する前よりむしろ問題が解けなくなってしまいました。 **「インプットとアウトプットの割合は3:7がいい」** とかよく聞きますが、競プロに関してはそれ以上にアウトプットの割合を高くしていった方がいいように思います。

### 競プロをやって良かった！
競プロのおかげで世界が広がりました。特に良かったのは次の3つです。

1. __プログラミングが好きになった__
　C++の難しい機能や他の言語のことは全然わかりませんが、競プロで「問題から考察して実装できる形で整理して考える」ということを繰り返し行い、たくさんコードを書いたことでプログラミングが好きになり、少しだけ得意になりました。おかげで今年の夏休みは2ヶ月間のインターンにも参加することができました。

 2. __専門の数学のモチベーションに繋がった__
 　自分は（競プロの影響を大きく受けて）**組合せ論**を専門にしているのですが、一見何のために考えているのか分からないようなことでも競プロで活かせるようなものもあったりして楽しいです。まだあまり多くのことは学べていませんが、修士課程も含めて残り2年半続けることで研究も競プロもいい感じにできたらいいな。

3. __人間関係が広がった__
　競プロがきっかけで出会えた人がたくさんいます。その人たちとは、競プロのことはもちろん、それ以外にも例えば各々の専門の話・インターンの話・Kaggleやってみようという話など、ができて楽しいです。今後はTwitterやオンサイトコンテストで大学外の人とも交流を増やしていきたいなぁ。


# 今後に向けて
次は、<font color="Yellow">黄色コーダー</font>を目指して頑張ります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1888415/fe9e3851-da28-c803-3b8b-3d5bbc2df43d.png)

現在のDifficulty Piesはこの画像のとおりで、AC数は **947** です。青diff200問・黄dif100問くらい、AC数2000を目指して精進していこうと考えています。また、AtCoder以外にもCodeforcesやyukicoderに取り組み、とにかく大量の問題に挑戦していくつもりです。


# 最後に
モチベ維持のためにCodeforcesでバチャも積極的にやろうと思ってるので、一緒にやってくれる人が嬉しいです。その時はまたツイートするなどします。

黄色になった報告記事が書けるように頑張ります！！