AtCoder青になりました - 橋梁管理日誌

コンテスト初参加から1年で青くなることができました！ pic.twitter.com/fND6dnbB5b
— まほろば (@mhrb_minase) 2019年4月20日

先日行われたTenka1 Programmer Contest2019でレートが1657になり、青色に到達しました（なお執筆時点のレートは1642な模様）。300-600-800-800のセットの1完早解き黄パフォで青になっており、多少後味は悪かったですが、ともかく色が変わって嬉しかったです。ここでは、n番煎じながらやったこと等をまとめたいと思います。

～灰

大学の競技プログラミング部に入部しました。AtCoder Programming Guide for beginners(APG4b)で、先輩方に教えていただきつつ競プロに使う言語であるC++の基礎を学びました。その後、コンテストに1回参加しました。

学んだアルゴリズム等

この頃はif文とfor文が書ける程度で、単純な演算や繰り返し処理ができた程度だと思います。

～茶

競技プログラミング部での活動として、バーチャルコンテストをやっていました。問題セットはABCの過去問でした。また、AtCoder Beginners Selectionを埋めたり、AIZU ONLINE JUDGEのLessonやLibraryをちまちまとやったりもしました。

学んだアルゴリズム等

多重for文による全探索
約数列挙
素数判定
配列上の二分探索（下3つを使うようになるのはもう少し後かも）

～緑

狂ったようにABCのA,Bを埋めていました。いわゆる虚無埋めですね。ただ、このおかげでB問題までを解くスピードが上がり、後ろの問題にかけられる時間が増えたと思います。また、実装にどう落とし込むのかというのが分かってきたところで、300点問題を通せるようになってきました。

学んだアルゴリズム等

std::sort
std::next_permutation
最大公約数（ユークリッドの互除法での実装）
最小公倍数
素数列挙（エラトステネスの篩）
再帰関数を用いたあれこれ（例えばこういうの ※ネタバレ注意を再帰で計算したり）
累積和
いもす法
幅優先探索
深さ優先探索
余りを取る問題の足し算、引き算、掛け算
繰り返し二乗法

～水

まず、C問題を確実に時間内に解けるように、過去問のC問題を埋めていました。C問題がほぼ確実に解けるようになった頃には、自然と400点のD問題を自力で解けるようになっていました。先述した競技プログラミング部内でのバーチャルコンテストや、部内で競うように精進していたことなどの成果が出たと思います。そして、300点以下を高速で通すマンになりました（流石に青以上の方々と比べられるとアですが）。これにより大失敗を回避できました（実質的な力がついていなくてよくなさそうですね）。このあたりから、競技プログラミング部内のバーチャルコンテストはAOJ Arenaを用いて行われるようになりました。

学んだアルゴリズム等

bit全探索
二分探索
union-find木
素数modの逆元
combinationの計算法
グラフの最短経路問題（ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法）
最小全域木（コンテスト中にこれを使った記憶はありません）
ナップサック問題等の易しめの典型DP
メモ化再帰
2次元以上の累積和・いもす法
半分全列挙

～青

300点以下を爆速で通すマンになりました（流石に黄色以上の方々と比べられ（ｒｙ。必然的に400点くらいの問題もそこそこのスピード（30分前後？）で通せるようになり、また、ABC+ARC相当の企業コンテストやAGCが続いたこともあり、レート上昇の要因は早解きがかなりのウェイトを占めています（考察力をつけなさ～い）。とは言っても、500,600点程度の問題は3割くらいは通しているはずなので、早解きにも限界があると思われます。400点～600点くらいの得点帯の過去問を解くようにした成果だと思います（にしては突破率が低いような・・・？）。最近では～800点くらいまででコンテスト中に見た問題は復習するようにしています。コンテストに月1回出るか出ないかくらいの頻度でCodeforcesに手を出しています。yukicoderもちょこっとかじりました。