AtCoderで茶色になった
AtCoderで競プロを始めて約2ヶ月、2020/11/01 のABC181で茶色になったのでブログ書きます。自己紹介をしつつ、これまでどう勉強したのかまとめてみました。
その後の記事
【AtCoder】入緑しました！！！ - shu8Creamのブログ
AtCoderで水色になりました！ - shu8Creamのブログ
自己紹介
職業：大学4年（情報系）
競プロ歴：約2ヶ月（20/09/13開始）
使用言語：C++
生息地：shu (@shu8Cream) | Twitter
大学で勉強したことも触れつつまとめてるので参考になったら嬉しいです。
僕の簡単なスペックとしては、プログラミング力は、自分ではよくわからないので大学の成績をあげると真ん中ぐらい、なのでそんな程度だと思ってます。数学力としては、大学受験でいうとセンター数学IA・IIBともに９割以上で２次試験も数学で戦ってた感じはあります。競プロ界隈では数強の方も多いので自分が数強だとは言えないですが、数学は好きで趣味程度に楽しんでます。
レートについて
競プロ界隈にいると上にいる方々が凄すぎて、自分なんてという気持ちが強くなるんですが、茶色も凄いぞって感じで褒めてくれたり、評価していただけると僕が嬉しいです。
正直、茶色の難易度の問題でも本番で解けないことも多々あります。スピードも実装力が求められる問題だとかなり時間がかかったり、数学でゴリ押せる問題だと似たようなレートの中でもかなり早く解けたりするのでまだまだ不安定な部分もあります。
AtCoderでのレート
| 色 | レート | 補足 |
|---|---|---|
| 青 | 1600~1999 | なれたらいいな |
| 水 | 1200~1599 | ここになりたい |
| 緑 | 800~1199 | 次の目標 |
| 茶 | 400~799 | 現在地（427） |
| 灰 | 0~399 | 戻ることはないようにしたい |
| 黒 | 未参加 |
目標としてはこんな感じで最終的には水色を目指しています。青にもなれたらいいですが、今のところ現実味がないです。
茶色コーダーになるためにやったこと
競プロの取り組み方
まずは、AtCoder Problemsの記録をみてもらうのがわかりやすいと思うので載せときます。
こんな感じですね・・・って言ってしまったらこの記事終わるのでちゃんと説明します。解いた問題数は画像の通りなんですが、はじめ頑張っていたのは以下の３つです。
- 本番の形式に慣れる（バチャコン参加）
- 灰問題をひたすら解く
- うーんと悩んで解けるぐらいの問題を毎日一問
僕は実装力が無いと思っているのでひたすらコードを書く事を意識しました。あとは、APG4bで解説されるようなSTL関数やSTLのコンテナは本当によく使うので、実際の問題で試しまくりました。慣れると「この問題set使えるな」とかすぐ頭に浮かぶようになりました。
覚えたこと
- 線形探索
- bit全探索
- 二分探索
- 累積和
- Union Find
- (modint)
意識して覚えたのはこんなところです。どれにしても応用の難しい問題は解ける気はしてないです。とりあえず理解して基礎問題は取れるぐらいにしました。最後のmodintはACLにありますが、使い方覚えていた方が圧倒的に便利です。
大学でやったこと
初めにも触れましたが、情報系の大学にいるため嫌でもアルゴリズムやデータ構造は勉強しました。ここにまとめるために残ってた授業資料見直したんですが、強くなるために必要そうなものは網羅されてそうでした（もう覚えてないけど）。
出す順番が無茶苦茶ですが、一通り知っているので改めて勉強するにも取り組みやすかったです。まだ復習できていないものに関してもそうだと思います。ただ問題は実装がちゃんとできるのか、これが大きい問題で僕自身の課題です。地道にやっていこうと思います。
目標とこれからやりたいこと
入茶したので今後の当分の目標は緑です。期間は年内までに、と言いたいところですがそんな甘く無いと思うので年度内までに入緑できるよう精進したいと思います。
具体的にこれから取り組みたいことと言えば、
- 高校数学の場合の数、確率＋数列の復習
- DPの勉強（EDPC）
- けんちょんさんの本を読み進める（現在DP頑張ってます）
- 茶diff埋め
こんな感じです。競プロ勢のみなさん数学が得意な方もいっぱいいると思いますが、僕は色々抜け落ちている部分があるので高校数学の復習をしたいと思っています。そして、DPは慣れというのも見聞きするんですが、ひたすら精進あるのみですね。最後に茶問題を解ききろう！って感じです。
茶色コーダーのみなさん一緒に頑張りましょう！
こんな記事も書いてます
ヒューリスティックコンテストで大量テストケースを一気に実行したい！ - shu8Creamのブログ
CFR #839 (Div. 3) D. Absolute Sorting 解説 - shu8Creamのブログ
おすすめの本
以前から持っていた本や読んだ本をいくつかまとめておきます。
プログラマの数学
『数学ガール』シリーズを書いている結城浩さんの本でプログラミングに役立つ数学の知識がわかりやすくまとめられています。ソースコードが多く載っているわけではないので、これだけですぐ競プロに使えるほどではないですが、論理・剰余・順列・再帰など高校数学の復習知識やプログラミングする上で大事な基礎の考え方がまとまっています。けんちょんさんの本（一つ下で説明）もいきなりだと難しそうと感じる人は読んでみるといいと思います。数学に苦手意識のある競プロerは『数学ガール』シリーズもおすすめです。（ただ僕が好きなだけ）
問題解決力を鍛える！アルゴリズムとデータ構造
僕が説明するまでもないと思いますが、けんちょんさんの本です。実際の競プロで役立つ知識満載の競プロerなら買いの一冊だと思います。本格的に競プロで戦っていくために学ぶべきものが詰まっています。競プロ本として有名な蟻本だとちょっとむずくて厳しいと感じる人はこの本から始めるといいかもしれません。（こんなふうに紹介してる方が結構います）僕は「蟻本むずそうだな〜」と手を出そうか迷ってる時にこの本が出版されたのですぐ買いました。
まとめ
以上が入茶するまでにやっていたことです。初めてブログを書いたので拙い文章ではあったと思いますが、ここまで読んで下さりありがとうございます。今後も気が向いた時に書いていこうと思うので僕のTwitterで動向を見ていただけると嬉しいです。
