組合せゲーム理論屋が競プロを始め、青コーダーになった話
初めまして、COOH2という名前で競プロ（Atcoder）をしている組合せゲーム理論の研究者です。組合せゲーム理論の問題しかない有志コンテストをいずれ開きたいという野望を持っています。
先日Atcoderで青色になったので色変記事なるものを書いてみようかと思い、ブログを始めました。このブログでは競プロや組合せゲーム理論に関する記事を書いていこうかと思っています。
・始めるまでの能力
高校時代から部活でゲームプログラミングをしていたのでプログラムの経験はありました。Visual Basicを当時は使っており、C++の経験はあまりありませんでしたが、参考資料もC++の方が豊富なので競プロではC++を使っています。
研究者として組合せゲーム理論の造詣は深いです。アルゴリズム系の研究集会とかも顔を出すことがあるのでそっちの知識も多少はありました。
・始めるきっかけ
研究者一本だと不安定なので手に職をつけるという意味でも競プロに興味があり、高校の後輩であるレッドコーダーのjoisino君と会ったときに聞きたいことを聞いてみました（以下はあくまで再現であり実際の会話の文脈を完全に保っているかは保障できません）。
Q.競プロ興味あるけどあまり重箱の隅をつつくようなオーダー下げコーディング(nの3乗をnの2.97乗に下げるような）はしたくないし知識ごりごりにため込まないといけないのもしんどいんだけどそのあたり実際どうなの？
すると、
「そこまで重箱の隅をつつくような問題はAtcoderにはあまりない。想定解法の次に早いような手法でも間に合う」
「確かにABCは知識を抑えている必要があるけどAGCの方が数学パズル要素が強い」
「COOH2さんだったらAGCだけ普通にやってたら橙くらいまでは行くんじゃないですか？」
というような感じの（繰り返しますが一年以上前なので一部曖昧です、あしからず）ありがたいお告げをいただいたのでやってみることにしました。
・コンテストに出だしてから青に入るまでの変遷
AGC037(19/08/17) パフォ：1124 レーティング：122
初めてのAGC。標準入出力くらいは普段使わないので調べておいて、結果A1完のみ。Cも方針は見えていたけど競プロ的な考え方に適応していませんでした。さすがに多少は競プロの練習積まないといけないかと思うとちょっと面倒になってしばらく放置。
AGC043(20/03/21) パフォ：1438 レーティング：554
やっぱり競プロが気になって再びのAGC参加。またA1完だったがやはりBも方針が見えるので精進をもうちょっとやればぐいと伸びる気もする。このころからちょっと過去問を解きだします。
4月はちょっと忙しくなったものの5月に入ってまた一日一問以上を目安に解くようになりました。
AGC044(20/05/23) パフォ：―― レーティング：554
一問も解けずNo sub撤退。特に難易度が高くレーティングシステムに悪影響を与えたか何かで、ご存じの通りここからAGC参加にレーティング下限が設定されるようになります。
この時点でARC級はほとんど開催されておらず、必然AGCに出たければABCに出てレーティング下限に入るしかなくなったのですが、私の特性として、数学SSS、アルゴリズムA、実装C みたいなとてもいびつなパラメーター割り振りです。
・本職で数学を扱うので難易度の高い問題も時間をかければ解けることがある。
・まだ練習量が足りていないので早解き用の回路は育っていない。
→ABCとの相性が最悪
というわけなんですね。
で、どうなったか。
ABC174(20/08/02) パフォ：1176 レーティング：711
ABC176(20/08/22) パフォ：1080 レーティング：781
ABC178(20/09/13) パフォ：1046 レーティング：823
始めたてなのでレーティングは伸びていますが水色入りも怪しいような状況。始めた頃よりむしろ悪化してる。しかし、緑に入ったあたりでARC再開の報を聞きそちらにチャレンジすることにします。
ARC104(20/10/03) パフォ：2016 レーティング：1121
いきなりパフォが1000くらい違う件。この頃になるとARCの過去問バチャで橙パフォが出たこともあったので期待はしていたのですがここまではっきり違いが出てくれてよかったです。
ARC105(20/10/12) パフォ：1898 レーティング：1277
引き続き好調で水色に滑り込み、翌週のAGCのレーティング制限を突破します。それまでも変動なしで出ていましたが久しぶりのRated。
AGC048(20/10/18) パフォ：1757 レーティング：1357
Dでまさかの知ってる組合せゲーム理論の問題が出て解けました。しかしドツボにはまってAを落とすという痛恨の失態を犯しBCも解けず、パフォとレーティングはさほど伸びず。Dが載っている組合せゲーム理論の教科書をTwitterで紹介したらプチバズりました。
ARC106(20/10/24) パフォ：1671 レーティング：1403
ARC107(20/10/31) パフォ：1632 レーティング：1434
AGCだけ出るという戦術を取れるようになりましたが、ARCでもある程度レーティングが稼げる感じなので引き続き出続けました。
AGC049(20/11/15) パフォ：2100 レーティング：1544
やはり長時間コンテストは性に合っているというようなBC2完。しかしAを落とすのはよくないですね。それでも自己最高パフォを出せました。
ARC108(20/11/21) パフォ：984 レーティング：1485
AB2完。終了4分後くらいにDが通りました。悲しい。100分コンテストはきつい……初の冷えも体験して気落ちします。とはいえ気分を切り替えて翌週もARCにチャレンジ。
ARC109(20/11/28) パフォ：2276 レーティング：1615
ABCD4完。Dはかなり怪しい通し方をした自負があります（場合分け24通りとかいろいろ）。いや普段から怪しいのですけど。問題の相性がよかったようでみんな解けてるのでは？と思ったけど思ったほどおらず、過去最高パフォで一気に青入りしました。120分だったし、やっぱり100分コンテストより長いコンテストの方が相性がよさそう……
・やったこと
継続は力なり？ということで5月初めから毎日1AC以上を続けていたら200日を超えました。茶diffや灰diffだけ通している日もありますが多くは緑以上です（最近忙しくて灰茶が多い）。
自力ACにはそこまでこだわっていません。プログラミングの基礎的な内容(mapとか)を知らずに問題が解けなかったようなこともあり、今は問題を解くことと解説を見て知識を蓄えることを並行するのがよいと考えています。
・目標
組合せゲーム理論がせっかく競プロでしばしば扱われる題材なので、研究者としてはもっとブームを巻き起こしたいと思っています。
joisino君の予言もちゃんと達成したいので色としては橙を目指したい。
・感想
やはり日ごろから数学の研究をしていることは大きなアドバンテージになると思います。エンジニアの方でも競プロに来ると苦労するみたいな話も聞きますがエンジニアをするよりも数学の研究をしている方が相性がいいのかもしれないと思いました。
ただ、競プロ的な考え方に慣れる必要があると思います。問題によって、数学的なアプローチと競プロ的なアプロ―チ両方あり、かつ数学的アプローチでやると危険な問題（最近なら、ARC108-Aとか）をしっかり競プロ的アプローチから解けるようになるのが大事だと感じました。
