AtCoderで水色から青色になるまでの日記

8月23日のAtCoder Beginner Contest 177で、念願の青コーダーになることができました。

私の今回の色変記事は、ただの日記です。

水色から青色になるまでにどういう精進をしてきたのか、何を学んだのかを振り返り、この節目に一度まとめておきたいと思い、ただただ自分のために本記事を書きました。前回の色変記事の執筆目的とは180度異なり、他の競プロerさんに役立ててもらおうという思いでは書いていません。そのような色変記事を期待して読み始めた方には申し訳ございません。

ただ、私自身青色になれた今、青色になるために最も大切なことは、知識を増やすことではなく、水色までに身につけたことの精度・スピードをあげることだと感じています。青色になるために必要なアルゴリズムや精進のTipsが知りたいという方で、私の前回の色変記事を未読の方は、ぜひそちらを読んでいただきたいです。

また自己紹介につきましてはこの記事をお読みください。

今回の色変記事を書くにあたり、水色になったとき(2020/5/3)から青色になる(2020/8/29)までの自分自身のツイートをすべて振り返りました。 一競プロerが水色から青色になるまでの競プロ関連の出来事をもれなく書いたので、興味を持っていただける方は以下本編へどうぞ。

各種精進データ

f:id:Rorent:20200902202754p:plain f:id:Rorent:20200902202814p:plain

f:id:Rorent:20200902202915p:plain

f:id:Rorent:20200902202832p:plain:h190 f:id:Rorent:20200902203132p:plain:h190

日記

5月

上旬

  • 5月3日にAtCoder水色になりました。
    この色変を期に、ブログというものを人生初めて書きました。稚拙な文章ながら頑張って書いたら、たくさんの方から反応をいただけて、競プロコミュニティの幅がぐっと広がったように思います。
  • Markov Algorithm Onlineにのめり込みそうになりましたが、Test Contestで自身の適性の無さを自覚し引退しました。

  • 精進はあさかつ・よるかつが主軸でした。
    わからなかった問題については解説ACも厭わず、すべての問題を通すようにしていました。

学習内容

  • multisetの使い方

中旬

  • セグ木と運命の出会いを果たしました。再帰で書いたらえびちゃんに絡まれました。
    これを期にフォローしていただけて、以降たくさんのことをえびちゃんから教わりました。

  • Twitterで流れてきたDDCC2020の動画を見て、オンサイトへの参加を夢見るようになりました。 (一応)新卒枠なので、オンサイトが開かれると大変嬉しいのですが、今年度はあまり期待しないほうがいいかもなという気持ちもあります。

  • 大学から課せられた膨大な量のレポートに苦しめられつつも、それ以外の時間は夢中で競プロばかりしていました。レポートはどれも、単位がくるであろう最低限クオリティで次々と生成しました。

学習内容

  • 再帰セグ木、非再帰セグ木
  • ダブリングとその抽象化

下旬

  • 第3回アルゴリズム実技検定(PAST)を受けたら、70点中級でした。同レート帯のライバルの多くは上級を獲得しており、屈辱を味わいました。必ず第4回でのリベンジを果たします。

  • Codeforcesで初めて紫になりました。(この後3回ほど反復横跳びをしたのは内緒です。)

  • AtCoderで青精進(RPS 160000)を達成しました。

学習内容

  • セグ木の抽象化
  • セグ木上の二分探索(再帰
  • Fenwick Tree、二次元Fenwick Tree、Fenwick Tree上の二分探索
  • パスカルの三角形上の矩形和の性質
  • グラフの頂点倍加テクニック
  • Z-algorithm

6月

上旬

  • VSCode教からEmacs教に改宗し、左手小指を痛めました。
    Emacsキーバインドに慣れるまで、コーディングが一時的にとても遅くなりました。

  • よるかつがなくなったこともあり、あまり朝夜のバチャに参戦しなくなりました。

  • Rubikunさんの色変記事に感化されて、自分より2つ下の色の問題から全て埋めていこうと決心し、すぐに茶・緑diffを埋めました。問題を解くことに脳のリソースを奪われずに済むので、Emacsの練習にもちょうどよかったです。

  • AOJ Course埋めにハマりました。学んだデータ構造/アルゴリズム知識をそのまま問われる、教科書の例題のような問題ばかりが並んでいます。

学習内容

中旬

  • 新型コロナウイルスの感染状況が落ち着き、大学の実習が再開となりました。

  • Emacsキーバインドが手に染み付いてきて、以前よりもコーディングのスピードが明らかに上がりました。 左手小指の筋力がついてきました。

  • 今までに勉強した知識を用いる問題を解くことよりも、AOJ Courseを埋めるべく、新しくデータ構造/アルゴリズムを学ぶことのほうが楽しくなってきました。

学習内容

下旬

  • AtCoderの成績が振るわなくなりました。
    この間に、ライバル視している人たちにぐんぐん抜かされてしまいました。

  • Codeforcesも青色に落ちてしまいました。
    水色から青色になるまででいえば、この頃が一番辛い時期であったように思います。

  • 同学の競プロerとICPCのチームを組みました。(最近公式からアナウンスがありましたが、当然のように平日開催されるのですね。果たして実習を休むことができるのか不安になってきました……。今度学務に掛け合ってきます。)

学習内容

  • 行列累乗
  • 形式的べき級数の基礎
  • 包除原理

7月

上旬

  • 実習が本格化してきて、コンテストの成績が振るわない中、思うように競プロに時間を割くことができず苦しかったです。

  • 最低限の精進量は確保しようと、くじかつ(Normal) を解説ACしてでも最後まで通すことをノルマとしていました。

  • 通学電車の中でWavelet Matrixの勉強をし、その魔法のような仕組みに魅せられました。

学習内容

  • Wavelet Matrixの仕組み

中旬

  • この頃からくじかつをサボり気味になりました。くじかつが有用でないと判断したという訳ではなく、精進として他にやりたいことが増えた、という理由からです。

  • ライバルの真似をして、令和ABC-EをGolf以外すべて埋めました。回ごとの難易度差がとても激しかったです。

  • DPに対する苦手意識を克服しようと、EDPC埋めを始めました。

  • 実習が終わり、夏休みになりました。この夏は競プロに捧げることを誓いました。(就職活動さん……。)

学習内容

  • 典型bitDPのパターンを整理
  • Convex Hull Trick
  • Sparse Table

下旬

  • 水diffをすべて埋めました。「埋める」という精進法の特徴として、どうしても自分の苦手とする問題が残りがちなので、終盤はかなりハードでした。

  • 区間に辺を張るテクニックについての記事を書きました。今まで書いた記事の中で一番多くの方に読んでいただき大変嬉しかったです。
    その後、このテクニックの概要を紹介しているブログ記事や、このテクニックが使えるyukicoderの問題解説などに、実装の例としてリンクを貼っていただけました。

  • EDPC埋めを3問(T, W, X)残して終了しました。残り3問は放置してしまっているので、いつかもう一度向き合わねばと思っています。

学習内容

  • 区間に辺を張るテクニック
  • 配列サイズ2nのセグ木が動く仕組み
  • 3nの全探索
  • Li-Chao tree(線分対応、非再帰、2n)の自前実装
  • 2種のトポロジカルソート(Kahn, Tarjan)の違いについて
  • Heavy-Light Decomposition

8月

上旬

  • Educational Codeforcesバチャを精進の主軸にしようとしましたが、復習キューの消化に思ったより時間がかかりすぎてしまい、休止しました。

  • ABCで、以前勉強したWavelet Matrixで殴れる典型問が出題されたにも関わらず、コンテスト中にググって出てきた別解法で通すということをしてしまいました。
    既に勉強したデータ構造の典型問を自力で解けない自分に悲しくなり、写経で済ませていたWavelet Matrixの自前実装を夏休み中にすることを決意しました。

  • いつも意識している同レート帯のライバルがこの頃からAtCoder青になり始めて、より強く青色に憧れを抱くようになりました。

  • JOI埋めを始め、まずは難易度1〜5までを埋めました。典型DPの再確認をすることができたように思います。

学習内容

  • 平面走査
  • Mo's Algorithm
  • 基数乱数、法 2^{61} - 1 のRolling Hash
  • modintライブラリの書き直し
  • ガウスの消去法の実装

中旬

  • Codeforces Round #664 (Div. 2)で日本人1位、全体10位を獲得しました。

  • JOI難易度6埋めを終えました。このあたりからなかなか手応えのある問題が増えてきましたが、何とかすべて自力ACで埋めることができました。

  • Codeforcesで薄橙になりました。はっきり言って上ブレでしかない思うのですが、それでも自分の名前が暖色って嬉しいものですね。

  • 8月16日から8月19日まで、他のことをほぼ何もせずにひたすらWavelet Matrixの勉強と実装をしました。 実装し終わってverifyできたときの喜びは、コンテストでいい成績を残したときの喜びとはまた質の違う、他の何物にも代え難いものでした。

学習内容

  • 全方位木DPの抽象化
  • Zobrist Hash
  • FFT
  • RollbackできるDSU
  • Offline Dynamic Connectivity
  • Manacher
  • Wavelet Matrixの自前実装
  • 構築 O(N) 、クエリ O(1) のRMQ

下旬

  • JOIの難易度7埋めをひたすら進めました。
    学習効率を最大限に高めたいなら解説ACはそれほど厭わないほうがよい、というのが持論なのですが、JOI埋めに関してはAtCoder過去問より問題数が限られているのと、一問たりとも例外なく大変学びの多い問題ばかりであるので、解説ACをしてしまうのがどうも悔しく、何とか自力で解きたいという思いで考え続けました。考察1周目を済ませた段階では16/36しかACできませんでしたが、解けなかった問題について何周も考察を繰り返していくうちに、32/36まで自力ACすることができました。

  • 8月29日、ついにAtCoder青色を達成できました。
    TLの皆さんからたくさんの祝福をいただき、とても嬉しかったです。また、何とか夏休みの終わりまでに目標を達成することができて、清々しい気持ちでいっぱいです。

学習内容

  • セグ木上の二分探索(非再帰

心がけていること

考察パートと実装パートを切り分ける

これは前回の色変記事にも書いたのですが、再掲です。それだけ重要なことだと考えています。
私がコンテスト中に意識していることとしては、とにかくこれに尽きます。

「焦って曖昧な考察のままコードを書き始めてしまい、実装し終わった後にその解法の欠陥に気付き、結局すべて消す羽目に……。」なんて経験はありませんか?
実装前に考察を詰めておくようにすれば、誤ったコードを無駄に実装してしまう確率は減らせますし、コーナーケースへの注意力も高まります。また、頭を悩ませながら実装するのと、十分な考察の基に実装するのでは、スピードが段違いです。

時々やることを変えてみる、または少し距離を置く

同じことばかりしていれば、誰しも飽きるものです。そんなときは一度、やることを変えてみるとよいです。私は、問題解きたい(今までに学んだデータ構造/アルゴリズムの演習を積みたい)期と新しいデ/アを学びたい期が周期的に訪れるので、その欲求のままに精進をしています。日記の学習内容欄の量を見ると波がわかりやすいかと思います。

競プロをしばらくやらないのも、決して悪いことではありません。といいながら、何となく罪悪感を抱いてしまうのはとっても共感できるのですが……。私も、競プロの対義語であるところの人生が忙しくなってきたときは、少しの間競プロから離れて、どう両立させていくかを毎回模索しています。経験上、しばらく離れてから再開すると、また純粋に競プロを楽しいと思えるようになります。

今後について

日記にも書いた通り、この夏を競プロに捧げて何とか青色まで来ることができました。
しかし今後は大学の実習も再開し、なかなか思うように競プロに時間を割けない日が続きます。今までライバルだと思っていた人たちともぐんぐん差をつけられてしまい、悲しくなることもあるかもしれませんが、他人との比較に囚われすぎることなく、これからも私なりの精進の軸をぶらさずに、可能な範囲でコツコツと取り組んでいきたいと思います。

今後学びたいことリスト

  • 遅延セグ木を自前実装
  • Segment tree beatsの勉強
  • 剰余環の勉強
  • DPのオフライン化の勉強
  • 線形代数の勉強
  • マトロイドの勉強
  • フローの勉強

美しいデータ構造/アルゴリズムが大好物なので、推しのデ/アがあるよという方はぜひ教えて下さい! 私の推しは、セグ木とWavelet Matrixです。未履修の方はぜひ学んでみてください。

ここまでお読みいただき、ありがとうございました。
最後に私のポリシーをペタリとしておきます。私が緑だったころのツイートです。
Twitterで交流のある競プロerのみなさん、これからもぜひお互いに切磋琢磨していきましょうね。