AtCoder青色になりました【マジメ ver】
俺は今日で青色になるよ
— じーふぉーぽんたん💊 (@G4NP0N_kyopro) 2021年3月13日
少女解答中
NowSolving…
G4NP0Nさんのパナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）での成績：464位
— じーふぉーぽんたん💊 (@G4NP0N_kyopro) 2021年3月13日
パフォーマンス：1858相当
レーティング：1579→1610 (+31) :)
Highestを更新し、2 級になりました！#AtCoder #パナソニックプログラミングコンテスト（ABC195） https://t.co/N9SIrzKDVF
AtCoder青色、到達です！！！！！！！ pic.twitter.com/V7qhWtB9uA
— じーふぉーぽんたん💊 (@G4NP0N_kyopro) 2021年3月13日
先日行われたパナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）にて、AtCoder青色になりました！！
競技プログラミング界隈ではAtCoderの色が変わったときに色変ブログを書く慣習があるので、それに乗っかっていきます。AtCoder水色になったときには記事を書いていなかったので、色変記事を書くのはCodeforces青色になったときのものに引き続いて2本目ですね。
AtCoderで初めての色変記事だしお気持ちポエムとか自分語りとかして～～～～～って思ったんですが、普通にAtCoder青色を目指す参考にしようと思ってアクセスした人に自分語り読ませるのは申し訳ないので、記事を分離することにしました。この記事はマジメ verです。自分語り verは暇すぎて脳みそが溶けそうなときとかに読んでください。
青色になるまで
AtCoderを始めたのは2年前なんですが、茶色になってから1年弱ほとんど参加していませんでした。(この期間の精進量はほぼゼロです）1年ちょっと前くらいに再び参加するようになって、きちんと精進をするようになったのもこの頃からです。
余談なんですが、2年前の茶色になったときは一切のアルゴリズムの勉強をしていなくて、全探索と算数っぽい何かだけで茶色中位まで行きました。今のレベルからすると信じられないですね。
コンテストごとのレートとパフォーマンスの推移はこんな感じ。春休みをすべて捧げた結果、緑になってから2か月、回数で言えば10回くらいで水色に到達できていました。この時は完全に調子に乗っていて「ま、すぐに青にもなれるだろうし色変記事はまだいいや」とイキり散らかしていたんですが、結果的に青になるまで10か月かかりました……。
水色になってからのレート推移は、今見てみると線形に見えるものの、当時はかなり停滞感がありました。特に1300~1400は相当しんどかったですね。
ほかの青になった人を見ていると色変間際には黄パフォや橙パフォを何度もたたき出している人が多いようなんですが、自分は結局パフォ1900越えが2回しかありませんでした。よく青色になれたなあ。
競プロ環境
使用言語はC#です。Visual StudioをWindowsノートPCに入れてコーディングしています。ディスプレイにHDMI接続してデュアルディスプレイにしています。競技プログラミングはマシンパワーをそこまで必要としないのでいいですね。重い重いと言われがちなVisualStudioも、メモリ8GBで十分動いてくれます。C#を使っている理由は親だからです以前から使用していて手に馴染んでいたからですね。あとはVisualStudioのリッチな開発環境に慣れてしまったからというのもあります。
また、競プロ用にiPad miniを購入して考察ノート替わりにしています。Apple Pencilひとつで複数色のペンと消しゴムを兼ねられる、方眼紙と白紙の切り替えが自由で直線や円なども容易に描画できる、携帯性が高く場所を問わず問題の考察ができるなど、競プロとの相性は抜群です。
AtCoder青色になるまでにやったこと
AtCoderの過去問精進
定番ですね。AtCoder Problemsで見れる情報をいくつか張ってみます。
AC数は青到達者としては並かやや多いくらいだと思います。虚無埋めがけっこう占めてる割合多いので。
見てすぐに解けてしまう難易度の問題を埋める、いわゆる虚無埋めはっこう賛否が分かれるところですが、自分は音ゲーのいわゆる低難易度埋めを楽しめるタイプ（そして高難易度特攻が得意でないタイプ）なので、とくに抵抗感なく進めていました。ただ、脳死でやるだけではもったいないので、意識的に「どうやったら最もシンプルに解けるのか？」みたいなことを考えながら埋めていた気がします。
水色到達以降は「まずは水Diffを全部埋める！」というモチベーションで精進をしていました。最終的にはAGC数問を残して埋め終わるところまでいきましたが、レート最大化という点からみるとあまり効率がいい方法ではなかったと思います。
単純にレート最大化を目指すならば、流星のごとく現れた期待の新星、Rcoderさんの色変記事が本質だと思います。
seashellpink-frostywhite.hatenablog.com
ただし、精進がレートに反映されるかどうかは運も絡んでくるので、レート最大化だけを重視した精進はモチベーションの維持がなかなか難しいです。なので、〇色まで埋める、RPS△点を目指す、streakを伸ばす、そういったレートとは独立した目標を設定すると、長期的なモチベーションとして機能すると思います。
青Diffを意識して埋め始めたのはレートが1500に乗ってからくらいでしたね。それまでもちょいちょい解いてはいたんですが、解けそうな問題だけ解いたりしていたので、精進としての効果は非常に薄かったと思います。やっぱり青に上がることを意識して青Diffを解くのは非常に効果的でした。令和ABCの青Diffを全部埋めたんですが、とても学びが多かったです。
コンテストに参加する
当たり前ですが、大事です。
2020/1/18のキーエンスプログラミングコンテスト2020以降,引っ越しの準備で参加できなかった2回を除きすべてのratedコンテストに出場しています（たぶん）
Problemsでざっと見た感じだと、1問目から解けなかったAGC044を除けば、NoSub撤退もARCで1回あったのみでした。
コンテストに出ることが最も時間効率のいい精進だという話もありましたね。誰が言っていたか忘れましたが。
ちなみに、個人的には現行ルールにおける潜伏は問題ないと考えているのでARC,AGCで潜伏することは結構あったんですが、結果的にだいたい提出に至っていました。ABCの潜伏はマジで無意味なのでやめたほうがいいと思います。
Codeforcesのコンテストにも参加していました。こちらはアドホック要素が強めなので、考察力や発想力を鍛えるいい練習になったと思います。特に数列操作とグラフの問題が多め。ABCよりはARCで効果が出ると思います。ABCで青を目指すだけなら必要ないかもしれません。
バチャに参加する
みんな大好きバーチャルコンテスト。僕も大好きです。大きく分けてAtCoder Problemsを利用したAtCoderの過去問バチャとCodeforcesの過去回の2つがあります。
目的に応じて参加するバチャを選ぶのがいいと思います。バチャに片っ端から参加してしまうバチャ中毒みたいな人も多いですが……
オススメのバチャを軽く紹介しておきます。バチャの名称は適当です。
- くじかつ
TERRYさんがAtCoder Problemsで毎日21時から主催しています。難易度傾斜が程よく、ABC対策として一番効果的だと思います。
- えすえふバチャ
えすえふさんが主催している21時からのCodeforcesバチャ。こちらも参加者が比較的多く、感想戦で盛り上がっていますね。
- Moringforces
タイヨウさんが主催している朝7時半からのCodeforcesバチャ。起きる部分が最難関ですが朝からバチャに参加すると一日をいい感じに競プロ漬けにできます。これの常連メンバーはきちんとみんなレート上げてるな～って感じ。
- かいけーバチャ
異常バチャ精進の王かいけーくんが不定期にCodeforcesバチャを開催しているので目についたら並走しています。
- poyoさんバチャ
期待の新人バチャジャンキーことpoyoさんがAtCoder Problemsで不定期に開催しています。最近は23時から開催が多い？
AtCoderバチャを復習用に、Codeforcesバチャを考察力訓練に使うのがいいと思います。Codeforcesバチャは正直あんまり復習まで手が回らないことも多かったんですが、なんだかんだ効果はありました。
EDPCを解く
フォロワーの熱心な布教により解き始めました。DPはけっこう得意だと思っていたんですが、典型を忘れていたことが発覚したり、期待値DPが大の苦手であることを把握できたり、高度典型DPの概観をつかむことができたりと、非常に大きな成果がありました。
青になれた回のE問題もEDPCの応用問題でした。ありがとうEDPC。
まだ後ろ数問をACしていないので早いうちに埋めたいですね。TDPCにも手を出してみたい。
データ構造/アルゴリズムの勉強
これは人によって進め方がかなり異なると思います。茶色でセグ木やったり緑で全方位木DPやってるバケモノも中にはいますが、自分は精進を進めるうえで必要になったら用意する、くらいのノリでやっていました。蟻本とかも全然読み進めていない……。
自分は抽象化が好きなので、よく典型のデアを抽象化して遊んでいました。セグ木なんかはみんな抽象化していると思うんですが、ダブリングやLISを抽象化しているのはけっこうレアなんじゃないかと思います。抽象化をすることによってそのデアへの理解はかなり深まったので、オススメです。
自分は青コーダーとしてはデアの履修率がかなり低いはずなので、まだ自分のものにできていないものを列挙しておきます。これらができなくても青色になれる！！！（コラ）
- 遅延セグ木 一応持っていたんですがバグっていました
- 全方位木DP 1回だけEDPCで解いたけど、まだ経験値が圧倒的に足りないです
- 文字列アルゴリズム各種 Z-algorithmとかロリハとか。ABCで使わないから……
- フロー Dinicを一応持っているので重み無し最大二部マッチングは何度か解いたんですが、他はからっきしです。
- ベルマンフォード法 使う機会なくない？一応仕組みはわかってると思うけど空で書けない気がする
- Binary Index Tree セグ木でよくない？＊よくないです
- 平方分割 やらないとと思いながら一生後回しにしています
- 強連結成分分解 AGCで必要になったときに計算量酷いやつを再発明しました。
- FFT,NTT 名前だけ聞いたことがあります。
- FPS スプラトゥーンなら得意です。
開発
たぶんやらなくてもいいと思います。でも楽しいのでやりました。
CodinGame
たぶんやらなくてもいいと思います。でも面白かったのでやりましょう。
たぶんやらなくてもいいと思います。でも楽しいのでやりました。
ライバルが精進している様子を見てモチベーション上げたり、疑問点を放流したりして強い人が教えてくれたりします。いやこれやったほうがいいな。みんなTwitterをしよう！
AtCoder青色になって
AtCoder青色は、競技プログラミングを始めた際の最も大きな目標でした。
「大学在学中に青になりたい！！！」という思いをずっと持っていたので、なんとかギリギリ目標を達成できたことに安心しています。
春から社会人となりますが、これからも競技プログラミングへの情熱を絶やさずにいきたいなぁ。次の目標はAtCoder黄色です。遠く険しい道のりですが、くじけずに頑張っていきたい！
