ながめも

競技プログラミングについて

AtCoderで水色になるまでにやったこと

20191123に開催されたDDCC2020予選で、水色になりました

f:id:coonevo:20191124002926p:plain

jjjjjjjtgpptmjj - AtCoder

概要

これは何

AtCoderで水色になったヒトが書きがちな「AtCoderで水色になるまでにやったこと」という記事です。 新規性があるかどうかはわかりませんが、これから水色になろうとしているが困っているヒトの助けになればなと思って書きます。

私は誰

生命科学系の大学院生M1です。研究で必要になったため、Pythonの勉強を兼ねて始めたところ、競プロ沼にはまりました。

学部時代は全くプログラミングに触れていなくて、いわゆる純粋培養(?)です。周りにC++を書いているヒトもいなくて、ツイッターの親切な方々に教えてもらったり、独学しながら雰囲気で慣れていきました

どういった人向けか

緑で伸び悩んでいる人向けだと思います。

上のレートのグラフを見ていただけるとわかるのですが、緑の期間がかなり長いです。8ヶ月停滞していました(ええ・・・)。

正直、4月の段階では(傾き的に(これは罠で、身の丈に合わない青パフォをとったせいです、驕っていました))水色になるのは時間の問題だと思っていたのですが、そこから約半年停滞しています。

抜け出し始めたのはここ最近ですが、自分の中で感覚として変化があったように思うので、それをなるべく言語化したいと思います。

〜緑

ABC-A,B埋めをしたら、だいたい雰囲気は掴めました。 たまに頑張ってCを解くと緑になれる時代でした。

緑中位停滞期

ABC-Cを埋めたり、コンテストに出続けていました。 コンテストに出ては一喜一憂して、

なんでレートが伸びないんだ

とゴネていました。

大学院の授業が忙しかったりして、普段の精進はあまりできていなかったのもありますが、それ以上の問題がありました(後述)。

勉強していたこと

  • 全探索
  • 累積和
  • 二分探索
  • DFS, BFS
  • 基本的なDP
  • bit全探索
  • UnionFind
  • modint
  • GCD
  • XOR
  • 最短経路問題(ワーシャルフロイド、ダイクストラ
  • 後ろから操作する

あまり他の人たちと変わらないです。

緑中位脱出期

緑になった頃にライバルだった人たちが次々と成長していくのを横目に、緑中位をうろちょろするのもしんどくなっていました。

なんとなくAtCoder Problemsで彼らと進捗を比較してみたところ、あるものに圧倒的な差があることに気がつきました。

それは、解いている問題数です。

私がABC-Dの1/3を埋めているときに、彼らはほとんど解き終わっていました。

そこで、少し精進量を増やすとともに、以下のような工夫をしてみました。


  1. 復習をする

  2. 解いた問題をまとめる

  3. 何も考えずに書けるように工夫する


1. 復習をする

これは、当たり前のことなのですが、

ヒトは、復習をしないと忘れます。

私は、1ヶ月前のコンテストの問題すらもう一度見ても解法を思い出せませんでした。

そもそも、解いた記憶すらないみたいなこともありました。 なので、一度自力ACした問題も、解説ACした問題も、復習するようにしました。

2. 解いた問題をまとめる

復習をしやすくするための工夫です。

それだけでなく、記憶を増強するのに有効だと思ったので、なるべく実行するようにしています。

ACした問題全てを真面目に書くと疲れるので、

  • しっかり理解したい問題
  • ポイントだけでも瞬時に見たい問題

にわけて、前者は真面目に記事にして、後者はメモ程度に留めるようにしています。

一時期はてブロにまとめていたのですが、記事を書くのが億劫で続きませんでした。 最近は、scrapboxというサービスを使って記事を書いています(ステマではありません)。

f:id:coonevo:20191124014119p:plain

自分のメモにおすすめです。

もしよかったら覗いてみてください(解法のネタバレになる可能性があるので、注意です) scrapbox.io

3. 何も考えずに書けるように工夫する

私は勘違いしていたのですが、私が伸び悩んでいた原因は、地頭が足りないことでも、実装力がないためでもなく、

準備が足りていなかったからでした。

ここでいう準備とは

  • 類題の考察はコンテスト外でやっておく

  • アルゴリズムの書き方はコンテスト外で固めておく

といったことです。(累積和、二分探索(めぐる式は神)、DFS、BFS、グリッドの走査など)

競プロにおいて、多くの人が解く問題(例えば最近のABC-CやD)は、とにかく早さが命です。 10分変わるだけでパフォが数百変わるみたいなことも普通に起こります。

例えば、累積和の書き方を理解して、色々な問題に適用できるようになったとします。その書き方を、毎回紙に書いて考え直す場合と、自然と書ける場合では、10分の差など簡単にできてしまいます。

また、この差は、その問題だけでなく、後半の問題を考察する時間、またそのときの精神的余裕にも影響します。

停滞していた時期は、Dまで解けるし、Eが解けるようにならないとなあと思っていたのですが、大事なのは、Dをもっと早く解けるように工夫することでした。

工夫の仕方は、とにかくスニペットを充実させることでした。

累積和も、毎回添字を気にするのは辛いので、理解したら、それを呼び出したら絶対にバグらないようにしておく、みたいなことが大事だと思います。

今日のコンテストもそれがなかったら水色になれていなかったと思います。

何も考えずに書けるようになるものが増えたあと、

パフォーマンスの下限

が上がった気がしました。

個人差もあると思いますが、

毎回博打に頼ってレートを伸ばすよりも、コンスタントにパフォーマンスを出す方が精神衛生上よかった

ですし、実際レートは安定します。

緑〜水色になる決定打になったのは、私の場合、

準備に力を入れたことによるパフォの下限の上昇でした。

(参考) f:id:coonevo:20191124014028p:plain

AtCoder Performances

こんなこと書いていて次回以降下がっていったら悲しいなあ。頑張ります。

最後に

長くなりましたが、だいたい考えていたことはこんな程度です。当たり前のことしか書いてない気もするのですが、改めて言語化する意味でも記事にしました。何かの参考になったら嬉しいです。

今回入水したからといってこれを維持できることが保証されるわけでもないですし、今後緑との間を行き来することもあるとは思いますが、

以上のような精進方針を続けて、いずれはABC-Eレベルを安定させたいなと思っています。

それにはここに書いたこと以上のことが必要になってくるので、気を引き締めたいです。

最後まで読んでいただきありがとうございました。