AtCoder 青になりました

昨日の AGC で念願の AtCoder 青になったので、記念としてポエムを残しておこうと思います。

AtCoder 青になりました！！ pic.twitter.com/sOkR4awItI
— rodea (@rodea0952) 2019年10月5日

競プロを始めるまで

高校生のとき、情オリに出ていた友人がいたため、「競プロ」という存在自体は知っていました。が、プログラミングをやったこともなく、数学が特別得意という訳でもなかったので、特に興味を持ちませんでした。

紆余曲折あり、気が付いたら情報系の学科に進んでいました*1。B2 から学科の専門科目が始まり、そこで初めてプログラミング（C 言語）をやりました。しかし、全く慣れることができず、ほぼ学科同期から書き方を教えてもらいながら課題を解く、といったような散々な感じでした。当時、

「自然数 N が 1 つ与えられる。その自然数 N の各桁の数字の和 S を求めよ。」

といった問題にも全く歯が立たなかったのを今でも鮮明に覚えています。

このままではまずいと思い、プログラミングの練習をしようと色々探して偶然見つけたのが yukicoder でした。パズル感覚で問題を解くことが面白く、暇なときにぼちぼちやっていました*2。この頃から少しずつハマっていき、螺旋本・蟻本を買ったり、競プロer の方々をフォローしたりしました。

B3 になって、大学の競プロサークルに入ったのと同時に、AtCoder に取り組むようになっていきました*3。

灰 → 茶

まず C++ を最低限使えるようにしました。また、yukicoder の星 1, 1.5 あたり、AtCoder の 200 点や簡単な 300 点を解いたりしていたと思います。

必要だったスキル

if, for, while 文や配列
全探索
競プロに慣れる

茶 → 緑

AtCoder の簡単な 400 点を解いていたと思います。また、螺旋本や蟻本の簡単なページを読んでいた気がします。
旧 ABC の C まで早解き、あわよくば全完が可能になってくると突破できると思います。僕自身もこの頃に初めて全完していました。

初、ABC全完！！！
— rodea (@rodea0952) 2018年6月10日

必要だったスキル

C++ の STL
UnionFind
累積和
貪欲法
GCD, LCM
簡単な DP
エラトステネスの篩

緑 → 水

緑になったことで更にモチベが上がり、螺旋本を大体読んだ気がします。また、AtCoder の過去問埋め、特に ABC-C 埋めを頑張っていました。

ABCのC埋めが終わった…！ pic.twitter.com/stgUAUcokF
— rodea (@rodea0952) 2018年9月5日

あとは、会津合宿 2018 に参加して強い人達を間近で見たこともかなり刺激になりました。

ACPCお疲れ様でした
初めての合宿・他大競プロerとの交流でしたが、みなさん優しくて強くてとても有意義な時間を過ごせました！ありがとうございました〜 pic.twitter.com/nujk1a9oUl
— rodea (@rodea0952) 2018年9月21日

必要だったスキル

最短路（ダイクストラ法、ワーシャルフロイド法、ベルマンフォード法）
最小全域木（クラスカル法）
尺取り法
imos 法
二分探索
繰り返し二乗法
逆元
約数列挙・素因数分解
半分全列挙
組合せ

水 → 青

ここからが長かったです。実際、1 年とちょっとかかりました。
自分の場合、ポテンシャルで水色を保つのは確実に無理なので、AtCoder で難しい 400 点に挑んだり、500 点以降の問題に着手したりと、とにかく問題を解いていきました。また、実装力が乏しかったので、ICPC 対策も兼ねて AOJ の問題を中心に解いているときもありました。解いていく中で、分からない箇所は公式解説に加え、他の方の解説ブログやコードを見て、腑に落ちるまで考えることを心掛けていました*4。

また、蟻本の中級編を読んだり、サークルの勉強会で水色からすると高度なアルゴリズムを学んだりと、コンテストに出たときに使えるように知識を蓄えていきました。

2019 年 1 月末～ 2019 年 8 月末の約 7 ヵ月間はレートが停滞し、かなり辛かったです。特に、初令和 ABC で早解き全完 & 初黄パフォを出した回が unrated になったときは応えました…。いつかレートが上がると信じて地道に精進し、積極的にコンテストに参加するようにしていました。

7 ヵ月分の精進の成果か分かりませんが、ABC140, 141, 142 そして AGC039 の直近のコンテスト 4 回で +165 することができ、念願の青色を達成することができました。これらのコンテストでは「以前解いたあの問題の解法を少し変えたらいけそう」といったように、今までやってきたことが活きてきたのを感じる瞬間が多く、感慨深かったです*5。