AtCoderで水色になりました！
zekeです。AtCoderで競技プログラミングをしている大学1回生です。先日、三日連続rated(初日はunrated)でめでたく入水できましたので、色変記事を書いた次第です。
この週末で+113した pic.twitter.com/K1PMWfdZVQ
— じーく (@zeke8080) January 12, 2020
約10か月で水色になれました。4月に一応の目標としていた水色に到達できてほっとしています。水色の色変記事を書くことは夢だったので、自分語りを加えながら、これまでの競プロ人生を振り返っていきたいと思います。
一応の注意
完全な自己満記事です。覚悟してください。
競技プログラミングを始めたきっかけ
高校まではプログラミング自体をほとんどやったことがなく、むしろハードの方面をやっていました。ロボカップなどに出ていたこともありました。しかし、大学の新歓でKMCというサークルに出会い、そこで競プロと出会いました。そのサークルでは毎週、競プロ練習会が開かれていて、自分のようなC++を触ったことのないような初心者に対しても親切に教えていただいたので徐々にはまっていった感じです。先輩方には感謝してもしきれないです。AtCoderもその流れで知って、ABC124にて初参加を果たしました。平成ABCにしては簡単な回で3完などをしています。
灰～茶にかけて
先述した通り、毎週の競プロ練習会でいろんなことを教わったのですが、始めたばかりの自分には荷が重く、あまり理解はできませんでした。その頃は、あまり競プロを熱心にはやっておらず、毎週末のコンテストに出るだけだったのですが、7月ぐらいにICPCがあることを知りました。これは大学生向けの競プロの大会であり、3人組で出るものだったので、同じサークルの同じく同時期に始めた人と組んで出場しました。このコンテストのために最低限のC++の文法(配列、データ構造)や基本的なアルゴリズム(全探索など)を頭に突っ込んでいた覚えがあります。そして、コンテスト直前ぐらいで茶色になりました。
そのあとにあったICPCですが、やはり初心者には荷が重く、2完しかできませんでした。しかし、その時印象的だったのは、自分たちの向かいのチームが終わる直前で難問を通していたことです。そのチームは「heno world」さんで、めちゃくちゃ強い方々だったのですが、その姿を見て「早く強くなって、あんなふうになりたい」と思った記憶があります。
茶～緑にかけて
ちょうど夏休みに入ったので、大学図書館に行っては精進を繰り返していました。蟻本を買ったり、drkenさんの記事(神記事たくさん！)を読んだりして、いろんなアルゴリズムを頭に叩き込みました。全探索、BFS、DFS、累積和、二分探索、尺取り、動的計画法などのアルゴリズムの存在を知りました。とにかく、このころはICPCで振るわなかったこともあって、必死でABCのC問題を埋めていた気がします。この時、同時並行でゲーム製作をしていたこともあり基本的な実装力がついた気がします。具体的にはA、B問題は確実に解ける、C問題も令和ABCになってからは安定してとけるようになる、といったところでしょうか。レートが伸び悩んだ時期もありましたが夏の終わりまでに色変を目指して頑張っていました。そうやってしているうちに、緑パフォが安定してきて9月初めごろに緑になれました。
緑～水にかけて
かなり大変でした。緑になるまでに、いろんなアルゴリズムを学びましたが、それがまだ実践段階にはなかったのです。具体的には二分探索の使いどころや基本的な動的計画法の書き方とかです。またbitを用いた問題(XORなど)、グラフ問題と出会った問題と出会ったのもこの頃です。しかし、今まで学んだことを組み合わせて使ったり、違った視点から見る問題にも出会って、だんだん競プロの楽しさに気づき始めました。問題もAtCoderにとどまらずAOJやCodeforces、yukicoderにも手を出して片っ端から解いていた感じです。難易度帯としてはAtCoderだとdifficultyが緑～水ぐらい、yukicoderでは星2～3ぐらいでしょうか。AOJは新たなアルゴリズムを知った時に、それを試すために利用しました。コンテストのほうは令和ABCに切り替わってからA、B、C問題はACして当たり前、Dも大体解けて、E問題にチャレンジしていこうという感じです。しかし、時々爆死してしまうこともあり、それは他の記事にまとめています。
11月ぐらいで順調に上がっていたレートがカクっと下がったり、解けそうで解けない問題に出会ったりして歯がゆい思いもしました。しかし、この頃に始めたTwitterであほみたいに強い方々や、同じぐらいのレベルで頑張っている人を見てモチベをもらったりしていました。そんな感じで精進を続けていたら二回のunratedを経て無事に水色になりました。
やったことに関してあれこれ
精進などの内容をつらつら語ります
その１：コンテストに出る
多分一番大事なのでは？と思います。もちろんABCは出るとして、諸意見ありますがAGCや企業コンにもどんどん出るべきだと思います。自分は理不尽に難しい問題を解くのが好きなこともあるのですが、二時間ぐらい頭を抱えながら問題を考える経験を付けるべきだと思います。また、ACしたときの快感は凄まじいものがありますし、たとえできなかったとしても解説を見るなどして、いろんな気づきがあるからです。Twitterでコンテストについてワイワイするのも楽しいですし、とにかく出ましょう！
その２：問題を解きまくる
はい、精進です。解きまくりましょう。個人的に精進の助けになったページを下に貼ります。
drkenさんの蟻本シリーズです！蟻本で習った内容をAtCoderの問題で復習できるので、最高です！
はまやんはまやんはまやんさんの分野別問題まとめページです！ある分野に関して集中的にやりたいときに最適です。
AtCoder Rivalsというサイトです。登録したユーザーの問題の提出状況をTL形式で観測できます。異常精進している人々を観測してモチベを上げましょう！
他にもたくさんのサイトにお世話になりました。感謝します。
その３：刺激を受ける
こちらのサービスは天才や人外がうようよいて、奢りそうになった時に見るといいかもしれません！！！
他にも、解説記事を書いてみたり、サークル内で講座をやったりすることで自分は精進をしました。拡張などを作ったりするとテンションが上がります。
水色になるまでに勉強したアルゴリズム、テク(若干、上から目線)
いろんなマクロ
自分は緑になったぐらいでC++でマクロを導入しました。賛否が分かれますが、自分は競プロの本質のみを追求できるので愛用しています。
全探索系アルゴリズム
BFS、DFS、bit全探索、貪欲などを含みます。この辺りは類似問題を解きまくって、慣れるしかないと思います。実装が重いことがあるので注意です。コンテストでは真っ先に疑う癖をつけたほうがいいと思います。
二分探索
これも真っ先に身につけたほうがいいと思います。応用範囲が大きいですし、何よりよく出ます。これもコンテストで真っ先に疑うべきものです。
(基本的な)動的計画法
最初の難関です。ナップサックを始め様々な形があるのが特徴です。自分は、全然できなかったのでEDPCなどを解きまくって習得しようとしています。以下、自分が書いた精進記事です。
累積和
めちゃくちゃ出ます。他のアルゴリズムとの組み合わせの相性がとてもいいです。一次元、二次元imosを習得しましょう。
以下の記事が最高なのでぜひ読みましょう！
グラフ
最短距離問題、全探索系問題、木、二分木、抽象グラフに落とす…などバリエーション豊かです。概念自体を競プロで初めて見たので大変でした。
こちらも神記事なので読みましょう！
UnionFindなどの集合系
UnionFindだと思わせない問題が多いように感じます。
小学校算数
いっぱい出ます。組み合わせ、確率、整数、いろいろあります。自分は中学受験勢だったので当時のことを思い出しながらやっています。
受験数学
いっぱい出ます。整数、幾何、三角関数、いろいろあります。数学が得意な人々は持ち前の数学力で殴っていくらしいです。自分はよわよわです。
C++の文法あれこれ
コンテナ、構造体、STLなどです。C++には競プロのために作られているのではないかと思うほど便利なSTLがあったりするので、ぜひ覚えましょう。
ぶっちゃけ使えなくても大丈夫なやつ
セグメント木など
これから勉強していこうと思います。一回だけ実戦で使ったことがあり、青パフォをたたき出したときには発狂しました。
幾何とか
あまり出ないし…誤差に注意なことを覚えておくといいかもしれません。
フローとか
知ってはいるけど実戦では使ったことはない、そのようなものです。
他Twitterでみかけるような難しそうなやつ
ぶっちゃけそんなものを覚えるよりも、既存の知っているアルゴリズムの熟練度を上げるのが大事だと思います。
最後に
自分は大学に入ってから競プロに出会ったのですが、この界隈には天才、奇人、人外、神、その他諸々がうようよしています。自分はただの凡人なので、そういった人たちを見ると自己肯定感がガリガリ削られます。でも、自分は頭を限界まで使う競プロが好きで、この界隈に入り込んだことの後悔を全くしていません。むしろ、自分の力がどこまで通用するか試したいぐらいです。この度は水色になりましたが、次は青目指して猛進していきたいです(/・ω・)/。
長くなりましたが、ここまで読んでいただきありがとうございました。
