記事の目的
タイトル通り3年かけて再び緑色になったことを振り返る記事です。
レート推移
自分がいつ競プロをやっていたかが良くわかるグラフになっています。
AtCoder Problems
自己紹介
こんにちは、dorimiamnと言います。
この記事を書いた時点ではMARCHの数学科みたいなところのB1です。
競技プログラミングやWebプログラミング、IPAの資格取得とか浅く広くやっている感じで、プログラミングとかCSに興味があります
(CSって書きましたがもっと優しい呼称があるかもしれません。情報に興味があるは曖昧すぎる。かといってCSというのは大仰すぎる。適切な名称を知っている方がいたら教えてください。)
再入緑を目指したときの前提スペック
私のスペックについて言及します。
3年ほど前に入緑しましたが、維持できず3年ほど茶色で停滞していました。
知っていた、名前を聞いたことのあったアルゴリズム・データ構造
- 全探索
- bit全探索
- next_permutation
- 貪欲法
- DFS
- BFS
- ダイクストラ法
- ベルマンフォード法
- フロイド・ワーシャル法
- UnionFind
- 二分探索
- 累積和
- 尺取法
- ナップサック
- 半分全列挙
- エラトステネスの篩
- キュー
- 優先度付きキュー
- スタック
あくまでも知っていただけで理解していたわけではありません。
それ以外の部分
- 数学は多分得意ではありません。どちらかというと苦手です。具体的に言及すると高校三年生の時の記述模試では偏差値は50以下でした。
- 公立中→公立高→通信高→浪人→現在といった経歴を持っています。
- 応用情報に合格しています。
- 考察が苦手だった。普段の精進で考察をストックさせることが出来なかった。
再入緑をするまでにやったことや意識したこと
- 二分探索の類題を20題ほどやった
- 考察をストックして時間があるときに実装したり解説を読んだりするようにした。
- どこに着目したら計算量が落とせるかを以前より考えられるようになった。
二分探索をしつこくやった。
停滞期は漠然といろんな問題を解くことが多かったのですが、それだとその問題で扱ったアルゴリズムがきちんと使えるようになっているかわからなかった。類題として3題は解くようにしていたが足りなかった。
その対策としてAtCoder Tagsを用いて類題を徹底的に解くようにしました。
現状は二分探索カテゴリーの緑Diff 問題をほぼ解き終えたので水Diff の問題を解こうかというところです。
水Diff で一旦区切りをつけるつもりです。
AtCoder Tags にはとてもお世話になっていて非常に感謝しています。製作者である、ぬるぬる(Twitter:@__Null_Null_)様には頭が上がりません。本当にありがとうございます！！！
これは運が良かっただけなのもありますが直近のABCではD問題で二分探索が有効な問題が多かった印象で、そのおかげでこの精進をするようになってからは+70 ほどレートが上がりました。
そもそも二分探索の重要度は高いと感じています。ABCのD問題辺りではよく出されている感覚があります。二分探索を通して区間の考え方(開区間や閉区間、区間自体に持たせる情報の意味など)がよく身について他の系統の問題でも混乱せずに書けるようになった感じがします。
私は3年前も苦手としていたようで、ちゃんと穴を塞いでおきたいという意図もありました。ABC144 D Water Bottle は強く印象に残っている問題です。
自分が知っているアルゴリズムをちゃんと理解しているかは確認しておいた方が良いです。そうでないと高度なアルゴリズムの方に気持ちが向いてしまってなぜか解けるべき問題が解けないなんてことが起こりうると思います。
考察のストック
今年の5月から考察をストックすることができるようになりました。というのは二分探索を集中して解いてたから二分探索への理解が進んだためだと思います。アルゴリズムの本質を理解した上で扱えるようになるとちゃんと問題が解けたり、解説の内容をより深く理解できるようになると感じました。
また考察はいつでも出来ます。実装は時間と場所をちゃんと確保しないと私には辛いですが、考察ならそんなものはあまり必要ありません。考えておいて時間があったら実装をするって感じのことが出来るようになったので基本的に毎日考えておけるようになってきました。これはつまり24時間精進しているといっても過言ではないです。今まではパソコンに向かっている時間が精進の時間でしたが今や24時間いつでも精進をしているようなものですね？
着目する場所
考察のストックの延長にあるかもしれませんが、コンテスト中にE問題の方針が立たないなんてことがなくなった気がします(直近3,4回は)。おおよそE問題だと愚直に実装したらTLE するような問題が出されると思うのですが、これらの計算量を落とす方針を立てられるようになりました。粘って考察できるようになったので、単純にアルゴリズムを適用しただけでは解けないからそこからどうしたらアルゴリズムを応用して計算量を落とせば良いか？まで思考を進めることが出来るようになったと感じています。
これから
入水目指して頑張ります。
今の精進方法と同様に、AtCoder Tags のお世話になってグラフ問題をひたすら解くことになりそうです。
3年間ほどスランプだったのでその分、今は調子がいいです。波に乗ってHighestを伸ばせたら嬉しい。
終わりに
3年間ほど停滞していても緑には戻れる！
レートが上がらなくても焦ることはないと思います(実際私も焦ることは多かったですが)。ちゃんと上がります。停滞したり下がったりでメンタルをやられることがあると思いますが無理をせず距離を取ることも大事です。またやりたくなったら戻れば良いです。競プロだけが全てではありません。私は一度資格を取る方に逃げました。
数学が得意でなくても緑にはなれる！
高校数学で求められる考え方を、模試で偏差値50 とかいうレベルの理解でも緑にはなれます。
プログラミングが好きって人ならアルゴリズムも楽しんで学ぶことが出来る感じだと思うので、たくさん実験をしたり問題を解いてその延長で対策を行えば緑タッチはいけると考えています。数学ができない分初速は遅いですが着実に伸びてはいくはずです。
自分に合った精進方法を探しておいた方がいい！
私の場合は自分の苦手をきちんと把握して重点的な対策をすることが大事でした。レートが低いうちは高度なアルゴリズムに手を出すよりも既に使えるアルゴリズムをよりしっかりと使えるようにしたほうが良さそうです。
以上参考になるかわかりませんがなったら嬉しいです。
ここまでお読みいただきありがとうございました！