Growth Record of Lettuce Farm

競プロの記録・解説をします

AtCoder 水色になりました

色変記事 AtCoder

先日の エイシング プログラミング コンテスト 2020 で、AtCoder水色になりました！！！！！！！！！！！！！！！！！！！！！！

自分にとって水色は通過点だと思っていたのでぱぱっと水色になって上に行こうと思っていたら思いの外レートが伸び悩んでしまい、一時期非常に苦しかったのですが、無事水色になれました。マイルストーンとして今までに競プロでやったことをまとめようと思います。

ところで、先日って7月11日？もう1か月経ったらしいですよ？ぼーっとしてたらこの記事を下書きに保存したまま1か月経ったらしいです。怠惰ですね。この記事をお蔵入りさせるわけにもいかないので、1か月遅刻してしまいましたが公開します。

競プロ成長記録

f:id:fairy_lettuce:20200712120225p:plain f:id:fairy_lettuce:20200712120519p:plain 水色になるまでのRatedコンテストの履歴です。途中でなぜか真っ平らな場所がありますね(すっとぼけ)

競プロを始めてから一時休止まで

競プロは去年2019年に大学に入学するとほぼ同時に存在を知り、なんとなくで始めました。プログラミング経験はちょっとだけあったし数学も好きなので、水色はすぐなれるかな～と高を括っていました(当時は今よりも水色に必要な実力が少し低かったので、センスがある人なら水は無精進でもなれるという感じでした。今もそうだと思いますが一年前よりハードルは高いと思います)。
しかし、始めてから2か月、7回目の参加で緑になり、そこから2か月ずっと足踏みをしていて、水色って案外遠いのかなと感じました。自分としては実力は水色程度はあるだろうと思っていたのですが、あまりにもABCで下振れを引くことが多かったので、これは下振れなんかじゃなくて実力不足だとは勘付きました。
実力不足だとは自覚しながらも、休止する直前の10月9日時点でAC数139(精進レートにして灰)しかありませんでした。コンテストで出た問題だけ解くというようなスタイルでした。競プロ上達は精進があってこそと口を揃えて上位の人は言いますが、私は競プロに限らず課題を溜め込んで試験前日に一夜漬けするタイプでした。まずいな、精進しなきゃなと思う中で、やがて競プロからは少しずつフェードアウトしていきます。
競プロからフェードアウトした理由は実は競プロで伸び悩んだからではなく、大学の講義などで忙殺されて精神状態が悪くなってしまったからです。課題を溜め込む悪い癖が出てしまいました。本当に毎日毎日ダウナーな気分で何にも手が付きませんでした。些細なことをするにも多大なMPを消費する状態で、競プロにも当然手を付けられず、そのまま半年も過ぎてしまいました。コンテストもその期間ずっと出られていません。うにゅーん。

休止から復帰以降

競プロ休止期も半年が過ぎ、新年度が始まりました。半年ずっと競プロからは離れていたものの、当然私以外の人はその間に実力を伸ばしています。知り合いの水色の人は青になっていて、青の人は黄色になっていて、いつの間にかこんなに強くなっていたのか……とちょっと焦りを感じ始めました。春休みの実家帰省から戻り自由になったし、またコロナ禍で外出することがなく暇だと思っていたし、その時はメンタルがある程度回復していたし、久々に競プロ復帰しようと思い立ちました。
復帰直後はあまり上手く行かなかったものの、少し経つと休止直前と同じくらいには出来るまで調子が戻りました。しかし、その後はパフォーマンスが反復横とびを繰り返しながら結局緑で足踏みを再開しました。明らかに精進量が足りないのが伸び悩む原因だと感じ、Streakを繋ぎつつ精進量を増やす、またバチャをたくさんすることを心がけるようにしました。結果、精進グラフの傾きは以前の約5倍にもなっています。

f:id:fairy_lettuce:20200817232112p:plain
なお、この画像だけ入水直後ではなく入水後1か月時点のグラフです(なぜそうなってるかというと、下書きは入水直後に書いていたもののここだけ後から書き足したからです)。

精進量を増やしたことがレートに反映されるのは少し時間がかかりました。先程の精進グラフを見ても分かる通り、5月半ばから精進量を増やしたけれど6月末まではレートが伸び悩んでいますが、7月に入ってから一気に伸びています。精進が実力に反映されるのはいつかわからないというのは競プロ界隈ではよく聞く話ですが、それを強く実感しました(正直、1か月で反映されたのはむしろ早いほうではとすら思います)。
7月に入ってレートが伸びるようになる頃は、こどふぉバチャや令和ABCバチャをたくさんしていました。そのバチャの結果がすこぶる良くて(2連続黄パフォ相当の成績を出したバチャもあるほど)、今までの停滞からようやく解放されたと感じました。それまではABC(本番・バチャ)では良くて水パフォ後半、水パフォが出たならまだ良い方で、緑パフォを取ることも多かったです。しかしそれ以降は青パフォがたくさん出るようになり、調子が悪く下振れだという実感があるときでも水パフォは確実に出るようになりました。そしてようやく、7月11日のコンテストで水色になることが出来ました。
水色は自分の中ではゴールではなく、あくまで通過点だと考えていただけに、水色に到達するのにこんなに時間がかかってしまったことにはつらさを感じたことはありましたが、ようやく達成できたことに少し安堵を感じています。しかし、ここで安心することなく精進を続けていき、青色、さらにはその先へ進んでいきたいです。

精進記録

2020年07月12日、入水直後の記録です。2か月でAC Countを3倍くらいに伸ばしました。

f:id:fairy_lettuce:20200712192455p:plain

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

蟻本などを参考にしながら、自分が使えるアルゴリズムやデータ構造などを列挙していきます。自分がライブラリとして現時点で持っているものには*を付けています。ちなみに入水直後に書いたので、今はちょっとだけ出来る内容が増えていますが、それはまたそのうち。

何の迷いもなく書ける・使える

  • 全探索
  • 貪欲
  • DP
  • PriorityQueue
  • (Multi)Set, (Multi)Map
    • 自作したやつ(RBST)が定数倍重すぎてやってられなくなったので近々AVL木か何かで書き直します
  • DFS / BFS
  • Dijkstra法
  • GCD / LCM *
  • 素数列挙
  • 素数判定 / 約数列挙
    • O(log3 n)の素数判定をライブラリ化したい
  • 繰り返し二乗法
  • 行列累乗 *
    • 何故かyukicoderで典型化している……
  • 二分探索(Lower/UpperBound) *
  • しゃくとり法・imos法
  • XORの性質(知らないこともあるけど……)
  • ModInt (四則演算・逆元・累乗) *
    • 一応任意Modで作っています

調べたら使える・ちょっと苦労するけど書ける程度

  • Deque
    • 流石にこれライブラリ持ってないのまずくない？
  • Bellman-Ford法(知識としては知ってるけど、書いたことがありません……)
  • Kruskal法(書いたことがありません……)
  • Warshall-Floyd法(書いたことがありません……)
    • グラフ弱すぎない？
  • Union-Find(メイン言語をC#にして以来書いてない……)
  • ダブリング
  • 半分全列挙
  • 座圧
    • 正確には、座圧が出来ないというよりは座圧が絡む問題が苦手、な気がしなくもない
  • Segment Tree / Binary Indexed Tree
    • いい加減にライブラリ化したい
  • 平方分割
  • 桁DP
    • 桁DPの変遷難しくない？
  • LCA
  • Rolling Hash
  • KMP法
    • この前調べて感動した

なんもわからん

  • きたまさ法
    • 面白そう、勉強したい
  • フロー全般
    • 時間かけないと理解できなさそう
  • FFT
    • こんなものなんだっていう理解はあるけど、書いたことない
  • 包除原理
    • ABC172-Eが解けず、包除原理自体は理解してるけど競プロに応用する段階まで行ってないと発覚
  • Nim / Grundy数
  • 強連結成分分解
  • Trie木
  • Aho-Corasick法
  • Suffix Array

伸び悩んでいる人へ

  • メンタル最優先
    メンタルが死んで日常生活に支障が出るようになると元も子もありません。私は競プロが原因でメンタルを病むようになったわけではなく大学無理しんどいになったのですが、どちらにせよ辛いことは放っておかないようにしましょう。ちなみに大学無理しんどいは現在進行系で続いています。進振り詰んだ
  • 上を見すぎない
    強い人、精進せずに水とか青とか行ってますよね。私は下手にプライドが高く無精進水コーダーになりたいと思っていましたがどうやらそんなに強くはなかったみたいです。無精進である程度まで強くなって精進するようになると鬼のように伸びるタイプの人は実際にいますし、自分もそのようになりたいと思う人もいるかもしれませんが、なれそうにないときは潔く諦めて精進しましょう。というか典型が身についていないのに無精進で強くなろうとするほうが邪道です。典型を車輪の再発明する天才ならまだしも、コンテスト中知らずに解けないのなら素直に典型を勉強した方が絶対に伸びます。(言葉がちょっと強くなりましたがこれは過去の自分に対する戒めでもあります)
  • 人の努力・精進の仕方には向き不向きがある
    精進をする人のTwitterやブログを見るといろいろな精進方法をしているのが分かると思います。バチャだったり、過去問をとにかく解きまくったり、短期間でAPG4bや蟻本のような教科書を読み込んだり、とにかくたくさんありますが、どれが自分に合ってるかは自分で探すしかないと思っています。私は大学受験の時数学の過去問を本番と近い環境で解く練習を15年分やっていたように、競プロでもバチャをするのが一番モチベを保ちやすくたくさん精進できると気付いたので、今はバチャメインで精進をしています。逆に問題集をたくさん解くみたいなのは昔から苦手で、競プロでもAtCoder Problemsから過去問を適当にピックして時間無制限で解くことをしてもあまり集中できません(することはあるけど)。バチャは数時間を取るのが難しかったり逆に集中できないので問題集のように解きたいという人もいると思います。結局人それぞれです。精進を重ねながら色々やってみて、自分に合った精進方法を探してみてください。

水色なりたてコーダーの分際で、と言われてしまえばおしまいですが、参考になれば幸いです。

おわりに

いかがでしたか？(定型文)
復帰後も言うほどたくさん精進できているわけではありませんし、入水から1か月が経って再び調子が崩れてきていますが、再び調子を取り戻せるようにたくさんバチャして問題を解きたいです。
2か月ほど前chokudaiさんが雑談配信で「半年以内に水色に行けない人は最終的に橙や赤のような上に行くのは厳しい(大意)」と言っていました。私は結局水色になるには16か月(休止期間を除いて10か月程度)かかってしまいましたが、その反例となりたいです。なります。非常に遠い道ですが千里の道もなんとやら、なので、ひとまず目先の目標はAtCoder青色です。学部卒業までに橙色になれるといいな。
目標宣言をして自分を逃げられないところまでに追い詰めたところで、このブログを締めさせていただきます。駄文にお付き合い頂きありがとうございました。次の色変記事でお会いしましょう。
あ、★押してくれたら喜びます。おねがいします><