はじめに
こんにちは。灘中学１年生(執筆時点)の〇〇です！AtCoder(ID:T__T)という競技プログラミングサイトで緑になったので入茶・入緑に最低限必要なことをまとめてみようと思います。つよつよな人たちよりも、入茶・入緑までの苦労ポイントだけは知っていると思っているので、そこがこの記事の強みです。書くのは初めてですが読んでいただけると幸いです。
自己紹介
ーーーーーーーーーーーー
僕のAtCoderの歩み。灰色・茶色の人に伝えたい精進の大切さとその方法
精進レート
僕は現在AtCoderでレートが902となっています。
このグラフを見ればわかると思いますが、最初の頃は、全然レートが上がってませんね。最初の頃はずっと１完とかでした。ですが、あるタイミングでいきなり上がり始めました。さて、なぜいきなり上がったのでしょうか。その訳は次のグラフにあらわれています。
これはレートのグラフに精進グラフと呼ばれるものを重ねたものです。精進グラフというのは（解いた問題の点数の和÷100）で表されるものです。これを見ると精進とレートというのは強い相関関係があるということがわかると思います。灰色や茶色でレートが停滞している人はまず、自分がどれくらいの精進をしているかということを見てみて欲しいです。このグラフはhttps://atcoder-scores.herokuapp.com/graphから見ることができます。本当に、、精進は大切です、、精進は(少なくとも入緑とかまでは)きっと裏切りません！
Diffculty
また、自分がどのような問題を精進しているかにも目を向けて欲しいです。
これはDifficulty Piesと呼ばれるものです。AtCoder Problemsで見ることができます。ちなみにAtCoder ProblemsはAtCoderを楽しむには必須サイトなので、知らない方はチェックしてみてください。difficultyはその問題の難易度を表すもので、diffなどと言われます。レートxの人の50%が解ける問題のdifficultyがxになっています。ですから、レートと同じように緑diffなどと言ったりします。このように、僕は、あまり無闇に難しいor簡単な問題を解くということをしていません。一概には言えませんが、自分の色より２色以上高いdiffの問題や、あまりに簡単すぎる問題を解くのはレートを上げるためにはあまりいい手段とは言えないと思います。自分のレートと同じくらいから少し高めのdiffの問題を解くことで一番効率良く実力がつくと思います。自分にあった問題はどのような問題か、diffという視点から考えてみるといいかもしれません。
入茶するために最低限必要なこと
コンテストにて
一概には言えませんが一般的なABCコンテストにおいて、３完(A問題、B問題、C問題)を安定してそれなりに早いスピードで解くことができると入茶することができると思います。ARCコンテストは、基本的にはA問題が解ければ入茶には十分だと思います。早解きというのは意外に重要で、解くスピードでパフォーマンス(各コンテストでの成績がこのレートのレベルということを表す)が800近く変わるなんてこともザラです。順位表観戦などで時間を潰してしまわないようにしましょう。diffは灰diff、簡単めの茶diffが解けるようになると入茶の可能性はグンと高まるでしょう。
どんな問題を解けば良いか
A問題が解けない人
まずA問題が解けない人は、そもそもの言語に対する理解が浅すぎる可能性があります。言語をしっかり学んだ上で、問題文に書いてあることをしっかり実装できるように練習しましょう。
B問題が解けない人(diffが50~200程度の問題)
B問題が解けない人は、競プロの問題に慣れられていない可能性が高いです。先ほど紹介したAtCoder ProblemsのTrainingのEasyを解くことで競プロの問題にある程度慣れ親しめると思います。
C問題が解けない人(diffが300~600程度の問題)
C問題が解けない人は、愚直に実装はできるものの、少し考えなければいけない問題や、アルゴリズム、典型問題などが解けない可能性が高いです。
先ほどのTrainingのEasyに加えてMediumにもチャレンジしてみるといいでしょう。
入茶に必要なアルゴリズム・考え方
1.累積和
まず最低限考え方を身につけて欲しいのが累積和です。累積和は簡単にいうと配列上の要素の和を速く求められるアルゴリズムです。どういうものかは、けんちょんさんの記事累積和を何も考えずに書けるようにする！ #AtCoder - Qiita に詳しいと思います。身につけてない方は是非読んでみてください。
2.計算量
(時間)計算量というのは、そのプログラミングの実行速度がどれくらいになるかを大まかに見積もることのできるものです。計算量を身につけると、その問題が問題文に書いてあるとおり実装すればいいのか、それとも工夫しなければいけないのかが大まかに見積もることができるようになります。C問題などになると愚直に解くだけでなく、計算量を考慮しないといけない問題も多くあります。詳しくはこれまたけんちょんさんの記事計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 #新人プログラマ応援 - Qiitaを是非読んでみてください。
入茶するためにはあまり特殊なアルゴリズムなどは必要ありません。それよりも、競プロに慣れることができるまで問題を解いてみましょう！
入緑するために最低限必要なこと
コンテストにて
一概には言えませんが一般的なABCコンテストにおいて、4完(A問題、B問題、C問題、D問題)を安定してそれなりに早いスピードで解くことができると入緑することができると思います。ARCコンテストは、基本的にはA問題,B問題が解ければ入緑には十分だと思います。緑下位diffが安定して解けるようになることと、灰・茶diffをいかにハイスピードで解くかということが重要になってきます。
どんな問題を解けば良いか
基本的には茶diff、それが解けるようになってきたら緑diffを解くという流れでいいと思います。綺麗に解けなかった問題は、解説を見て、綺麗に解く方法を知ることも多いにプラスになると思います。精進する問題がわからなければ、AtCoder ProblemsのTrainingのMedium、Hardを解けばいいと思います。ちなみにHardは僕は90問ぐらいしか埋められていません()(埋めろ矢)。
入緑に必要なアルゴリズム・考え方
1.累積和・いもす法
茶色コーダーの方なら累積和は使えると思いますが、いもす法は履修できてなかったり、本番で使えないという人が多いのではないでしょうか？ですが入緑するためには是非身につけて欲しいアルゴリズムです。これは名前の元にもなっているいもす法 - いもす研 (imos laboratory)を是非ご覧ください。
2.DFS BFSなど...(グラフ)
僕もとても苦手ではあるのですが、入緑するためにはグラフ問題が解けなくてはいけません。(悲しい)まず最低限、DFS,BFSは身につけましょう。これまたけんちょんさんの記事
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 #AtCoder - Qiita
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 #AtCoder - Qiita
を読んでみると良いと思います。また、ワーシャルフロイド法をはじめとした、他のグラフ探索アルゴリズムに関しても、問題に出てくるたびで良いので学習していきましょう！僕もグラフについてはまだまだ知らないことだらけなので学んでいきたいです。
3.二分探索
二分探索も使えるようになっておくと良いと思います。二分探索はO(log N)で指定した値を見つけることができます。C++のSTLでvectorで二分探索を行う場合 index(何番目か)を求めるにはbeginを引きます。また、イテレーターの値が欲しい場合は*(イテレーター)をやると良い感じに値が得られます。僕も詳しい中身などは知らないのですが、良い感じの記事を見つけられていないので、見つけられたら追記します。
4.bit全探索
bit全探索は緑diff以降では特に良く使うアルゴリズムです。簡単にいうと000...0~111...1の2桁数個の数列を生成できるアルゴリズムです。計算量は基本 O(N*2N)です。例えばNコの箱があってそこにボールを 入れるor入れない を全通り調べよう！などという時に使えます。これはAPG4bをみるとわかると思いますAC - 3.05.ビット演算この記事の中でbit全探索について述べているので、履修してない人は読んでみてください。
5.DP=動的計画法(簡単なもの)
DPは難しいやつはことごとく難しいです、、ですがDPの考え方自体はシンプルなもので、１次元DPと呼ばれるものはDPのDと言われることもあるD問題でよく出ます。要は前の結果を利用して次の結果を求めるということです(雑) 。詳しくはまたまたまたけんちょんさんの典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ #機械学習 - Qiitaなどを読んでみると良いと思います。
6.MOD(modinv modpowなど)
競プロではよく109+7などでMODを取る問題が出てきます。MODの足し算やただの掛け算ならば良いのですが、割り算や何乗もするのは少しややこしいです。正直考えてどうこうなるものでもない気もします(一部の天才は除くのかもしれない)。ですから、MODについてしっかり学習しておくことは大切になるでしょう。そこでまたまたけんちょんさんが神記事を書いてくれているので是非チェックしてみてください。
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 #競技プログラミング - Qiita
7.その他
ここに書ききれてないアルゴリズムもたくさんあります。(例えばしゃくとり法など)ただし、アルゴリズムの数は膨大なので、問題を解くたびに新しい知識を吸収していくことも大切になると思います。何が言いたいかというと、精進大事。 また、競プロでは数学というものの影響も大きいと思います。例えばmodinvを求めるのには何だかよくわからない数学を使います。また、場合の数や確率の問題でも数学が必須となるでしょう。特に何をやれということはないかもしれないですが、数学も適度に精進しましょう。僕も頑張ります。
さいごに
感謝
まず、けんちょんさんをはじめとした神サイトをあげてくださってる方々、色々教えてくれた、Twitterの皆さん、先輩方、同期の皆さんに感謝を申しあげます。皆さんなしでは緑コーダーになんてなれなかったと思います。やっぱり"人"って大事だと痛感した半年間でした。茶色になるまで、緑になるまで色々な困難はありましたが、これからも頑張っていきたいと思います。
目標
目標は高くと言います。僕も目標は高く設定しようと思います。
・2020年度(3月まで)に入水！
・2021年中に暖色コーダー！
・JOI本戦！
これを達成できるように沢山精進します！←怪しい
