AtCoderで黄色になりました

伝統に従って記事を書きます。

やったこと

AtCoder, CodeForces, Topcoderのコンテストに(撤退することもあるけどとりあえず)出続ける

短期間で圧倒的精進する人にはやっぱり抜かれてしまうけどこれでレートが落ちることは(赤とかにならない限り)ないかなと思います。

青序盤との差分

数え上げの苦手意識が多少軽減した

いやまだ苦手なんですが。でも、数え上げはわりと1ステップ1ステップごとに考察を詰めやすくて構築みたいに一発天才ゲーではなく素直に考察すれば解けることが多いことに気づきました。橙目指すなら数え上げかなりうまくなる必要がありそうだと思う。

典型DPに慣れた

Earsのような状態変化を記録するタイプのDPは青帯の人にとってはわりとつまるところだと思う。これに慣れたのはでかい。挿入DP, 区間DP,  O(3^n)のDP,  O(N^2)の木DP, 約数の包除原理など。

知識

これは列挙しようと思ったんですがさすがに多すぎて思い出しきれないのでやめました。比較的最近勉強したHeavy-Light Decompositionはあまりに便利なので青の人でも一度勉強してみることをおすすめします。

ゴリ押し用のデータ構造(Implicit Treap: 要素の削除や挿入ができる遅延セグ木のようなもの, や要素の削除や挿入ができる上位k個要素のsumを返すデータ構造など)をいくつか常備していますが、2, 3ヶ月に一度ぐらい役に立つ印象です。

ConvexHullTrickとかFFT, NTTなども使えるようになりました。

あと問題を解くと、こういうふうに帰着しちゃうとヤバいみたいなのがいくつか経験からわかってきて余計な考察を省けたりします。

当面の目標

コンテスト中に1時間ぐらい同じ問題を考察してやっと解けた、みたいな経験が最近少なくて(ICPCとかは実装担当なのでほぼ考察をしていないし)、長時間系のコンテストが苦手になっている気がします。黄色になっちゃうとレート上げチャンスがAGCや企業コンになりますが、前者は長時間系コンテスト(Aはすぐ解けちゃうし、たいていCやBに各1時間以上費やすことが多そう)の代表なので考えることに慣れなきゃいけないなと思います。これなにをすればいいんでしょうかね、やはり精進しかなさそう