Y.Y. の Y は Yellow の Y

この記事は「色変記事 Advent Calendar 2020」 4 日目の記事です．*1
3 日目は陶山大輝さんによる「(12月中に)atcoder青になります」です．
5 日目は monkukui さんによる「AtCoder で黄色になるまでにやったこと」です．

AtCoder で競技プログラミングを始めて，青色になったときに「競プロはじめました」という記事を書いてから，ちょうど 2 ヶ月が経過しました．さて，現状は…

f:id:ygussany:20201203221617j:plain

というわけで，タイトルでの宣言通り（？）めでたく黄色になることができました！！！

以下では，この 2 ヶ月間の振り返りや質問箱の話を中心に，前回書いていないことを書いてみようと思います．

振り返り編

この記事を書いている時点での AtCoder Problems の様子はこんな感じです．

f:id:ygussany:20201203223301j:plain

f:id:ygussany:20201203223318j:plain
f:id:ygussany:20201203223330j:plain

精進

9 月中に黄 diff 埋めまで終わっていたので，10 月以降はひたすら橙 diff を埋めています．黄色までは古い方から埋めていたのですが，コンテストに出るようになったこともあり，橙からは基本的に新しい方から解いています．時間をかければ解けない問題はほとんど無いという印象で，面白い問題も多くて楽しいのですが，30 分やそこらで AC できる問題はかなり少なくなってきて，平均 1 時間半ぐらいかかっているのではないかと思います．*2 それでも毎日 1 問以上 AC するのは続けられていて，今年中に橙を埋めるのを目指していますが，途中の diff 更新でだいぶ増えたのと，永遠に解けずに積まれている問題 *3 がいくつか残っているので，結構厳しいかもと感じています．

コンテスト

青になった直後の HHKB コンテストで洗礼を浴び，失敗するとレートが下がって悔しいということを実感しました．

この回は D がなかなかの鬼門で，泥沼にハマって抜け出せなくなり，結局時間内に合わせられずに苦い思いをしました．これを教訓に，以降は 1 問に固執し過ぎないことを心掛けるようになりました．*4

その後は順調に黄パフォ以上を連発してレートを上げ，AGC049 で滑り込みで黄色になりました．デビュー以来一進一退の攻防を繰り広げていて，勝手にライバル視している nok0 (@nok0_kyopro) さんと同時に黄色になれたのが印象に残っています．

f:id:ygussany:20201203191924p:plain

直後の ABC183 (unrated) では rated だったら冷えていたので危なかったのですが，それ以降は黄パフォ維持で黄色安定圏には入ったかなと思っています．まだまだ伸びしろはあると思っているので，これに満足せず，次はこの記事のタイトルが嘘になるよう橙を目指したいと思います．

質問箱編

他に何を書こうかなと思って，質問箱を開設してみたところ，たくさん質問を頂いて喜んでいます．ありがとうございます！

時間と取り組み方

どれぐらいの時間競プロをやっているかなのですが，均せば 5 時間/日ぐらいだと思っています．始めてから 200 日と少しが経過したので，トータルでは 1000 時間を超えたぐらいという認識です．chokudai さん曰く，プレイ時間が倍になると 1 色分という感覚らしいので，2000 時間ぐらいになると橙になれるのでしょうか．個人的には，もう少し早くなりたいですね．

青 diff 埋めぐらいまでは，問題を見て解法を考えて実装するまでを基本的に一連の流れとしてやっていました．黄 diff 以降は，すぐに解けない問題が増えてきたので，寝る前や家事をするときなどに問題を頭に入れておいて，解けたら後で実装する，というやり方も増えてきました．

基本的に問題を解くこと自体に愉しみを感じているので，コンテスト（バチャ）中以外はほとんどスピードを気にしていません．こんな風に長期に渡って何度かチャレンジして，最終的に解けるととても嬉しいです．

解説 AC について

これも「問題を解く（ AC する）こと自体に愉しみを感じている」に近いのですが，基本的に解説 AC 禁止縛りでプレイしています．基本的にというのは，前回の記事でも取り上げたように，犯罪 AC をした後で解説を見てしまった問題はいくらかあるためです．*5

元々アルゴリズム全般に関してはそれなりに知識がある方なので，初見のものでもある程度は再発明して何とかできるだろうというのと，すぐ解けなくても長く考えるのは苦でないので，この制約でやるのが自分に合っていると思っています．もちろん，自力で解いた後に解説等を見て学びがあれば，その方針で書き直して再度 AC するということもあります．

競プロに輸入したい分野

これは面白い質問で，あまり考えたことが無く，しばらくぼんやり考えているのですが，そのうち何か作問して輸入できたらいいなと思い始めました．回答では（組合せゲームではない方の）ゲーム理論としましたが，maspy (@maspy_stars) さんから 1 問教えていただきました．問題文に少し難有りという印象ですが，いわゆる混合戦略 Nash 均衡を求める問題で，まさしくゲーム理論の問題でした．

本業との関係

せっかくここまでハマったんだから，本業に活かせたらいいなあとはそれなりに真面目に考えています．実際そういう方を何人も知ってもいるのですが，その方々と比べると，自分はまだまだそんなレベルではないというのも確かです．ただ，アルゴリズムを実装して実験する心理的ハードルはだいぶ下がったので，プログラムを援用して何かができる日はそう遠くないと見ています．

まとめ

AtCoder で競技プログラミングを始めて，たくさん問題を解いていたら約半年で黄色になれました．「色を埋める」「 Streak を繋ぐ」というようなやり方が結構好きなので，ここまで続けられたのは AtCoder Problems のおかげです．ありがとうございます．*6 今後の目標は，今年中に橙を埋めることと，半年後ぐらいまでに橙になることです．どちらも簡単なことではないと思っていますが，対戦よろしくお願いします．

*1:2 年ぶりの連日更新です！

*2:これだけ解いていても，未だにコンテスト中に橙 diff を通せたことはありません．最も惜しかったのは ARC108-F で，考察が割とすんなりいったので 30 分近く実装時間があったはずなのに，木の直径を求める前処理部分にバグを埋め込んでしまい，気が付いたときには終了 10 分後 AC となってしまいました．

*3:ここまでを読んで Problems の状況を見れば，どの問題のことか分かるかと思います．1 問解けました！ (2020-12-06) https://twitter.com/ygussany/status/1335568463595622401 

*4:人間は一度では学習しないので，PAST-J で場合分け解法に拘って無限に時間を溶かし，82 点の上級止まりになってしまったという話もあります．

*5:犯罪 AC からの解説 AC まで禁止すると，黄 diff はおろか青 diff すら埋まっていないと思いますし，いくつかの典型テクは自力で再発明できていない気がします．

*6:僅かながら support もさせていただいております．