okumuraです。前のコンテストでAtCoder青になったのでそれを記念して初投稿いたします。(すぐに水色に落ちそうなので怖いんですが)
そのほかの人も結構こういう記事が多いので、今回は個人的にやったこと半分とPythonで気をつけること半分で話したいと思います。
#1 AtCoderやり始めたとき
AtCoderをやるまでプログラミングはif,for,while文ちょっと知っているぐらいでした。とりあえず、問題解いたらPythonの他の文法とか覚えるだろーと思ってやり始めました。
Pythonを選んだ理由は友人がやってたのと、文法が楽だったからです。
AtCoderに登録したら、まず
・AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
をやってどんな感じかを学びました。Pythonだと文法で困るということは少ないのでいきなりこの問題し始めても大丈夫だと思います。
そのとき少々困るのが入力形式なんですが、これはもう覚えるしかないので
・Pythonで使う競技プログラミング用チートシート
・Pythonで競プロやるときによく書くコードをまとめてみた
・[Note] 競プロ / Python 3
を見て覚えましょう。
#2 水色になるまで
普通だったら段階を挟むべきなんですが、私は水色になるまでやることがあんまり変わってなかったです。
やったことは主に３つです。
#2-1 蟻本を解いていく
プログラミングコンテストチャレンジブック(通称 蟻本)を購入し、読んでました。
ただ読むだけだと全く実装できないのでけんちょんさんの問題集
・AtCoder 版！蟻本 (初級編)
・[AtCoder 版！蟻本 (中級編)]
(https://qiita.com/drken/items/2f56925972c1d34e05d8)
をひたすら解いていきました。
この問題集は激ヤバに難しい問題も多々あるので、ちょくちょく飛ばしてたんですが・・・
他人のコードを参考にしながら、ACもらうまでやってました。
#2-2 コンテストに出る
難しい問題を解くのが好きだったんで水色になる前でもARCばっかり出てました(おそらくレート上げるならABCに出た方がいいのでオススメしません)
コンテストに出て毎回D問題にボコボコにされて復習してという感じです。
コンテスト終わってから復習が大事で、700点以下の問題をACするまでやってました。
解説見てわかることは稀なので、解説動画(AtCoder Live)や他人のコードをみてACを取るまでやってました。
解説動画は非常にわかりやすいんでめっちゃオススメです。
#2-3 D埋めをする
ARC-D問題とABC-D問題を埋めていきます。（実は私はまだ終わってません・・・）
D問題は難しく面白い問題が多いので、D埋めはオススメです。D埋めをすると自然とC問題も気になって解くので、結果C埋めにもつながります。
そのとき使ってたのがAtCoder Problemsで解いた問題とか見れるのでめっちゃ助かりました。
#3 青色になるまでやったこと
水色になるまでにやったことにプラスして次の二つをやってました
#3-1 強い人をAtCoder Problemsのライバルにする
AtCoder Problemsでライバルを選べるので、強い後輩をライバルにしてました。強い人は難しい問題を解いてるので、その人が解いてる問題をやってました。
#3-2 バチャコンに参加した
学科の後輩が競プロのグループを作ってたので、そのグループに参加し、週１ぐらいでバチャコンに参加してました。
これまた強い人がいるグループだったので、毎週300から700点問題を解くことになり、かなり勉強なりました。
#4 やったことまとめ
振り返ると
・難しい問題でも時間かかってでもACしていく
・難しい問題にチャレンジしていく
ってのがなんか上がった要因のように思います。もちろん早解きする訓練も大事なんですが・・・
あとは今年からCodeforcesもやり始めたのでまだまだやることは多いです。(まだ青色確定ってほどの実力もないので頑張らないとなのですが)
5 Pythonで競プロやるときに気をつけること
ここからはPythonで競プロやるときに気をつけるといいことを言います。
5-1 計算量を覚える
Pythonに限らず、計算量見積もりできないとめちゃキツいです。
計算量見積もりに関してはけんちょんさんの
・計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
・[特集！知らないと損をする計算量の話]
(https://qiita.com/drken/items/18b3b3db5735241465ef)
がためになります。
またPythonでは知らず知らずのうちに計算量食ってることも多々あります。
(A[k:l]というリストのスライシングとかremoveとか)
そういったやつを防ぐためにも
・Pythonistaなら知らないと恥ずかしい計算量のはなし
・TimeComplexity- Python Wiki
は一通り見ておいた方がいいと思います。できれば覚えておいた方がいいかもしれません。
5-2 ライブラリーを覚える
競プロでよく使うライブラリーはけっこう少ないです、なので覚えちゃいましょう。これはもう慣れです。deque使いたいときにはcollectionsから引っ張るとかです。
問題解いていって覚えるしかありません。
#5-3 高速化
これはそこまでシビアになることもないですが、頭の片隅に置いていて損はないです。
リストの初期化で[0]*N使ったら早いとかです。
主に以下のホームページを参考にしました。
[高速化のためのPython Tips]
(http://nonbiri-tereka.hatenablog.com/entry/2016/09/01/072402#PyPy)
Python を高速化したい
#5-4 Pypy3を使う
AtCoderでPython勢が戦えているのもPypy3があるからです。PythonでTLE (Time Limit Exceeded)起きるプログラムもPypy3だと通せることは多々あります（私は最近Pypy3でしか提出してない）
$N=5000$で$O(N^{2})$の解答はPythonだと無理ですがPypy3だといけます。
ただ時たま稀にPypy3でTLEおこったものでもPython3で通るというものもあります。以下のリンクはそのときに参考にしました。
Why is Pypy's deque so slow?
Pypy Performance -String concatenation is expensive-
でも基本Pypy3使っておいて大丈夫です。
#5-5 計算量落とすテクニックを覚える
これもそこまで気にすることはないですが動的計画法でsetを使う(FT Robot 解答例)とか動的計画法で辞書を使う(チーム分け 解答例)とかです。
これも申し訳ないんですが、過去問やって慣れるしかないです。
#5-6 Pythonでも無理な問題がある
PythonでもPypy3でも無理な問題はあります。やっぱりc++の速さには勝てません。
公式解答通りにプログラム書くとTLEを起こす問題はちょいちょいあります。D問題でもTwo Sequencesがそれにあたります。もちろんPypy3解答はあるんですが・・・
まあそこまで心配する必要はないです。（ただ私はちょっと怖くなってc++にも手を出し始めています）
#-1 まとめ
慣れるって書いたところをもう少し具体化した方がいいかもしれませんね・・・
余力があればよく使うライブラリー集とかも出すかもしれません