AtCoderで水色になるまでにしたこと
はじめまして。kawap23(twitter ID: kawap23)と申します8月10日に行われたAtCder Begginer conntest 137で水色になれたので、(競技プログラミングを始めてから)今までにやってきたことを(忘備録も兼ねて)書いておこうと思います。
現状~水色~
初回参加が2019年4月20日で8月10日現在最高1220で水色になりました。
爆上がりや爆下がりしているのはAGC, ARC相当のコンテストで1問無理やり通したり、嘘通したり、0完激萎えをかました結果です。
ちなみに精進の具合はこんな感じです。ABCのC問題はあと2問でABCのD問題に手を出し始めてます。
競技プログラミングを始めるにあたって
自分のバックグラウンドは物理であり、プログラミングに触れた経験は大学の授業(Fortran 12時間)、実験・測定用の(Labview)グラフィック型言語のみであり、if文、for文の概念(?)は理解しているという程度でした。その中で大学院の授業でpythonを使って機械学習の基礎的なことを授業があり、その中でプログラミングの練習がしたいと思い、プログラムを書く練習として競技プログラミングを始めました。
が、思った以上にAtCoderで問題が解けないことにイライラし、気がついたら機械学習の授業と課題を放棄して競技プログラミングのめり込んでいる自分がいました。
水コーダーになるまで
ようやく本題ですね
黒色~灰色
そもそも始めた時点では標準入力とは?という状態だったため、先人たちのブログをググりまくりながら参加するという状態でした。なので100分フルに使ってA, Bをギリギリ終わらせるという状態でした。
この時期に重視したことは、
- 入力の受け取り方で悩まないようにすること-->過去のA, B問題をする
- (少なくともコンテスト時間中は)300点400点問題でも手を動かして試し続ける
- 毎日1問は新規ACする
です。特に僕のような初心者は、やったことを忘れないように毎日繰り返すことが重要だと感じました。
灰色~緑色
ABC問題のCに取り組むと同時に、「いかに早く正確にA, B問題を通すか」を重要視していました。今はどうかわかりませんが、少なくとも数ヶ月前はAB早解きで緑パフォは出ていました。
この時期にしたことは
- 蟻本を買った(あくまで、買った)
- DFS, BFS, 累積和をコンテストを通して学んだ
- AGCも含めて、(レーティング的に)出ることができるコンテストに参加した
AGCはA問題だけでも解けるとレートが爆上がりするので、出得だと思います。
緑色~水色
この時期は真面目に競技プログラミングの勉強をしないとレートが伸びないと感じました。勉強法としては、ABCのC問題埋めをメインに、蟻本の初級編+コンテストで出てきた中級編の学習をしていました。結果的に学んだこととしては
- 競技プログラミングの楽しさ
- 深さ優先探索
- 幅優先探索
- bit全探索
- 順列
- 最小公倍数・最大公約数の性質の確認、書き方の確認
- キューと優先度付きキュー
- 累積和
- いもす法
- MODの四則演算
- 動的計画法
- メモ化再帰(この中では一番好き)
- 二分探索
- Union-Find木(たぶん必要ない)
- 最短経路問題(たぶん必要ない)
だとABC137の開始前までは思っていたんですが、あくまで学んだことがあるだけで理解はしていなかったみたいです…。ただ自分の引き出しが格段に増えていることは実感できました(悔しくなるポイントが以前と変わった)。
あとはこの時期は考察の大切さに気が付きました。そもそも制約条件からどれくらいの計算量に抑えないといけないのヒントがもらえる時"も"あります。
とりあえず過去問解きながら蟻本を斜め読みするぐらいがちょうどいいと思いました。
水色~青色に向けて
ここからは次のステップに向けて自分が必要だと感じていることを書きます。青色になって答え合わせしたいです。
最後に
水色になるまでに様々な方のブログやコードを参考にさせていただきました。
特にmaspyさんのコードは「ひぇーーー」って感じで、知らない知識が詰まっていてすごく勉強になりました。
あとはじゅっぴーさんのブログ「じゅっぴーダイアリー」は分類等がしっかりしているのに加えて、おもしろいので、良く読んでいました。
(勝手に名前だしてすいません)
偉大な先人についていくだけでなく、いつか参考になるようなコードを書けるようになるといいなぁ…
2019年8月25日追記
2019年8月24日に緑色に戻りました…
2019年9月27日追記の追記
2019年9月1日に水色に復帰しました