接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > 水色 > AtCoderで水色になるまでにやったこと

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

水色 AtCoder 競技プログラミング 競プロ

9月29日のAtCoderBeginnerContest142で水色になったので変色記事を生やします。 無限人によって書かれてますが自分のやってきたことを書いていきます。
停滞っていうほどの停滞はないけれど爆上げもなく地道にレートが上がってるっていう結構珍しい？タイプな気がします。

自己紹介

よく水色になった記事を見てもともと強い人だったり一瞬で水色なってたりで参考にならね〜って思ったりしたので自分の経験値的なものを書いておきます。
今は情報系の院に居ますが学部のときは文系でした。
一応理系志望だったので高校数学の範囲は一通りやった程度で学部に入ってからは数学にほとんど触ってないです。
プログラミングは高校生の時にCをちょっと触ってたくらいです多分ループと配列が書けて構造体がわからない程度アルゴリズムはバブルソートを知っていたくらい。
学部の3年生後半くらいになってからpythonを触る機会があってそこからまたプログラミングをやり始めて去年の6月くらいにAtCoderに初参加しました。
競技プログラミングをやるにあたってC++を一からやり始めました。
大体こんな感じで、めちゃめちゃ強い背景があるって感じではないです。
精進のところで後述しますが、どちらかというと効率の悪いやり方だった気がするので、水色になりたい人は必要なところだけ参考にして反面教師にしてください。

精進の種類について（主観）

やったことを書く前に精進の種類について書いておこうと思います。
これは一般的なものではなく完全に僕の主観なんですが、精進には2種類あると思っています。
その2種類というのが音ゲーでいう下埋めと高難易度特攻です。
下埋めは自分が時間をかければ大体解ける点数以下を全部埋めるもので
高難易度特攻が時間をかけても解けるか解けないかギリギリの難易度に挑戦することです。
それぞれどちらが良いかというものではなくてどちらにも良い点があると思うので目的に合わせて使い分けていくべきだと思ってます。
AtCoderにはパフォーマンスという概念がありますが、下埋めはパフォーマンスの下限を上げるもの。
高難易度特攻がパフォーマンスの上限を上げるものだと思っています。
僕の場合高難易度特攻はほとんどやらずに下埋めメインでやってました。
5月頃に300以下を全部埋めたんですが、そのおかげか新ABCあたりから結構安定して水パフォが出るようになったと思います。
その反面高難易度特攻をほとんどしなかったため、パフォの最高が初期あたりの1600で止まってますね…

f:id:tkm-kyudo:20190930011213p:plain 水パフォ安定して出したい人は300以下と今ならABCのDを埋めると良いと思うよ！
青パフォガンガン出したい人は500・600をガンガンやっていこう
今ならProblemsのDifficultyもあるので水色あたりにガンガン特攻するのが良いと思うよ。

長くなったけどパフォを安定させたいなら下埋めで上限伸ばしたいなら高難易度特攻っていう自分のイメージでした。
青パフォ出るけど事故って茶色とか出るって人は下埋めが足りないのかも？

緑色になるまでにやったこと

緑色になるまでにやったことは正直あまり覚えていないんですが、最初はけんちょんさんの記事を見て勉強してたと思います。
言わずと知れたABS。
AtCoderを始める前にとりあえずこれをやってコンテストに出始めました。
qiita.com その後はコンテストで解けなかった問題を復習したりAtCoder Scoresで200・300点あたりを触ったり AtCoder ProblemsでABCのCまでを埋めたりしてました。
他には蟻本を買ってけんちょんさんの記事を見ながら勉強してました。 qiita.com

最近だとABC-Dまで解いて緑色パフォ出ない回もあったりするので今から緑目指す人は前より大変だなって気はします…

水色になるまでに解いた問題

主にAtCoderがメインで最近はこどふぉでの精進もはじめました。
精進のやり方のところでも書きますが、最近だとこどふぉ精進が結構いい感じかなと思ってます。
AtCoderでの解いた問題なんかは以下の通りで他の水色になった人に比べると多めかなーっていう感じ。
緑の人でAtCoderで解けそうな問題は大体解いちゃったけどまだ水色になれなさそうっていう人はこどふぉがおすすめです。
英語っていうハードルはあるけれど、新ABC向けに良さそうな問題がたくさんあります。
新ABCで水色になるためには4完早解きかEを解く必要があるんですが、Eの打率を上げるのが一番の近道かなって思います。
で、そのEの打率を上げるために良い問題がこどふぉにはたくさんあるなって感じです。
Eは結構典型が置かれるイメージでAtCoderには少ないけどこどふぉにはたくさんあるのでEの打率を上げるためにもこどふぉやりましょう！

水色になるまでに勉強したアルゴリズムなど

どの変色記事にも書かれていてどこも似たような感じだと思いますが一応列挙しておきます。

  • GCD・LCM
  • 素数判定
  • 約数列挙
  • 素因数分解
  • ランレングス圧縮（最近ちょこちょこ使う気がする）
  • 二項係数
  • 繰り返し二乗法・MODの逆元
  • しゃくとり法
  • DFS・BFS
  • ワーシャルフロイド・ベルマンフォード・ダイクストラ
  • UnionFind
  • LIS
  • DP

以下はやったけど本番中に使った記憶がないもの
多分水色になるためには必要ではないと思いますがローリングハッシュなんかは500で出てきたのでやっておいて損はないかも

  • LCS
  • ローリングハッシュ・Z-Algorythm
  • 拡張ユークリッド互除法
  • 二部最大マッチング
  • BIT
  • セグ木（遅延評価）
  • 最大流(Dinic)

こうしてみると結構色々やってますね
僕の場合色々なアルゴリズム触るのが好きだったので色々手を出してましたが、水色になるだけなら知っているアルゴリズムを使いこなせるようになるほうが絶対いいと思います。

精進のやり方

  1. 基本的には問題を見て考察する（5~15分）
  2. 解けそうなら実装する、わからなければ解説を見る
  3. 解説でわかれば実装、わからなければ解説ブログを見る
  4. 解説ブログでわかれば実装、わからなければコードを見る
  5. コードを写経しながら理解に努める

っていう感じでやってます。
解説を見るときに意識しているのが、自分がどこまで考察できてどこから出来なかったのかを把握することです。
そして、どうしてそこから考察出来なかったかを考えて解説を身につけると考察力がついていくと思います。
他にも知識の抽象化は大事です。このアルゴリズムはどういうときに適用できるかとかですね。
次に、ここは結構分かれそうですが、僕の場合アルゴリズムやプログラミングの知識がどちらも少なかったので 最初は知識を詰め込むために写経メインでやってました。
写経の良い点としてはわからないものを実際に書くことで理解が深まることで
悪い点としては自分で実装していないので復習なんかをしないと知識の定着がし辛いってことが挙げられると思います。
で、僕の場合復習モチベがあまりなく、新規ACをしてモチベを保つタイプだったので
あーこれ知ってる、とかあーこれこのアルゴリズム使うんだよなーってなりつつ解けないみたいな感じが多かったです。
最近はこどふぉを始めたのでこどふぉで新規ACしながらAtCoderでは復習をメインでやってます。
水色になる1週間前くらいからEDPCの復習をしていましたが、そのおかげか本番でDPを通せて復習大事だなあって感じました。
一回で身につく人や理解して抽象化が上手い人はガンガン新規ACしていっても大丈夫だと思いますが
自分みたいに知ってるけど書けない！みたいな人は復習してみてはどうでしょうか？
前できなかったけど今できるようになってるなーと意外と成長の実感感じれてよかったです。
レート以外のモチベーションの維持もやっぱり大事だと思ってるので成長を感じられる復習は結構良いと思います。

モチベーションのためにやっていること

競プロ続けるのにモチベーションって大事ですよね。
勉強してるのに全然伸びないとかあとから始めた人に一瞬で抜かれたとか○○ヶ月で○色！とか色々モチベーション削られる要因はたくさんあると思います。
元も子もないことを言うと他人と比較するのはやめましょうｗ
特に競プロは今までやってきたこと（数学的な力）とかが大きく出るので初期のレート遷移は参考にならないことが多いです。
とはいってもレートっていう形で出る以上気にするなっていうほうが無理だと思うので自分のペースで続けられるなにかを見つけるのが一番いいと思います。
僕がモチベーション維持のために続けていることを以下にあげます。

コンテストに出る

これがなんだかんだ一番大切かなーって思います。
AtCoderを始めてからはどうしても外せない用事以外は基本的にコンテストに出てます。
AtCoder以外ではCodeforcesやyukicoderなど大体週に2~3回はコンテストに参加している感じです。
コンテストに出ている理由としては、やっぱり精進より実際のコンテストのほうが楽しいからです。
もちろん精進も精進で楽しい面もありますが、格ゲーのコンボ練習より対人戦が楽しいみたいな感覚です。
コンテストに出ると良かった点・悪かった点がわかるのでそれを精進に反映して…という流れですね。
一喜一憂あるとは思いますが続ける上でいちばん大事なのはコンテストに出ることかなって今は思ってます。

一日一問新規AC

これは結構やっている人も多いんじゃないかなと思います。
AtCoder Problemsにはstreakというものがあってそれを長く続けるっていうものですね。
僕は今191なので365までにはしたいなーっていうモチベで続けてます（prdさんの500日は本当にすごい）
これの良い点としては一日一回競プロに取り組むのを習慣化出来ること。
一回精進始めちゃえば精進出来るけど、精進やるまでが億劫っていうことがありますよね。少なくとも僕はそうです。
けどstreakを繋いでると継続するために一問は絶対解くことになるので精進やるまでの障害を少しでも減らせる効果になってると思います。
もちろんこれも悪い点があって、虚無ACで繋いじゃって精進にならないとか、streakを繋ぐのが義務感になっちゃうとか色々あると思います。
そういうときはすっぱりやめちゃってもいいと思ってます。
ぼくは今の所続けていますが、streakを繋ぐ意味を見いだせなくなったら一回すっぱり切っちゃうと思います。
こういう継続が苦手な人はこんな記事もあるので自分にあった精進方法を見つけましょう。 www.creativ.xyz

Twitterなどで繋がりを作る

繋がりって大事だと思います。
一緒に競い合う仲間だったり、仲のいい友達だったりがいると一人で頑張るよりは頑張りやすさが違うと思います。
僕は基本的に一人でちまちま精進していた身なんですが、最近Twitterとかで絡みが増えてる人とかが居て前より楽しいなーって思ってます。
もう一個良い点としては気軽にわからないことを聞ける人がいるのが大きいですね。
一人だとわからないことでもTwitterに投げるとプロが丁寧に教えてくれます（競プロ界隈の良いところだと思ってます）。
こういう繋がりがあることで競プロに愛着が湧くとちょっとやめたくなったり、落ち込んだりしても愛着があるとなんだかんだ続けたくなる気がします。
Twitterとか眺めてても色んな絡みがあってみんな楽しそうにしてるので、こういう繋がり大事だなーといつも思ってます。
あとはオンサイトなんかで仲のいい人や絡みのある人と会うことをモチベーションにしてる人もいるじゃないかなって思ってます。
そこで楽しかったらまた競プロも頑張ろうってなれますよね。

おわりに

ここまで読んでくださってありがとうございます。
結構思うままに書いてしまったので読みづらい点など多かったと思います。
水色になって一区切りとして競プロをやっていて感じたこと思ったことなんかを文字に起こしてみました。
参考になった方や楽しんで読んでくれた方が居ましたら幸いです。
水色にはなりましたが、これからも青・黄…と上を目指して精進は続けていくので競プロ界隈の方々はどうぞよろしくおねがいします。
夏休み競プロに捧げて流石に研究がやばいのでちょっと競プロの精進ペースは落ちるかも…ｗ
コメントや指摘、こういうこと書いてほしいということがあれば随時追記していきます。
聞きたいことある！って人は気軽にTwitterなんかで聞いてください。