AtCoderのレートが水色になるまでにやったこと

水色になったので自分語りをしたくなりました.
水色の大したことNASAofNASAなど思う人もいるかもしれませんが, 自分にとってはそこそこの到達点なのでここでだけはいろいろ言わせてください().

はじめてのコンテストのおもひで

2018/06/16に初めてのコンテストは30分ぐらい遅れての参加だったことを覚えてます.
Twitterやってたら今日やってんだ〜と思って参加しました. プログラミングが趣味でB2のときにたまーにAtCoderの問題を見ていたのでIDは持っていました. そのときはアルゴリズムのアの字も知りませんでしたが.
B問題のコーナーケースが通らずA,Cの2完という微妙な結果でした.
このときに大学の講義でアルゴリズムについてやっていたので, ある程度勉強すれば競プロもできるかもしれないと思い, 本格的に勉強をはじめました.
そのときに, ぼくの競プロは始まりました.

今までのレート

競プロを始めてから今に至るまで, 時系列順に成績を振り返ってみます.
f:id:xxxasdfghjk999:20181017224808p:plain
(右下の時計君の自己主張はゆるしてください)
6月半ばに競プロをはじめ, 3回目のコンテストで茶色(2018/07/01)になり, 6回目のコンテストで緑色(2018/07/21)になっています. そこからさらに7回のratedコンテストを重ね, 水色(2018/10/13)となっています.
ここで, 過去のAtCoder過去問埋め精進記録を見てみましょう. f:id:xxxasdfghjk999:20181017230137p:plain
軸がおおざっぱですが, 夏休み中の8月に猿のように精進を重ねていたことがわかります.
しかし, 実を言うと8月辺りで猿精進を重ねた後のコンテストの成績はあまり良くなかったです. ABC105とABC106, ARC102辺りではC問題が解けていなかったり, パフォが伸びなかったりで, (ABC105は運良く(?)unratedになりましたが...)正直メンタル的にだいぶ厳しかったです. グラフを見てみても, この辺で停滞してる感じです.
しかし, 来る9月中頃, 予定も立て込んでいて精進もできていなかったのですが, ABC110で初めて上限パフォを出すことができました(これは運悪くunratedになりました). おそらく, この辺りでやっと8月中の精進が効いてきたのかなと思います.
精進の効果が現れるのには時間がかかることを意識するのは個人的に重要だと思っていて, 成果がでなくてもしゃーないかーとか思いながら気楽にできる点が精神にいいと思います.
ABC112では, WAを重ね続けてしまってパフォは微妙なものの全完を成したので, なかなか成長を感じました.
そしてAGC028のA早解きで青パフォを出して水色になりました(ABCで1600出してなりたかった気もします.)

水色になるまでにやったこと

本題です.
その前に, 自分の経歴(?)を紹介しておきます.

わたし

  • 競プロ開始時点で地方旧帝情報系学部のB3
  • 講義や趣味で軽いプログラミング経験あり(Haskell(趣味), C(講義でよく使ってる) , SML(講義でちょっとやった), Python(Twiterのbot作ったぐらい))
  • 微妙な高校を出ていて, 特に数学やら算数が得意でもなんでもない
  • 中古のPC屋で15kのThinkPadubuntuを突っ込んで環境を整えたもので競プロをやっています(emacs使い)

特に, いつでも気軽に起動できるノートPCがあって, ubuntuでCtrl + Alt + Tでいつでもターミナルが開けて, コマンドちょちょいと打つとコンパイルできたりemacsが開けるというのがだいぶ大きかったように感じます. ものぐさで, ささっとできるものでないと続かないんです.
CをやっていたのでC++もすんなりわかったような気がします(わからない).
隙あらば自分語りをしてしまいました. この辺を前提にして読んでください.

蟻本

競プロを始めるとともに, amazonでポチりました. しかし, 新品が高かったので第1版の中古を買ってしまったんですね. この前本屋に行って蟻本を見かけたら, 第2版というものがそこそこ厚くて驚きました... 幾何やらなんやらの追加コンテンツができていたみたいですね. うーん安物買の銭失い...

蟻本でやったこと

やった項目は
2-1 すべての基本"全探索"
2-2 猪突猛進!"貪欲法"
2-3 値を覚えて再利用"動的計画法"
2-4 データを工夫して記憶する"データ構造"
2-5 あれもこれも実は"グラフ"
3-1 数学的な問題を解くコツ
3-2 値の検索だけじゃない!"二分探索"
3-3 厳選!頻出テクニック(1)
は一通りはやりました.

蟻本はぶっちゃけわかりにくいです. わかりにくいんですが, 競プロの問題がテクニック別にカテゴライズされているので, テクニックの辞書として使えます. コンテスト中に詰まったらとりあえずペラペラして使えそうなものないかなーって探すこともできるので, 持っておいて損はないです.

蟻本がわかりづらいと感じたら, けんちょんさんのQiitaのAtCoder蟻本(大変お世話になっています)とか見てみるといいと思います. いい問題がたくさん集まっていて, 解説もネットの海を探せばいろいろあります.

蟻本に関しては以上です.

yukicoder 埋め

8月の終わりぐらいにyukicoderをやり始めました. AtCoderとは毛色の違う問題が多いですが, 解くのが面白い問題が非常に多いです. 緑のときは★2 , または★2.5ぐらいを埋めていました.

AtCoder過去問埋め

こんな進捗です.
f:id:xxxasdfghjk999:20181017234419p:plain
D問題がわりかしたくさん埋まっていますが, 水色を目指すのならC問題を埋めたほうがよかったかなーと思います.
コンテスト中にDが解けずとも, Cの早解きでパフォが十分とれることがかなりありました.
ABC-C埋めが終わったらARC-A埋めもいいと思います. A,B問題が埋まっていませんが, やってもいいと思います. 虚無埋めなどと言われてますが, ACとれるのは楽しいですからね.

過去問を解くときは, 20分ぐらい考えてわからなかったら解説を見る, の繰り返しです. そして, 重要な問題だと感じたら記事を書く... という感じです.
こういう過去問埋めのときに知らないテクニックが解説に出てくると萎えるので, 埋める前に蟻本(中級までで簡単なところ)をやっておくことをおすすめします.

ブログ

あなたが見てくださっているこれです.
解説ブログを書くと, 意外と自分理解してないなーとか思うことがよくあって, いろいろ発見があります. 解法の言語化っていうのは大事だと思います.

Twitter

8月の終わりぐらいだったか競プロ垢を作りました. 強い人やレートが同じぐらいの人をフォローすると, 憧れやら, 自分もがんばんなきゃなーと思ってがんばれます. あと, コンテストの情報が入ってきたり, 新鮮な解法情報がコンテスト後に流れ込んでくるので, 作っといてよかったと思います.

まとめ

  • 蟻本でよく使うテクニックを学ぶ
  • 過去問を解く
  • 解法を言語化する
  • 同好の士をフォローする

こんなことをやってきました.

これからの目標

とりあえず青を目指してがんばりたいです.
まずは蟻本を進めて, セグメントツリーなるものをがんばって作りたいです.
まだまだこれからですね.