【AtCoder】Pythonで入緑しました！！

お久しぶりです！totosukiです。
ついに[ABC326](https://atcoder.jp/contests/abc326)にて入緑をしまして、入茶した時と同様に記事を投稿します！

![01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2091649/cbe5e81f-7350-86a9-1753-79aa831167ba.png)




## はじめに


### 自己紹介
プログラミングと音ゲーが好きな高校３年生です。
競プロ・機械学習・サイト制作を良いバランス（？）でやって、日々を過ごしてます。
最近は、Arcaeaという音ゲーで[良いスコア](https://twitter.com/totosuki_/status/1716768899147157612)を出して喜んでました。



### この記事のテーマ
この記事は、入茶後から入緑するまでの間に何をしたかに焦点を当てています！
もし入茶するまでの過程に興味があれば、私が以前に書いた記事を読んでみてください！！

https://qiita.com/Totosuki/items/d71012254af0977b5298





## 入緑するまでにしたこと
入茶記事の宣伝はここまでにして、早速入緑するまでにしたことをまとめていきます！
入緑（にゅうりょく？）するまでにしたことは以下の通りです。

- ABCのC問題を解く
- ABCのD問題を解く
- Virtual Contestに参加する
- 「競技プログラミングの鉄則」を読む





### ABCのC問題を解く
入茶してから１ヶ月間程度ABCのC問題をメインで解いていました。
C問題を解くことで自分が得られたと感じたものは以下の３つです！！

- 実装方針がまとまるのが速くなった。
- 計算量を意識した解法を考えられるようになった。
- バグが起きたときの原因特定の速度が上がった。

「実装方針をまとめるのが速くなった」ことが一番嬉しいです！
A問題B問題では実装方針を決めてから書くことが少なかったですが、
C問題では、しっかり考えてから解く必要がある場合が多く、段々と身についてきました！

また、A問題B問題に比べて難しいのでバグが多く発生します。
その過程でデバッグ力が向上し、本番でもWAを素早く直してACすることが増えてきました！







### ABCのD問題を解く
C問題までの早解きでも緑に到達することは可能だと思いますが、
将来的には水色になりたいので、D問題も少しですが解きました！

D問題を解いていく中で、私は以下の２つのことを得られました。

- 基本的なアルゴリズムの理解
- 他の人の提出コードを理解する力

競プロの上達において最も不可欠なものだと思うのが、基本的なアルゴリズムの理解です。
本番でも過去問でも、アルゴリズムを学んでいなくて手も足も出ない問題が沢山ありました。
なので、最近は入茶時よりこの部分に多くの時間を費やしています！これからも頑張るぞ〜

また、D問題だと解法を理解するために他の人の提出コードを読むことが多くあり、「他の人の提出コードを理解する力」も付いてきたと思います！
他の人のコードを読むと、便利なライブラリや技術を知るきっかけが増えるので今後も積極的に読んでいきたいです。






### Virtual Contestに参加する
まず初めに、Virtual Contestは[AtCoder ProblemsのVirtual Contest](https://kenkoooo.com/atcoder/#/contest/recent)を指しています！

Virtual Contestについて少し説明させてください。
Virtual Contestでは常に様々なコンテストが開かれていて、その中から気になったコンテストに参加することが出来ます！

![02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2091649/bff3b62a-ae0e-1780-7b7a-6bc6e9fc45b9.png)
また、ABCの様なコンテスト形式とは違い、長期間で沢山の問題を解くTraingモードなどもあります！

私は、様々なコンテストの中から「[ABCなにか](https://twitter.com/abc_nanica)」という定期的に開催されているコンテストに頻繁に参加していました。
このコンテストは21時から開催されていることや、35分間のコンテストと短い時間なので、気軽に参加することが出来ました。

Virtual Contestに参加すると、「時間内に解く」というプレッシャーが掛かり、
問題への深い理解が得られるため、一つの問題で得られる学習量？がとても多い気がします！

また、Virtual Contestだけに限りませんが、振り返りに多くの時間を使いました。
私はSNS上や友人と振り返ったりしています。友人と振り返るの楽しいのでおすすめです！







### 「競技プログラミングの鉄則」を読む
「[競技プログラミングの鉄則（鉄則本）](https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E9%89%84%E5%89%87-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8A%9B%E3%81%A8%E6%80%9D%E8%80%83%E5%8A%9B%E3%82%92%E9%AB%98%E3%82%81%E3%82%8B77%E3%81%AE%E6%8A%80%E8%A1%93-Compass-Books%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%B1%B3%E7%94%B0/dp/483997750X)」とはE869120さんが執筆された本です。
この本は、本書中に出る解答のソースコードが[GitHubに公開](https://github.com/E869120/kyopro-tessoku)されており、Pythonの解答例も見れるのでおすすめです！

私はこの本を[入茶前に購入](https://twitter.com/totosuki_/status/1674777276846841857)しまして、入茶後に本格的に読み進めていきました！
この本で学習すると、とても効率的に基礎的なアルゴリズムの理解が出来ると思います。

現在は、鉄則本を使ってアルゴリズムの理解をすることに焦点を当てて頑張っています！
後、競プロの上達ルートを綺麗に進んでる感じがします！！良いですよ〜





## 学習したアルゴリズム
入茶記事でも、「アルゴリズムを身につけないと実践で使えない」と書きました。
本当にその通りで、私は茶色の間アルゴリズムを身につける方に特に力を入れていました。
なので、実は緑になったからと言って難しいアルゴリズムが増えたわけでもないんです。

ですが！！どのようなアルゴリズムやデータ構造等を覚えてきたか紹介させてください！
***
まずは入茶時までに覚えてたアルゴリズムやデータ構造を列挙します！
（すごくとてもめっちゃ入茶記事に似てます）

- 全探索
　B問題を埋めるのが最適だと思います！！
- set型
　C問題だとset型を使用する問題がとても多いと思います。
　また、A問題B問題でも使うと楽に解ける問題がよくありますよ！
- 累積和
　[けんちょんさんの記事](https://qiita.com/drken/items/56a6b68edef8fc605821)や鉄則本で学習するのがおすすめです！
- いもす法
　累積和を覚えたら、考え方が似ている[いもす法](https://imoz.jp/algorithms/imos_method.html)も理解がし易いと思います。
- 動的計画法（DP）
　入茶記事では理解までしたとか言ってますが、全然無理です。奥が深すぎます。
- deque（デック）
　listのpopの処理を、$O(1)$でできてしまうデータ構造です。
　[nkmkさんのサイト](https://note.nkmk.me/python-collections-deque/)がとても分かりやすく書いてあるのでおすすめです！
- 幅優先探索（BFS）
　グラフ問題を一つは解いてみたいという思いから学習しました。
　現在は、しっかり身についていて実際のコンテストでも使ったりしています！
- Union-Find
　入茶した頃はライブラリを作るなど、力を入れて学習していました。
　ですが、BFSや後ほど紹介するDFSなどでも解けるのであまり使ってません...
- 整数問題系のアルゴリズム
　様々な記事を参考にしながらアルゴリズムの学習をしました。
　ですが最近は、ライブラリを使用して整数問題系を解いています！
***
次に、入茶〜入緑の間に覚えたアルゴリズムやデータ構造を列挙します！

- 二分探索
　二分探索の問題に出会うことが多々あったので、鉄則本で学習しました。
　コンテスト中に簡単な二分探索の問題をAC出来る位には身につきました！
- 尺取り法
　これも鉄則本で学習しました。[けんちょんさんの記事](https://qiita.com/drken/items/ecd1a472d3a0e7db8dce)もおすすめです！
　二分探索と尺取り法の両方が使える問題は、いつも尺取り法を選んで解いてます！
- defaultdict
　存在しないキーを参照してもエラーが起きない辞書型と思うと良いかもしれません。
　わりと使う機会が多くて、覚えておいて絶対に損は無いです！！
- 深さ優先探索（DFS）
　出来るだけBFSで解いてしまっているので、苦手なアルゴリズムです...
　鉄則本を読んで学習はしましたが、もっと練習が必要ですね。
- 優先度付きキュー
　最小値や最大値を$O(\log{N})$で取り出せるデータ構造です。
　Pythonでは、`heapq`という標準ライブラリに用意されています！
- 動的計画法（DP）
　一次元の簡単なDPは出来るのですが、多次元になると全く解けません...
　鉄則本や[EDPC](https://atcoder.jp/contests/dp)などで練習をして、段々と実践で解けるようになりたいです！
***
競プロ始めた当初、私は「沢山のアルゴリズムを学ぶことが上達の鍵だ」と考えてました。
しかし、緑に到達するにはそこまで多くのアルゴリズムを学ぶ必要はないと思います。
体感ですが、ABCのD問題までに上記のアルゴリズム以外が必要な問題は少ないからです。

私自身も、新しくアルゴリズムを学ぶのを辞めて、今まで学んで来たアルゴリズムを使用する問題を積極的に解いて、身につけることを優先しようと思います！
やっぱり、身につけて実践で使えるようになることが重要ですからね！！

また、「〇〇というアルゴリズムの問題を解きたい！！けどどうやって探すんだ...」という方は、[AtCoder Tags](やっぱり、身につけて実践で使えるようになることが重要ですからね！！)という、AtCoderの問題を種類別に分類してくれているサイトを使うと、探しやすいと思います！



## AtCoder Problems

入緑時のAC数やProgress Chartsを紹介します！
受験期なこともあり、夏休み以降は停滞気味です...（言い訳）

![03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2091649/585e54de-2cf9-43e3-819b-ca35a0b75684.png)
![04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2091649/eba2ccaa-915a-d811-08f9-a5ea3c867a0d.png)
![05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2091649/cdaabbe1-ef21-bbdf-dc32-0802a3520717.png)
![06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2091649/b7fff9ab-1793-8f89-200d-ab837da0b169.png)

やっぱりD問題の解く量を増やすべきですね...
受験が終わったら、鉄則本完読・C問題200問AC・D問題100問AC目標で頑張りたいです！
また、E問題も少しずつ解いていきたいと思います！！




## まとめ
- [入茶記事](https://qiita.com/Totosuki/items/d71012254af0977b5298)も書いてるよ！
- C問題では「実装方針の整理」「計算量の意識」「バグ取り」が上手くなる！
- D問題では競プロで必要不可欠な「基本的なアルゴリズムの理解」が出来る！
- [Virtual Contest](https://kenkoooo.com/atcoder/#/contest/recent)に参加してみよう。参加したら振り返りもしようね！
- 効率良くアルゴリズム力を上げたい人は「[鉄則本](https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E9%89%84%E5%89%87-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8A%9B%E3%81%A8%E6%80%9D%E8%80%83%E5%8A%9B%E3%82%92%E9%AB%98%E3%82%81%E3%82%8B77%E3%81%AE%E6%8A%80%E8%A1%93-Compass-Books%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%B1%B3%E7%94%B0/dp/483997750X)」を読むのがおすすめ！
- 基礎的なアルゴリズム・データ構造をちゃんと使えるようにしよう！


## 終わりに
入緑をすることが出来て、とてもとてもとても嬉しいです！！！
水色になるには、一年以上かかるかもしれませんがのんびり頑張りたいです。
また、入水記事も書こうと考えているので、その際は是非是非読んでみてください。
拙い文章ではありますが、少しでも役に立てたなら幸いです！それではまた！！