AtCoderでレート青になるまでにやったこと
AtCoderでレート青になったのでそれっぽいことを書きます。
だいぶサボっていたとはいえ、水色から1年くらいかかってるんですよね。
[1] 目指すべき実力
・青になるためには、5完以上を目指す。水色になるには、4完を目指す。
現在のABCでは、だいたい5問解ければ青パフォは出るようです。
そのために必要なものは、E・Fを解く能力もですがまずはD問題まで確実に解けるようになることです。
私が水色になった時は、まだABCとARCが分かれていて、ABCのD問題は今と比べると少し難しかったように思います。
この頃にD問題が半分以上とけるかな？という実力で水色になりました。
今の基準ではもう少し正答率が高くないと上がれないかもしれません。
[2] 言語の選択
・赤はC++が極端に多いですが、青まではPythonでも問題ありません。
Pythonは確かにC++などと比べて遅いですが、ABCレベルであればPythonだから解けないということはありません。maspyさんを参考にしましょう。
実際に、PythonでTLEが出た後にC++で書き直したら通ったという経験は1~2回ありましたが、乗り換えは行いませんでした。
言語の難しさという点ではC++のほうが遥かにハードです。大きい数は10^9+7でMODをとることが多いですが、中にはlong long intの範囲を超える数を答えとして出力しなければならないケースもあります。
また、計算の途中経過で超える場合などもあり、そこでWAやREが出るのは厳しいです。
また、VectorとPythonのリストや辞書も、扱いやすさがかなり違います。
Pythonから入った人間の意見ではありますが、こうした部分を考えると、初学者であり、競技プログラミング以外でもPythonを使う場面がある、という方であれば、そのままPythonで競技プログラミングに挑戦することをおすすめします。
paizaなどでは、Pythonのほうが実行時間の制限がゆるい場合もあります。
他の言語は、といわれるとやっていないのでわかりません、としか言えないです。
Go言語は流行りの言語という意味では悪くないのですが、基本のライブラリがあまり充実しておらず、maxの計算すら手間がかかるため、試しに採用してみたことはあるものの常用はしませんでした。
[3] 練習方法
・atcoder problemsなどを利用しながら過去問を解く。
atcoder problemsで933AC、その大半がABCとARCの低難易度埋めではありますがそれなりに頑張った気はします。
このときに考えることはいくつかあります。
1. 典型問題で利用する関数、入出力の部分などを作成しておき、ファイルやgithubからいつでも参照できるようにする。
非常に重要です。プライベートリポジトリなので公開できませんが、私は以下のようなアルゴリズムや関数のコードをgithubに登録しています。
・最小公約数、最小公倍数（最近、math.gcdがサポートされたので不要になりました）
・MOD下での逆数
・MOD下での組み合わせ
・Union-Find木
・スライド最小値、スライド最大値
・ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法
・トポロジカルソート
・転倒数
・最小共通祖先
・セグメント木
一度やった問題が確実に解ける、ということは大きな強みになります。頑張って自分の武器を増やしていきましょう。
2. DPを使えるようになる。
typical DP contestなどの問題を通して、典型的なDPを利用する問題を覚えましょう。
D以上の問題は、全探索すると解けないという問題が多く、その際に適切なDPを行って計算量を減らすことが求められます。
といいつつも、DPの漸化式が早く思いつけるようになるための方法は説明できません。ABCの過去問をたくさん解いて、パターンを覚えていったくらいですね。
[4] いまだにできていないこと。
青になってもできないことがあるので青なのです。AGCなどはA問題以外まず解けないです。
面白いもので、AtCoder Problemsで黄色以上のパフォーマンスになっているF問題はほぼ解けていないです。
このあたりの問題は、解説を読んでも解けない場合が多いので、配信動画を見るなり、自分と同じ言語を使っている人のAC解を見るなりして学んでいくしかありません。
話が逸れますが、他の人の解答をみることは非常に重要です。入力部分や、ループなどのコードをもっと効率的に書く手段が見つかります。私もPythonのmapなどを使いこなせているとは言い難いため、他人のコードを見て「この部分はどういう挙動をするのだろう」となることが多々あります。
こういった部分を潰していくことで、より効率的で可読性の高いコードが書けるようになります。
あとは、セグメント木や最小共通祖先を使う木の問題も苦手です。
特にセグメント木は何度解説を読んで実装してもわかってないような気がしています。
この先は「自分の苦手な問題はなにか」を明確にして、それらを潰していくことが重要になりそうです。
[5] 読んだ書籍
蟻本や、アルゴリズムとデータ構造は家にあるのですが読み切ってはいません。紙の本読むの苦手なんですよね。
ただ、色々な話を聞いている限り、ちゃんと読んだほうが良いかとは思います。
たとえば、blogなどで、ABC参加しました。この問題は蟻本にあった～で、というような記事はよく目にします。ABCでまだ出たことはないが、蟻本には書いてあるものは少なからずあると思います。
何したら良いかわからない方はやりましょう。持っていないならABCノックでもいいと思います。
[6] 最後に
・ABCはできるだけ出ましょう。緑や水色に上がり立てて下がるのが怖くても、出てください。
過去問をやったらやっただけ、本戦は出たら出ただけ実力がつくと思います。
本戦と、過去問ノックでは集中力が格段に異なります。本戦で100分間しっかりと頭を使う、ということを超える練習を私は知りません。（実力をつけるだけなら座学は強いですけれど）
それでは良いAtCoderライフを
