AtCoder黄色になりました
昨日のARCで、黄色になることができました！
パフォーマンス推移
ratedのみ載せています。青になったときと同じく、+150くらい上がって一気に届いた感じです。
このARC102は300-700-700の3完です。700を2問解ければこのパフォーマンスが出る、というのは希望が持てるのではないでしょうか。今までは、1000点くらいの問題を解かないと届かないイメージだったので…
上がってしまったからにはこれを維持しなければ…というプレッシャーがありますね。まあでも青からも1回落ちていますし、落ちてもまた上がればよいので、気楽にいきます。
やったこと
問題を解いた
AC数です。この中で個人的に重要だと思うのがARC-E（上の画像だとC）とAGC-Cで、黄色に届くためには
- ARC-Eをそこそこの頻度で解く
- AGC-Cを安定して解く
- （ARC-DやAGC-Bを落とさない）
のどちらか、できれば両方が必要だと感じています。ただこれは配点にもよりますし、特にARC-Dが700点とかの異常難しい回は実質ARC-Eと同じ扱いです。
ただやっぱりARC-Eは難しくて、ARC-Dをほぼ埋め終わったくらいのレベルで挑むと返り討ちにあいます。まずは解けそうな問題から埋めていって（昔の問題とか楽なのもあるのでオススメです）、その後は
- 解説ACをしていく
- ARC/AGC以外の、企業コンを埋めていく
- 問題を求めて他サイトに行く
あたりから選ぶのがいいかなと思います。
企業コンはけっこうオススメで、配点の割に難しい問題もありますが（400点で二部グラフとか…）、ARC/AGCとは少し違う知識が必要になります。いわゆる「ライブラリで殴れる」ような問題も多いので、埋めていくとちょっと高度なライブラリも充実していくんじゃないかと思います。
あとはまあ「知らないと思いつかない」ような解法がいっぱいあるので、解説ACも良いと思います。というか、解説読んでも分かりません。解説を読み込んで理解し、苦労してちゃんと通せば、類題やそれより少し易しめの問題が本番で出た時に解ける見込みが出てきます。
私は現時点で解説を読んだまま放置している問題がけっこうあるので、ちゃんと通していかないと。
Codeforcesを始めた
これは好みだと思います。私は単純にコンテストの場数が増えたので良かったなと思います。問題の傾向も少し違いますし。
海外サイトなので、英語を読めるかどうかでかなり効果が分かれるかなとは思います。競プロ以前に英語でつまづくと学習効率が下がってしまいますが…「ついでに英語の訓練を」という意識ならそれでもアリです。
AtCoderはコンテスト中に正解/不正解の確定結果が知らされる「フルフィードバック」方式ですが、Codeforcesは提出直後には一部のテストしか実行されず、他参加者から不正解ケースを指摘される「hack」やコンテスト終了後に改めて全てのテストが実行される「システムテスト」があります。サンプルもAtCoderに比べると不親切な傾向があるので、自力でコーナーケースを疑ったり、危なそうなテストケースを作って実行してみる必要があります。この能力は、方式の違うAtCoderでも損にはならないはずです。
C++を始めた
青になるまではRubyだけで戦ってきましたが、ARC-EあたりからRubyでは想定解でも通らない問題が出てきます。実質的に出題数が減るのと同じことなので、なかなかキツいです。
最近はPythonで競プロをやっている人も多いので、いずれ同じようにこの壁に当たると思います。このような時の選択肢は、
- 今の言語を使い続ける。
- 今の言語と高速な言語を併用する。
- 高速な言語に完全移行する。
になります（それはそう）
1は率直に言ってかなりストレスがあると思います。解法が分かっているのに通せない、これは私にとっては苦痛でした。当然、実力よりもレートの伸びは悪くなります。それを受け入れられるかどうか、だと思います。
2は今の私が取っている方法です。ちょっと面倒なので「慣れ」が必要だとは思います。ライブラリを2言語用意したり、コード提出欄の言語選択に気を遣ったり。まずは過去問から練習していくといいでしょう。今の言語に愛着があって使い続けたい人向け。
3は完全移行するまでが大変ですが、それ以降を考えると一番楽だと思います。新しい言語の経験を一番多く積めるのもこの選択肢です。
やはり強い人からは直接的または間接的に「速い言語を使うべき」という話がちらほら出て、少し肩身は狭いです。でも個人的にはスクリプト言語を使っている人は勝手に応援していて、青になるまではそのままでいいんじゃないかなとは思っています。それ以降、ぼちぼちどうするかを考え始めてもいいと思います。
用意したライブラリ
前回との差分でめぼしいものを挙げます。
- グラフ
- 最大フロー（最小カット、二部マッチングもここに含まれます）
- 強連結成分分解、二重辺連結成分分解
- データ構造
- 重み付きUnion-Find、部分永続Union-Find
- 文字列
- Z-Algorithm（過去問で使ったのでそのまま保存）
意外と増えてない…？青になる前に用意しすぎたかもしれません。
多分セグメント木の派生とか、文字列まわりのアルゴリズムで足りてないものがあるので、使う問題に出会ったら順次作っていきます。
データ構造だとセグメント木やBIT、アルゴリズムだと最小全域木（クラスカル法）やLCAあたりは青までには使わなかったかもしれないので、作っていない場合は是非用意しておくと良いと思います。
知識や考え方については挙げていくとキリがないので…何か別の機会があれば書いてみたいなと思います。
さいごに
色が変わったというのも分かりやすい指標ではあるのですが、やはり問題を解けることが楽しいです。今まで手も足も出なかった問題に少しずつ太刀打ちできるようになっている、という実感があります。この調子でどこまで行けるか…自分の力で届くところまで行ってみたいです。
引き続きブログも続けていきます。私のブログを読んで理解して通せた、という声が励みになっています。これからもよろしくお願いします。
