【色変記事】初心者がC++で緑色になるまで

2021/12/19日のABC232で入茶、2022/1/22日のARC133で入緑することができましたのでその報告の記事です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/b1bb09b2-4a43-1405-2371-386149826fb9.png)

# 私について

Twitterでは少し日記を書いたりしていましたが、Qiitaの方で投稿するのは初めてなので、まずは簡単な自己紹介から始めさせていただきます。

[twitterのアカウント](https://twitter.com/vi_24E) [AtCoderのアカウント](https://atcoder.jp/users/Yutchy591)

2021/11/14からAtCoderで競技プログラミングを始めた今だプログラミング歴3ヶ月弱の新参者の学生です。始めたきっかけは同級生(以下K)に競プロを始めないかという誘いを受けたことで、環境構築には大きく彼の助けをもらいました。始めからライバルがいる環境だったので（残念ながら最近引退してしまったのですが）、レーティングへの意識が強く、レートを伸ばすことを中心として精進を行ってきていました。

おそらくみなさんの方が経験豊富で私の記事からプログラミングの知識として得られることはほとんどないと思いますが、初心者が一から初めてこのように勉強するとこういう成長をするという、成長日記を読んでいる感覚でこの記事を読んでいただけると幸いです。

##始める前のスペック
プログラミングを始める前に知っていた知識、また私の得意なことと苦手なことを簡単に紹介します。

#### 知っていたこと/やっていたこと

- Scratchで簡単なゲーム作成[^1] 
- 数学、特に計算量(ランダウの記号)
- ちょっとしたアルゴリズム（二分探索とソートアルゴリズム）
- ある程度のタイピング力（5-6key/秒程度）
- 英語の記事が少し読める程度の英語力(英検準一級)

####得意なこと/苦手なこと
- 得意：
    - 直線的な考察
    - 数学的な考察
    - （IQテストの、図形問題とか数列の問題などの系統が得意）
- 苦手：
    - 平行思考
    - 問題文を正しく読むこと
    - (IQテストの言葉を使う系統の問題が苦手)

簡単なアルゴリズムを知っていると言っても、始めた当初は具体的なコードについては何も知らず、それこそ%が何を表しているかわからないレベルでした。しかしながら、最初から計算量の概念のために必要なランダウの記号を理解していたのは大いに役に立ったように感じます。

##現在の状況
C++をメインで、たまにdcでコードゴルフをしています。入緑してからはAtCoder Libraryも使っています。

エディタはVScodeで、それを4,5年前の型落ちのMacで動かしています。

一日あたりの勉強時間は平日は平均30分（やらない日もある）、休日は平均2時間程度です。
まだ得意な分野ははっきりとは分かりませんが、dp、BFSあたりの問題が少し上のdiffでも解けることがあるので、自覚はないですがこの辺が得意なようです。

#今までの振り返り
ここから1週間づつくらいに分けて振り返りをしていきたいと思います。

##〜1日目：言語選択

競プロを始めるとなって最初に悩んだのが言語選択です。

私がKに勧められたのはpythonとC++で、pythonは比較的簡単だけどデバッグが難しい、C++は比較的難しいけどデバッグが容易という風に伝えられました。

結局、難しい方から学べば簡単な方も学べるだろうという安易な考えでC++を選びましたが、ついこの間pythonを少しいじってみた感じ、C++の方が私に向いていたように感じます。[^3]

私があまりフォルダなども操作したことがないような、インターネットでしかパソコンを使わないタイプの人だったので、環境構築はほぼKに頼りきりでした。彼がいなかったらおそらく競プロを始めることもなかったので、本当に感謝です。

そして無事界隈に入ることに成功しました。

https://twitter.com/vi_24E/status/1459913325815349254


##1日目〜8日目：初めてのコンテストまで

最初の数日が一番モチベーションが高くなるのは自明なので、最初の3日でC++に最低限必要な知識を詰め込みました。その時心がけたのは、google docs[^2]にノートをとって一度やったことはすぐに参照できるようにしたことです。下のリンクのAPG4bがかなりのブーストになりました。
[APG4b](https://atcoder.jp/contests/apg4b) 
[3日目に解いた問題(灰中位diff)](https://atcoder.jp/contests/abc226/submissions/27294402)

ここからしばらくはやはり経験が足りなくて、バグにずっと悩まされ続けました。というのも、その時にはまだイテレータやオブジェクト指向がよくわかっていなくて、様々な文法エラーを犯していました。

その後、数日は灰色〜茶色中位の問題を解き続け、ある程度競プロになれはじめました。

そして最初のコンテスト、なぜかARCから始めましたが、無事2完できてまさかの緑perf!
偶然直前に解いた問題がA問題の類題で、B問題が簡単という完全に運に頼りきりでしたが、好スタートを切れました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/db3d9ed4-8dea-e73f-3da7-587b1ce290d0.png)

##9日目〜15日目:アルゴリズムの入り口

まだプログラミングについての大切な要素が何かもわからない手探り状態だったため、いろいろと手探り状態、手当たり次第に[ABS](https://atcoder.jp/contests/abs)、[EDPC](https://atcoder.jp/contests/dp)、[アルゴ式](https://algo-method.com/)などを手当たり次第解いてみて、結果全探索やdpがどのようなものかという理解をすることができるようになりました。

それから挑んだ初めてのABC、結果は初心者にしてはいいにしろ微妙で、原因はd問題が解けなかったこと。この時の[d問題](https://atcoder.jp/contests/abc229/tasks/abc229_d)が尺取り法のチュートリアルのような問題でしたので、そこからより発展的なアルゴリズムも学んでいくモチベーションになりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/f4f21ce8-fff5-d2fa-0e31-e9462ef8c03b.png)

ということで、最初に学んだアルゴリズムらしいアルゴリズムは尺取り法という、なんとも珍しいケースではないでしょうか。

https://twitter.com/vi_24E/status/1464650565867032579

##16日目〜24日目:dpとグラフ

何やらネットサーフしていると、dpがかなり重要になるようなので、とりあえずナップサックdpくらいまでのdpを習得しました。その後ABCの過去問を見ているとどうやらグラフを知らないとお話にならないようなので、基礎知識の全くないグラフを学び始めました。

当時は学ぶべきことが多すぎて何から手をつけるかかなり悩んでいましたが、結果として多くのアルゴリズムの基礎になっているdpを学ぶことは良かったのですが、その後しばらくDFS, BFSがわからない状態で解ける問題が制限されてたので、そこは早めにやるべきだったと後悔しています。

完全に余談ですが、脳内でdp, BFS, DFSが御三家的イメージがあったりします笑

##25日目〜35日目:初めてのデータ構造、そして入茶へ

（当時はアルゴリズムとデータ構造の区別があまりできていなかったけど、）計算量への意識が高まりSTLにある様々なコンテナの習得に学ぶポイントがシフトしました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/ca61b603-7106-2864-b9c9-949f07ff642e.png)

のコンテストで閉路グラフの検出ができなかったり、連想配列が必要になったりして、STLのmapを学んだことを皮切りに、set, priority_queueなどを学び、そのほかUnionFindを学んだりしました。

またUnionFindでグラフが出てきたのでDFS, BFSも学び、結果として次のコンテストで入茶できました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/ec31aa66-eacf-21c6-ca67-8821c4198a86.png)
ちなみにdcを始めたのもこの辺りで、今ではFizzBuzzくらいならできる程度まで成長しました笑

##36日目〜42日目:停滞からの躍進
リアルが忙しく、またDFS, BFSがなかなか実装できず、1週間ほど進捗が停滞していました。

しかしながら、週末のコンテストではかなり成績が良く、なんとARC132では水perfを取ることができました。そのおかげで一気に入緑が視野に入りました。

おそらく精進していなくとも、頭の中にあるアルゴリズムが整理されて、うまいこと本番で力を発揮できたのだと思います。ここから目標はABCでの安定4完になります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/ebcef8b7-576e-1a56-50cc-918354ca78bb.png)

##43日目〜51日目:安定4完に向けての精進
冬休みに入り、時間が確保できるようになったので、本格的に精進をしました。具体的には最近のABCからバチャでA-Dの4問を制限時間100分以内に解くという方法でしていました。

ちなみに結果は、

- 12/28: 
    - ABC225 ○
- 12/29:
    - ABC224 ○
    - ABC223 ●
- 12/30:
    - ABC222 ●
- 12/31:
    - ABC221 ○
- 1/2:
    - ABC220 ○
- 1/4:
    - ABC219 ○

ここでは書いていませんが、解くのに必要な時間も短くなっていき、かなり安定しました。すぐに解消できないバグや、文法ミスが大幅に減ったのもこの時からです。

##52日目〜62日目:基礎知識の完成
この辺りではあまりこれといった進捗はありませんでしたが、最低限知っておくべきアルゴリズムを習得できたので、様々なアルゴリズムの記事を読むことができるようになりました。そのため学びたいアルゴリズムが爆発的に増えたのがこの時期です。

https://twitter.com/vi_24E/status/1480941438691332099

この辺りの時期からコンテストで安定してperf1000を超えるようになりました。

##63日目〜69日目：入緑へ
リアルが忙しく、またあまり精進することはできませんでしたが、
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/45afd8d3-562c-db02-df8f-a7c9b94fe431.png)
無事入緑することができました！

##70日目〜現在:多様なアルゴリズム
現在は入水を目指してアルゴリズムの習得を続けています。新しく学んだアルゴリズムが練度が低く、まだ実用できるレベルではないので、今はそれらの復習が課題です。

最近では、ABCを早めに4完して水perfも出せるようになり、レートも1000を超えました。そのため、次は5完を5割程度で取れるようになればいいなと思っています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354884/ed7b2208-4e2c-cf3d-f55e-b02ad3879f36.png)

---

かなり冗長になってしまいましたが、ここまで読んでいただきありがとうございます。

初めてこのような記事を書いたので読みにくい点も多々あると思います。もし中身に何かしらの不備等がありましたら、コメントの方でご指摘よろしくお願いします。

これからも入水目指して頑張りますので、応援していただけると幸いです。


[^1]: 三角関数もわからない時に作ったものなので、なかなかにひどいものですが（苦笑）
[^2]: もしかしたらいつの日か内容を公開するかもしれないです。
[^3]: 型の有無が大きいです。