AtCoderで青色になるまでにやったこと
AtCoder Beginner Contest 197（Sponsored by Panasonic）にて、AtCoder青色になりました。
競技プログラミング界隈の風習にならい、色変記事を書きます。
naga on Twitter: "初参加から2年半、やっと青コーダーになりました！！！！！！！！… "
水色の記事はこちら。
自己紹介
21卒の大学院生で、来る4月からエンジニア職として働き始めます。専攻は生物で、研究で必要になり勉強していたところプログラミング自体にハマって今に至る、という感じです。
最近はマラソン型コンテストにお熱で、HTTF2021予選で64位になったり、ハル研究所プログラミングコンテストで18位入賞したり、AHC001で108位になったりしました。トップには全く敵わないものの、個人的には楽しんで取り組んでいます。
精進
AtCoder Problemsのスクショがわかりやすい気がします。 令和ABC-Eは割と埋めていて、Fに手がついていません。緑diffまでは埋まっていますが、水diffのめんどくさそうなのは放置しています。青diffもたまに解説ACする、という気まぐれ精進が見て取れますね。 2020年後期からほとんど精進ができていないのは、マラソンにハマり始めたり修論で忙しかったりしたためです。修論の追い込み期間はコンテストに出るのをやめていました。
それでもレートが少しずつではあるものの伸びているのは、コンテストにはかかさず参加するという習慣を維持できたのが大きかったのではないかと思っています。コンテストで結果を出す力は、コンテスト（orバチャ）でしか養われないと思うので。
コンテスト
上述のように、AtCoderのコンテストにはほとんどかかさず参加していました。土曜の夜は何よりもコンテストを優先していました。その結果、コンテスト参加回数は122回(全体でランキングで119位)になっていました。何も考えずにとりあえずコンテストに参加するのは、モチベーションを切らさない意味でも大切だったと思います。
勉強していたこと
高校数学も競プロに関係するような範囲は苦手で、大学数学もほとんど手がついていなかったため、競プロに必要なことは競プロで学んでいます。特に、場合の数確率、整数の範囲は、段々成長しているのかなと思っています。場合の数、整数ともにマスターオブシリーズがおすすめです。苦手で困っている人は、最初の数ページだけでも読んでみると捉え方が変わるんじゃないかと思います。
勉強したことで好きな考え方は、決めうち二分探索、拡張ダイクストラ(グラフを拡張したダイクストラ）、主客転倒です。最近は形式的べき級数の考え方に魅了されていましたが、役に立てるほど身についていないので、いつかマスターしたいです。
DP
- LIS
- 耳DP
- 数え上げDP
- 木DP
- 全方位木DP
二分探索
- 決めうち二分探索
- 単調性を見つけるのがうまくなった
貪欲
- 区間スケジューリング問題
- 解法の一部に含まれる貪欲要素に気を配れるようになった(DPのときとか)
数え上げ
- 主客転倒
- 包除原理
- 期待値の線形性(というかだいたい数え上げだと思って解いてる)
- マスターオブ場合の数を読んだのがよかった
データ構造
- BIT
- セグ木
- 遅延伝播セグ木
整数関連
- 中国剰余定理
- 拡張ユークリッドの互除法
- エラトステネスの篩
- 高速素因数分解
文字列
- Suffix Array(使ったことない)
- Z-algorithm(使ったことない)
- manachar(使ったことない)
ゲーム
- Nim(XORが大事)
- 真似するやつ
- 過半数が大事
- min-max法?
グラフ
フロー
- 最大流
- 最小費用流(使ったことない)
- 二部グラフのマッチング(使ったことない)
その他テクニック
紙に考察を書くこと
コンテスト中、紙にどの程度メモしますか？
touristの精進配信をみたときに、彼らが紙には何もメモせず、画面を睨みつけながら考察しているのが印象的でした。
私は、競プロを始めたばかりの頃、メモをしないで考察するということが理解できませんでした。暗算も苦手、すべて書かないと理解した気にならない、という癖があったのではないかと思います。レッドコーダーは、簡単な問題は紙に書かないということを知って、驚いたと同時に、自分もできるのかな？と挑戦しました。最初は確かに苦しいのですが、段々と頭の中だけで動かせるものが増えていきました。今となっては、メモをすると無駄な考察が増えるばかりだなと思うことも増えました。
この紙に書かずに考察する能力は、早解きに必須だと思いますが、精進の量を増やす上でも役に立ちました。頭の中に問題をセットして、歩きながら解くということも可能になり、いつでも精進ができるようになったことで、問題を解かなければならないというプレッシャーも減りました。
2x105の数列を頭に浮かべながら生活するのも悪くないです。
レーティングを気にすること
レーティングを気にする人は多いと思います。色変記事みたいなのがあるように、400刻みには何の意味もないのに色を気にする人は多いです。
結論からいうと、レーティングは気にしても上がらないので、考えないようにしていました。
こう考えるきっかけになったのは、コドフォでした。コドフォはAtCoderに比べるとレートの変動が激しいため、レートは溶けるときは溶けるという、当たり前のことを教えてくれました。
レートが溶けるのを気にしているとコンテスト中問題以外にメモリを奪われるので、無視するのが賢明だと最近は思い込んでいます。実際ここ数ヶ月はレートの浮き沈みが激しいですが、実力が上がればいつかは戻るので、気にしていません。今後も水色に落ちたりするとは思いますが、長い目で見て実力が向上していれば問題ないという気持ちでいます。
マラソンの影響
マラソンにハマってから、実装力が格段に上がりました。マラソンは令和ABC-B,Cレベルの問題を自作して解くという流れで進むので、アルゴ型にもいい影響があったのではないかと思っています。計算量を意識して作問しなければならないので、アルゴの問題でも受け身にならずに考察を進める力がついたような気もします。何より、アルゴの競争に疲れていたとき、マラソンで自分との戦いに挑戦した結果、悩みが馬鹿らしいものだということに気づけました。みんなもやろう、マラソン。楽しいよ。
最後に
最後まで読んでいただきありがとうございました。競プロで必要になったことはその場で学び直してなんとか這い上がった人間なので、そういう悩みを抱えている人に少しでも役に立っていたらいいなと思います。
まだ伸び代はあると思っているので、黄色になるまでは続けたいと思っています。黄色になりたい理由は、マラソンでできることを増やしたい、ただそれだけです。
マラソンに興味を持った人は、以下の記事などもどうぞ。最近は入門記事も増えているので、気軽に参加してみましょう！
