はじめに
なぜ色変記事を書くか
- 競技プログラミングを勉強する上で、色変記事を読むことがモチベーションを保つ大きな要因の一つだったため。
- ゴリゴリの理系でなくても入緑できることを伝えるため。
- 今後入緑する人の手助けになればいいと思ったため。
自己紹介
- 偏差値40代の理系大学に指定校推薦で入学している上、理系にも関わらず理系科目がとてつもなく苦手です。
- 現在はIT企業でSEをしていますが、前の会社では営業をしていました。
競技プログラミングを始めるまで
SEになるにあたり、プログラミング学習の良い教材はないかと探していて、競技プログラミングを知りました。
競技プログラミングのサイトの中で最も有名そうなサイトであったAtcoderの色（レート）に関する評価を見た際に、
エンジニアとしてもある程度の安心感がある。
と記載があったので、SEに転職したばかりの自分にとってちょうどよい目標だと思いました。
また、
他社アルゴリズム力判定サービスだと、上位１％の最高ランクが付く実力です。
と記載もあったので、上位1%に入れたらかっこいいなーと思ったのもあり、緑色を目指すことにしました。
わけあってPythonを勉強する必要があったのですが、Atcoderで解説記事が多い言語の一つであり都合が良かったので、Pythonでコンテストに参加することにしました。
行ったこと
行ったことは大きく分けて3つです。
過去問
AtcoderPloblemsで自分のレートに近い難易度の問題を探し、ひたすら解きました。
1000問以上解いていますが、プログラミングの基本的な勉強（変数やメソッドの使い方とか）も兼ねて問題を解いていたので、競技プログラミングの勉強だけに絞ると800問ぐらいかと思います。（知らんけど）
後述しますが、本の問題の一部もカウントされているので、実際にはさらに少ないかと思われます。
普通なのかわからないですが、入緑したにもかかわらず、難易度が緑の問題をほとんど解いていません。
一部緑色の問題を解いていますが、昔の問題であるため実質的には茶色の難易度の問題かと思います。
そのため、実際に解いた緑色の難易度の問題は、実際にコンテストで出題された2問だけになります。
余談ですが、他人と比較すると私は問題を早く解くタイプのようでした。そのため、緑色の問題をほとんど解いていないにも関わらず、入緑できたのかと思います。
多く問題を解くタイプか早く問題を解くタイプか確認できるサイト(AtCoder Type Checker)
（少し前に確認したときには、-14ぐらいだったはず・・）
本
2冊読みました。
正直、競技プログラミングの鉄則（鉄則本）だけでいいかと思います。
問題量が多く、カバーしている範囲も広いので、鉄則本と過去問を適当に解いてるだけで緑色に達すると思います。
3700円と比較的高い金額かと思いますが、Atcoderに常設されているジャッジを使用できる点や中身を考えると3700円は安いかと思います。
1.問題解決のための アルゴリズム×数学 が基礎からしっかり身につく本
2.競技プログラミングの鉄則
アルゴ式
動的計画法・BFS・DFSを学びました。
各アルゴリズムを細かい段階を踏んで学べるので、少し応用した問題を解くのが苦手な自分には非常に重宝しました。
知らないアルゴリズムやテクニックに出くわした際に、それらがアルゴ式に存在しているか真っ先に調べることをおすすめします。
入緑
46回参加し、1年半でようやく入緑できました。
結局1度もARCに出ることはなく、ABCのみ参加しました。
伝えたいこと
ちゃんとした理系じゃなくても入緑できるんだよ。ということよりも伝えたい事があります。
それは、UnionFindです。
最高パフォーマンスを出した回と入緑した回の両方がUnionFindを使った問題でした。
UnionFindがなにかについては言及しませんが、緑色未満の方は覚えておくとレートを爆盛できるかと思います。
というのも、問題の難易度の割に、書くコードの量を非常に少なくできる上に早く解くことができます。
以下、最高パフォーマンスを出した回と入緑した回のUnionFindを使用した問題になります。
ABC288 C - Don’t be cycle(ギリギリ茶diff)
問題URL
茶diffの問題にもかかわらず、4分20秒で解くことができ、非常に少ない記述量で解けました。
ABC293 D - Tying Rope(ギリギリ緑diff)
問題URL
緑diffの問題にもかかわらず、20分以内で解くことができました。
最後に
UnionFindを使えなければ、絶対に入緑できなかったと思います。
最近のABCでは、UnionFindを使うと簡単に解ける問題が多く出題されているので、覚えておくといいことがあるかと思います。
入緑する人が一人でも増えれば幸いです。