AtCoder橙になりました

5月4日のAGCで、ついに橙になることができました！！！

f:id:betrue12:20190505072920p:plain

初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。

ということで記事を書きます。ここまで来ると体系的に書けることがなくなってきたので、全体的にポエム成分が多めです。

解いた問題

f:id:betrue12:20190505082023p:plain

f:id:betrue12:20190505082204p:plain

AtCoder ProblemsのAC数と、AtCoder Scoresの精進グラフです。何だかんだでStreakをずっと繋いでいます。

全て埋めたのはABC全部と、ARCのE（昔のC）まで、AGCのDまで（今回のやつ解いていませんが）。最近はARC/AGCで残っている問題がかなり難しくなってきたので、JOIとか過去の企業コンとかを細々とやっています。

このゴールデンウィークは、コンテストに出る他はCodeforcesでDifficulty 2400くらいまでの問題をひたすら解いていました。こどふぉは最近レートが下がる一方なので復活していきたい。

これは黄色になる前も意識していたことですが、コンテスト中に考えて通せなかった問題をなるべく1～2日以内に通すようにしています。やっぱりコンテスト中に時間を費やして考えた経験は貴重ですし、その記憶が活きているうちに解ききってしまうと印象に残りやすくて効果的だと思います。

パフォーマンス推移

f:id:betrue12:20190505043918p:plain

黄色になった以降のパフォーマンスです。冷えている回もありますが、橙以上のパフォーマンスがかなりの頻度で出せるようになってきました。

たまたま最近の問題との相性が良かったという面は少なからずあります。ただ問題をたくさん解いた経験から、800点以下には（解けるかどうかは別として）気持ちで負けることはなくなりましたし、得意な問題はかなり速く、そうでない問題もコンテスト中にはACできることが多くなりました。

全般的に解ける問題の範囲が広がった、得意な問題をストレートに考察・実装して速く通せるようになった、問題が複数残っているときに自分が得意な問題を選んで取り組めるようになった、あたりが最近実感していることです。

今のところ明確に得意分野だと認識しているのは数え上げで、木の問題もわりと解ける率が高いです（木でないグラフは苦手…）。最近出た多項式の問題とかは苦手系だったり、いくつか苦手分野もありますがまあまあ平均的なタイプかなと思っています。

データ構造・アルゴリズム

私はライブラリに関しては「問題で見かけたら作る」タイプなので、あまり多く持ってはいないです。それでも黄色になりたての頃と比べるとまあまあ増えました。

高度なものは、AtCoderのratedコンテストに限って言えば必要なものはかなり少ないと思います。青上位→黄色くらいのタイミングで揃えておいたほうがいいかな？と思う代表的なものを何個か列挙しておきます。

セグメント木の抽象化、遅延評価セグメント木
- 最初は蟻本ベースで「minとmaxは抽象化してないセグメント木で、sumはBITで」から始めるのが良いと思いますが、色々な演算を乗せる問題を解くようになったら頑張って抽象化しましょう。
- 遅延評価できるものもあると便利です。遅延評価＋抽象化までできたら理想ですが、私はこれを理解するのにかなりの時間を要しました…
平衡二分探索木
- とりあえず1個あると便利。色々種類があるので好きなものを選びましょう。私は実装が楽なTreapをずっと使っています。
- 個人的につまずきポイントだったのが、「集合」を管理するものと「列」を管理するものがあって微妙に実装や使い方が違うということ。前者を平衡二分探索木、後者を平衡二分木と呼んでいることもあるように思います。
フロー（最大フロー・最小カット、最小費用流）
- ソラで書くとけっこう大変なので用意しておくと良いです。Dinic法が良いらしいですが私は最近書きました。
- フローの問題は結構独特だと思います。入力制約がやけに小さかったり、問題で課せられる条件が複雑に関係し合っていたり…「フローに帰着させることができればあとはライブラリに突っ込むだけ」なんですが、帰着のさせ方にも慣れが要ると感じています。
強連結成分分解、二重辺連結成分分解
- 閉路を潰すことで、それぞれ有向グラフをDAGに・無向グラフを木に変換するアルゴリズムです。DAGや木は扱いやすいことが多く、グラフをこれらに変換して考えられないかという視点は大事になると思います。
文字列アルゴリズム、データ構造
- Z-Algorithm、Manacher、ローリングハッシュ、Trieなど。文字列アルゴリズムといいつつ数列についても使うことが多いので、両方に対応できるライブラリだと良いと思います。
- Suffix ArrayやAho-Corasick法など、まだ使ったことがないものもたくさんあります。習得していきたいですね。

テクニック、思考パターン

これは文章化するのがとても難しい内容なんですが、AtCoderのレート上昇に一番効くのはやっぱりここだと思います。

二分探索に持ち込む、操作列やゲームを後ろから考える、クリティカルな特徴量を見つけ出す、差分更新で計算量を削減する、余事象や包除で数えやすくする、必要条件を洗い出して十分性を検証する…こういったテクニックの引き出しはけっこう充実してきたなと思います。そしてそれをどうやって増やすのかというと、やっぱり問題を解きまくるしか無いのかなあと。

高い得点の問題で要求される考察や閃きをゼロから自力で思いつくのはやっぱり難しくて、「似たことをやったことがある」「何となく見覚えがある」という過去の問題の記憶が大きな助けになることが多いです。実際にコンテスト中に過去の問題を思い出して解説を読みに行く、ということもたまにしています。

ただ人間はどうしても忘れるものなので、記憶に定着させる方法や思い出す方法が必要だなと感じます。ブログを書いたりAC記録を付けるのは良い方法だと思います。本当は解いた後時間が経った問題を解き直すのが一番良いんでしょうけど、どうしても新しい問題を解くほうを優先させてしまうので難しいです…

モチベーション維持

ここはレート帯に関係なく多くの人が悩むところなんじゃないかと思います。時間を使わないと実力とレートは伸びませんし、競プロに時間を使おうという気持ちになるためにはモチベーションが必要です。そしてモチベーションを上げるにはレートが上がることが必要で…と循環します。

私のモチベーション維持に関して、黄色になって以降特に大きかったなと思ったのは「オンサイトコンテストの存在」と「ライバルの存在」です。

昨年度の冬はDDCCや日経コンテストなど大規模なオンサイトコンテストが多く、そこでたくさんの人達と会うことができました。普段はコンテストもオンラインでやっていますし交流もTwitterがメインなので、実際に会って話すのはとても楽しかったですし、オンサイトに行くために実力を上げて良い順位を取ろうという気持ちになりました。あの頃の精進は今かなり効いていると思います。

あとはライバルの存在です。レート帯が近い人はだいたいライバルなんですが、特にAtCoderを始めた時期も黄色になった時期も近くて実力も伯仲しているメンバーのレートや順位はコンテストのたびに意識しています。負けたくないという気持ちは大きなモチベーション源になっています。いつもありがとうございます。

競プロは他の人との実力差が数値として可視化されてしまいますし、上を見るとキリがないです。正直、「強い」人の発言を見て自分が否定されているように感じたり、自信を失うという機会もとても多いです。実力が近くて勝ったり負けたりする位の人とライバル関係を結び、ともに実力を上げていくのが理想的だと思っています。

私個人としては「長期間伸び悩む」という経験がまだないですが、次は赤なので当分は無理ですし、橙は維持するだけで大変だろうと思っています。たぶんまた黄色に落ちる経験もするでしょう。ここからモチベーションを維持して着実に実力を伸ばしていくことが大事ですね。