AtCoderで赤になるまでにやったこと

AtCoderで赤タッチしたのももう1.5年も前ですが書きます。覚えていないこと・抜け・漏れなどのオンパレードですがご容赦ください。

お前は誰

kobae964 - AtCoderです。2017年11月に初めてAtCoderでredになりました。


なんで今更これ書いたの

当時は面倒だったので書きませんでした。その後人々が変色時に記事を書いていくようになり、見かけた記事は大体全部読んでいました。
微笑ましいと思ったもののAtCoderの赤でそれをやった人を見たことがなかったので、せっかくなので書こうと思いました。すでに誰か書いていたらごめんなさい。

注意事項

筆者はAGCよりもARCの方が得意なため、AGCでの立ち回りは強い人に聞いてください。

赤になるまでにやったこと

問題を解いた

2000問くらい解きました。


使った知識・メタ典型

赤タッチするなら 蟻本 + 赤の人ならほとんどが知っている知識の半分 くらいが必要になると思います。
以下では蟻本上級編以上のレベルの内容を列挙していきます。列挙の漏れは100%確実にあります。

使えた知識 (これが問われたら30分以内にわかる)
  • mod 2行列系 (うまく線形代数かなにかに落とし込む、一時期無限に出題されてた、問題例, 問題例)
  • ゲーム (grundy)
  • グラフマスターへの道 (SCC, 2-SAT, LCA)
  • マージテク
  • 文字列系 (ローリングハッシュ, suffix array, manacher)
  • 丁寧・高速な式変形
  • 代数についての知識
  • 数論系アルゴリズムについての知識
知っていたが使いこなせなかった知識 (これが問われたら1時間以上かかる)
  • 包除原理 (2^n系包除, 約数系包除, Zeta/Hadamard変換全般, ポリアの数え上げ定理)
  • 行列累乗 (遷移を行列にエンコードするのが苦手だった)
  • スライド最小値
  • 区間スケジューリング
    • 応用 (問題例) とかは難しい
  • Convex Hull Trick
  • 分割統治
  • 複雑なDP
    • 実家DP (配列をセグメント木で管理して、一点更新/区間和などに高速に対応する)
    • 累積和を取りながらDP (今のAtCoderでは結構見る)
    • 挿入DP
    • 桁DP
    • K種類の物を順番に埋めていく時にindexが最後に埋めた物以外の(K-1)個できるやつ (問題例)
    • …列挙していったらキリがないなこれ
  • 最大長方形 (stackを使うやつ)
  • マンハッタン距離は回す (問題例)
  • 小さい場合に手許でbrute forceして分析
  • Prim法 (は?)
  • 誤読して時間を溶かさない
  • 変な方針を思いついた場合に、変であることに素早く気付く
    • 変な貪欲に突っ走らない
知らなかったけど後で必要になった知識
  • 集合をクラスタに分けるO(3^n)ç³»DP (O(3^n)時間、O(2^n)空間で、dp[S] <- dp[T] * sub[S - T]みたいにするやつ)
  • 構築の手筋
    • 2ベキ
    • 必要条件を列挙して可能性を絞るテクニック
  • 必要条件を集めたらいつのまにか十分条件になってました系の考察
  • 計算量周りのテクニック
  • 木についてのテク (重心分解, HL分解)
  • MSTについての性質(マトロイド性、貪欲が効くことなど、問題例)
  • MSTのアルゴリズム (Boruvka法、Voronoi図を作る方法)
使わなかった知識
  • 枝刈り全探索
  • 幾何
  • 難しいデータ構造 (AtCoder以外では使った)
    • 遅延セグメント木
    • Sparse table
    • 平衡二分木
    • 平方分割

まとめ

赤を目指すには

  • 知識を増やす (汎用性の高い方法で覚えておくとよい)
  • なんとなくの考察 (第一感) の正確性を上げる (一発で正しい答えにたどり着ける確率を上げる)
  • 嘘解法についての嗅覚を鋭くする
  • 式変形を高速に、正確に行う
  • 知らないことでも実験して考える

とかが必要になる気がします。*1 いずれまた赤から落ちると思うのでそうなったらこれの通りにまた頑張ります。

ここまで読んでくださりありがとうございました。

赤になって得られたもの (追記 2019/7/1)

強い人と知り合いになれる確率がグッと高まる

赤になることに限定せず、強くなることによるメリットとして、いわゆる「いつもの勢」と呼ばれる、国内オンサイトコンテスト常連の人たちについての話をしない訳にはいかないでしょう。
赤になった年の翌年、入社した会社で強い人と知り合い、それがきっかけとなりいつもの勢の人々と知り合いになりました。いつもの勢の輪に入れているとは思いませんが、少なくとも観測できるようにはなったと言っていいです。彼らの競プロに対する考え方は、非常に参考になります。ストイックに精進したい人にはいい環境だと思います。

OpenCupに出場できる確率が高まる

これもコネが増えたことによる帰結です。
OpenCupについて、chokudaiさんなどが言及しているのをたまに目にする人がいるかもしれません。OpenCupというのは、ある期間日曜午後に (不定期に) 行われる、5時間チーム戦内輪コンテストです。*2 これも社にいた強い人に教えてもらい、幸運にも組んでいただける人を見つけることができました。精進したい人にはオススメです。

ARCがunratedになる

ARCみたいな面白いコンテストにunratedで出て新戦法を試すことができるのはメリットだと思います。多分tourist出しの練習をした人絶対いると思いますよ

Q. ユーザによっては一度に限り変更できる場合があるようですが、なぜ私は出来ないのでしょうか？

先日ユーザ名を一度だけ変更できる機能が実装されましたが、最大レートが2800以上のユーザはユーザ名の変更ができません。草

f:id:koba-e964:20190701021801p:plain
max rating >= 2800になると現れる文言

モチベーション維持の方法 (追記 2019/7/1)

ブランク期間の長さにペナルティをつける

自分の心の中のレート := 本来のレート - 100 / 1ヶ月 * ブランク期間 くらいにすると、ratedを避けるモチベがなくなっていいっすよ
これはAtCoder固有の事情ですが、ある程度の参加回数になると1回の大失敗で下げられるレートの上限が121 (= -800 * log_2(0.9)) になります。つまり36日ratedに出ないともう何やっても悪くなりません。無敵だな!

ポエム (ここから下は読む必要なし) (追記 2019/7/1)

私は高校時代、数学オリンピックに出ていましたが、ろくに何も精進しなくて本戦 (予選の次にある2番目のやつ) 止まりで、春合宿出場者やIMO出場者に対して羨望に近い憧れを抱いていました。そんな私が、高校時代から知ってはいたものの手を出せずにいた競技プログラミングに手を出したのが大学1年の時です。当時はTopCoder *3 がまだ盛んで、参加して緑落ちしては嘆き、黄色に昇格しては狂喜乱舞し、というのをやっていました。おそらく当時はUnionFindやbitDPすらまともに書けなかったと思います。レッドコーダーたちについては、尊敬の念をもって見ており、自分がなれるとは夢にも思っていませんでした。
転機と呼べるものがいつあったか、正確には思い出せませんが、大学3年くらいの時だと思います。演習で競プロみたいな内容のものがあり、競プロの面白さに目覚めました。そのときはyukicoderあたりを埋めまくって典型を覚えていったと思います。
本格的に取り組み始めたのは院生になってからだと思います。研究そっちのけで (は?) 競プロに打ち込み、M1の11月にオレンジになりました。そこからはより一層のめり込み、友達との食事の時間も考察に明け暮れる始末で (は?)、ratedのたびに2800以上のパフォーマンスを取っては赤パフォだと喜び、2400以下のパフォーマンスを取っては落ち込み、という繰り返しをしました。
途中からARCでパフォーマンス3200を取れるようになってきたので、このまま続けていればいずれは赤になれる、と徐々に確信できるようになりました。が、実際になれたときの喜びはひとしおでした。高校時代憧れの的でしかなかった国際科学オリンピック出場者に一歩だけ近づけたのだという思いが湧きました。

この先 (追記 2019/7/1)

誰か強くなる方法を教えてください m(_ _)m

*1:誰も「赤になる方法」みたいな記事を書きたがらないように見えるのは、こういう情報量ゼロの内容しかないからでは、と思っています。

*2:内輪なので参加するのはちょっと面倒です

*3:今は表記がTopcoderになっていますが、2012年頃はTopCoderだったと思います