【Atcoder】水色になって黄色パフォを取れるようになるまでにやったこと
自分が水色になったのが2019/3/30でそれからしばらく時間は空いてしまったのですが、この前のAGC037ではじめて黄色パフォ取れて自分なりに成長を感じたのと、(個人的に)自分が出来る出力ってなんだろうみたいなことに最近関心があってその一環としてこのブログを(午前3時の深夜テンションで)書いている次第です。
やったこと
- Atcoderのコンテストにはなるべく出る。(非ratedにはあまり出てないけど、ratedなら灰色のときからAGCでも出た)
- ABC埋め(現時点でAB問題100問、C50問、D25問解いていました。)
- 蟻本初級
- Twitterで競技プログラマーをフォローしてコンテスト後のTwitterに参加する
- けんちょんさんの記事を読んだり写経したりする
- 水色行った人のブログを読む
- *色になるまでにやったことブログを読む
- Atcoderの問題を分類してみた、を解く。
競プロerとしては珍しく?Codeforceにはほとんど出たことが無いです。
時間順に追ってみる。
水色になるまで
最初はとりあえず出る→解説を読む→知らない単語を調べる→できそうなら実装する。というのをぐるぐる回していました。これで自分は緑の上の方まで行きました。それまでに身についたことを並べておきます。
身についたこと
知ったこと(書くのはつらい、またはやったことがない)(水色になってから知ったことがほとんど)
- (複雑な)DP
- 隣接リスト
- ダイクストラ法
- ベルマン–フォード法
- いもす法
- セグ木 グラフ問題が出たら捨て問みたいな学習の仕方ですね、、、。ただこれでもC問題くらいならほぼ解けるようになります。
(今と環境は違います)水色になるためにはC問題早解きとD問題打率4割~6割必要と言われていました。 これらを身に着けた上でC問題まで20分で解けば水色パフォがもらえたので、C問題の過去問の早解きを頑張りました。
水色になってから
- ABC埋め
順位表から300点問題を1:30とかでACしている人たちがいると知りました。自分がこれを成す場合少なくともタイピング速度が足りていません。ある程度快適なコーディング環境のためにVSCodeにvim keybindをいれて使ってみたり、Emacsを使ってみたり、VImつかってみたりしています。
Twitterで強い人達(大きすぎる主語)はAtcoderの問題を埋めるということをしていることを知ったので、タイピングの練習がてらABCのAB埋めをしています。計算ドリルみたいなノリで、やっておくと思考と手がシームレスにうごくようになる気がします。これに関して強い人(大きすぎる主語)がABCのA~Dは考察量が同じとTwitterで発言されていたので、最近はC問題も解いたりしています。(D問題はまだ時間がかかりすぎるので埋めていません)
また、Atcoder-predictorやAtcoder-toolsなど各種ツールを入れたのもこのあたりです。
- 蟻本初級編
蟻本が2週間だけ借りられる環境があったので、借りて解けるところまで解いていました。priority_queがなぜ早いかとかもグラフを用いて解説してくれる上、コード例もきれいなので一番学習効率が高いです。なにげに一番大きいのは競プロで強くなるためにはどのようなことを知れば良いのかが簡潔にまとまっていることだと思います。
- けんちょんさんの記事を読んだり写経したり
問題名を打ち込むと上位(1番上であることもしばしば)にけんちょんさんの記事が出てくるので読みます。考え方(どうしてそういうことが思いついたのか)から実装までを丁寧に追ってくれるのでとても助かっています。今なら AtCoderの問題を分類しました - Qiita の記事もまとまっていて目次を見るだけでもためになると思います。
- *色になったブログを読む
これは自分のやっていることがまちがっていないか、邪道じゃないかを確認するためと、まだ見えていない赤色への道のりを学ぶためです。なんとなくですが、それぞれのアルゴリズムを学ぶのは水色~青色くらいで終わりで、その後は複合して解くみたいになるんじゃないかと思っています。そのためにも実装方法は分からなくとも、こういうことが出来る実装方法があって、それはこういう名前なんだよっていうことをストックしておくことが重要なんじゃないかと思っています。例えば、遅延セグ木は区間に対する最大値最小値などを評価出来るデータ構造で、入力と出力にO(logN)かかる代わりに、評価moO(logN)で済む、みたいなことをストックしておくことです。ここらへんの計算量とアルゴリズムのdictionaryは別の記事で書きます。
これから何やるの?何したい?
ABC埋めは続けると思いますが、まとまった時間ができたら蟻本を再開させたいですね。あれを1週は回してそこから景色を見てみたいですね。おわり