AtCoderで青色になるまでにやった事とかをまとめる

こんにちは。6/3のAGC025で無事青色になる事ができたので、今までにやってきた事と青色になるために必要だと感じた事をまとめようと思います。
この記事に載っている内容はあくまで個人の意見なので、あくまで参考程度にお願いします。
また、私自身が青色最底辺の人間なので知識が浅く、いくつか間違っている点があるかもしれません。ご容赦ください。

この記事を読む前に (宣伝)

この記事は三ヶ月ほど前に投稿した AtCoderで水色になるまでにやった事とかをまとめる - shibh308’s diary が少しバズった事で、それに味を占めて調子に乗って執筆した物になります。
書いてある内容や構成などはほとんど上記の記事と変わらないので、まだ読んでない方はそちらも読んで頂けると嬉しいです。

自分語り

塚本@shibh308です。去年のJOIは予選落ちでした。執筆時点でのレートは1602で、今までのレート推移はこんな感じ(下画像参照)です。
f:id:shibh308:20180604004627p:plain
AtCoder以外のコンテストサイトだと、Codeforces(青:1784)とかCSAcademy(青:1764)とかもやっています。
水色になるまでの流れは以前の記事にも載せたので割愛しますが、水色になってからレート1600に乗せるまではちょっと大変でした。水色に乗せるまではレートが単調増加になっていて非常に良かったのですが、流石に水色になってからそうは行かず、何度かレートを落としてしまう事があり悲しかったです。
それでも青パフォを安定させる所まではたどり着き、25回目の参加でついに青になる事ができました。

成績について

水色になってからの私のコンテスト記録を貼っておきます。順位やパフォーマンスの参考にどうぞ。

f:id:shibh308:20180604083856p:plain

また、水色になってからのratedコンテストでの配点ごとの正答率、解けた時の平均の解答時間(その問題に対してかけた時間の平均)もまとめておきます。200以下はAGCのクソ問題を除いてすぐ解けるので除外、800以上は解けた事がないので除外しています。
コンテスト履歴から手計算しているので、いくつかガバや書き漏らしがあるかもしれません。

・300点: 9/9 平均10:36
・400点: 2/2 平均21:33
・500点: 5/5 平均33:10
・600点: 0/3 正答なし(!)
・700点: 3/6 平均45:40

青色になるために必要そうな事

私のこれまでの経験と偏見を元に、「これだけできるようになれば青色になれる!」みたいな目安と知っておくべきアルゴリズム、考察のコツについてまとめました。

コンテスト順位や問題について

順位やパフォの目安

・ARCで350〜250位辺りをだいたい維持する
・パフォ1600-1900辺りをある程度安定させる
†爆死しない†

順位とパフォについては平均がこの範囲内になっていればいい感じ、という程度だと思います。
前回の記事でもほぼ同じ事を書きましたが、爆死しない事が一番大切な気がします。レートを取り戻すのに時間がかかりますし、モチベが維持できずに悲しくなってとてもつらいので気をつけましょう。(自戒)

解けるようにすべき問題の目安

・300点以下を確実に通せるようにする
・400点問題のうち8-9割、500点問題のうち5-8割を数十分で解けるようにする

600点以降の問題は解けなくても問題ない気がしますが、1-2割解けるようになってるとパフォが取れて割と嬉しいです。
通常のARCだと1完早解きでパフォ1600に乗ることはあまりないので(もちろん回によりますが)、Dが400だったり500だったりする回はそれを確実に通せるようにして行きたいですね。

問題を解くために使った知識について

まずは、AtCoderの(unratedを含む)コンテスト中に実際に使ったアルゴリズムをまとめたいと思います。
以前の記事では必要になりそうな知識についても記述していましたが、なんか地頭の方が大切そうなのでAtCoderではアルゴリズムそのものが要求される事が少なく、考察の方に重みが置かれている(気がする)ので、この記事では実際に使った知識のみ紹介したいと思います。

コンテスト中に実際に使ったアルゴリズムや知識

・グラフの探索(BFS,DFS)
・累積和、累積xor
・Union-Find
・二分探索
・二次元でのいもす法
・エラトステネスの篩
・しゃくとり法
・二部グラフの最大マッチング(最大流問題)
ダイクストラ
・階乗と逆元の前計算による組み合わせの計算

コンテスト中に実際に使ったアルゴリズムは以上になります。もちろん、ここに登場していない物で使えると便利なアルゴリズムも沢山ありますが、こうして並べてみると実際に使ったアルゴリズムは(参加回数と比べると)そこまで多くないような気もします。

方針の立て方

緑〜水色の人向けに、特に400点以上の問題を解く時の方針について簡単に説明していきたいと思います。
(※説明の途中にいくつかの問題のネタバレを含んでいます!このようなリンクを押すと問題ページに飛ぶようになっているので、ネタバレを避けたい方は問題ページへのリンクを踏まないようにすすといいかもです。)

問題を見たらすぐにやる事

まずは問題文を流し見して、入力部分だけ適当に書いてしまいます。読む時に誤読と制約の勘違いをするととても辛いので、そこだけ気をつけてます。(それでも誤読する時はするので悲しい)
この時点で計算量のある程度の目安を考えておくと考察がいい感じに進むような気がするので、それもやっておくと良い気がします。

最初に考察をする際にやる事

とりあえずまずは愚直に書いてみて(575)、そこから計算量をどう落とすかについて考えて行きます。ゲーム系の問題構築想定解が貪欲になるような問題は愚直に書く時点で詰んでしまう事が多いので、その場合は別のアプローチを考える事にしています。

計算量の落とし方ですが、ここについては(ある程度は)パターン化ができると思っています。
区間に対する取得での累積和、状態をまとめられる場合のDP、単調性がある場合は二分探索やしゃくとり法といったように、その状態において成り立つ条件さえ分かればある程度典型なテクニックを使う事で高速に求められるような印象があります。
O(N2)をO(N)にするため累積maxを取る問題単調性を活かしてしゃくとりや二分探索が使える問題など、このようなアプローチができる問題は最近のコンテストにも多く出題されている気がします。

愚直に書く事が難しいような問題は頑張って考察をする必要があって辛いですが、頑張りましょう(はい)
サンプルや小さいケースを手で解いたり、嘘貪欲を書いたりしてみるとちょっと気づきが得られたりしていい感じです。
後は、問題文やサンプルを図や表に書き起こして法則性が降ってくるのを待つのもよいです。

考察でつまづいた時にヤケクソでやる事

考察が進まずに死にかけた時はTLE解とか嘘貪欲とかを投げてみるのも一つの手ではあると思います。フィードバックを見る事で何か気づきを得られて、それでペナルティ以上の短縮ができるなら十分得な気がします。(もちろん何も分からなかったら死亡 かなしい)
コンテスト中なら順位表を見ると難易度や実装の目安が分かったり分からなかったりするので、それも目安にはなります。(解法が降ってくる訳ではない)
どうしても思いつかなかった場合はエスパーで解法が降ってくるのを祈りましょう。僕はそうやって青になれました。

問題集

このページで例に挙げた問題と、最近のコンテストで出題された問題で(個人的に)やっておくべきだと感じた問題をいくつか貼っておきます。どれも良い問題なのでぜひ解いてみましょう。

ARC096-D Static Sushi

ABC096-D Five, Five Everywhere

codeFlyer-C 徒歩圏内

ARC098-D Xor Sum 2

AGC025-C Interval Game

ARC094-D Worst Case

ARC094-E Tozan and Gezan

AGC023-B Find Symmetries