Ccmmutty logo
Commutty IT
4 min read

本格的に競プロに取り組み始めてから半年で入緑するまで

https://cdn.magicode.io/media/notebox/0fcb587e-ed2c-4bea-b805-fbed5937e47a.jpeg

スペック

  • 大学時代は文系学部
  • 入茶までは14回程度
  • 中学受験経験なし
  • 数学を受験で使っていたがセンター(現在の大学入試共通テスト)数学は60点くらいだった気がする
  • 数学は嫌いではないが苦手意識がある
  • 数Ⅲの範囲を独学で少し齧ったがあまり覚えていない
  • Webアプリケーションエンジニアとして3年強働いている

入緑までのレーティング推移

上記のような形でかなり苦しんだ。
最初に入茶した時から入緑するまでに50回ほどかかっており、そのうち緑コーダーになれそうだと感じたのは2022年10月くらいから。
そのあたりからは緑パフォを出せることが多くなり、2022年11月最後のABC279で入緑を達成。
レートが上がり始めた10月末の時期に何をしていたかというとちょうど茶色diffの問題が埋め終わり、緑diffに手をつけ始めたところだった。
茶diffを埋め終えたところで茶diffの問題であれば、概ね解けるだろうという自信がついたのが大きいと思う。 その前は何をしていたかも書いておく。
6月から本格的に競プロを頑張ろうと思い、去年も目標にしていた入緑を年内には達成しようと決意した。
6, 7月はAtcoder ProbremsのBoot camp for Beginnersをぼちぼち埋めていた記憶がある。
8月は灰diffもとにかく埋めてやろうと思い虚無埋めをしていた。
これは無駄な気もするが、ABCのA問題B問題を解くスピードが上がった気はする。
あとAtcoder ProbremsのAC数が増えていくのが楽しい。
9月もぼちぼち灰diff埋めと茶diffの問題を解いていた。
このあたりからAtCoder上達のガイドライン【中級編】の問題も解いていた記憶がある。
10月は鉄則本を誘惑に負けて買ってしまったので、少しずつ進めていた。
またガイドライン中級編の問題が難しくなって来て、解説AC多めながらも何とかやり切った。
茶diffの問題も10月末には埋まりきった。
11月は140問くらい解いていた緑diffの問題を少しずつ埋め始め、現状250問までAC。

入緑するまでに手を付けたもの

  • Atcoder ProblemsのBoot camp for Beginners(300問)
  • Atcoderの過去問を片っ端から灰800問、茶280問、緑250問くらいまで
  • レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編】(https://qiita.com/e869120/items/eb50fdaece12be418faa)
  • 鹿本(アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門)
  • 鉄則本(競技プログラミングの鉄則)4章途中まで

有効だったと思うもの

どれも有効だったと思うが鉄則本を読むまで2次元の累積和を知らなかったし、競プロに最適化されてる気がするのでおすすめ(途中で止まっているが)
片っ端から問題を解くのも最終的には有効だった気がする、難易度を階段順にするためにdiffの色が同じ問題の中で、ポイントがついてないもの→ABCのdiff順→ARCのdiff順の順に解いていった
ARCは茶色でもABCの茶色より難しく感じて発狂しそうだったが考察力は鍛えられた気がする(コンテスト中の問題読み取り力が上がった気がする)
E869120さんの上達のガイドライン中級編も分野毎に問題がまとまっていて有効だと思う
ただbitDPや区間DPは緑までは必要ないかなとも思うので緑になるまでの段階では飛ばしても良いかもしれないと思った

多分身についているアルゴリズムとデータ構造

  • Union Find
  • DFS(再帰関数)/BFS(queue)
  • あまり複雑ではないDP(1次元、2次元)
  • 累積和(1次元、2次元、いもす法)
  • 二分探索(三分探索も概念は理解しているつもり)
  • 最小公倍数(LCM)、最大公約数(GCD)
  • エラトステネスの篩
  • 高速な素数判定
  • map, set, multiset
  • modについて
  • ビット全探索
  • priority_queue
  • メモ化再帰
  • 全列挙の通り数を減らす考察
  • 高速な累乗計算(繰り返し二乗法)
しゃくとり法はそれほど使ってないので微妙
その他グラフアルゴリズム(ダイクストラ、ワーシャルフロイド、クラスカル)や逆元、bitDP、区間DPなども問題に触れたりはしているがきちんと理解しているとは言い難い

精進スタイル

  • 問題を読んで全く取っ掛かりがつかめない場合は割とすぐに解説を見ることが多い
  • わかりそうな場合は時間を掛けて解く
  • 問題の解き直しなどはしていない
  • わからなかった問題は解説や他の人の提出コードを読み解きながらコメントを書きつつ、理解できるまで考えるようにしている(中には今の自分では本当にわからない問題などもあるが、茶diff、緑diffまでなら大体の場合理解できる)

感想

  • 他の人はもっと少ない問題数で入緑している人が多いと思うので彼我の差を感じる
  • やっぱり数学ができる人は基本になる論理的思考力が身についているので強い
  • 論理的思考力が上がった気もするが自分がしているのは解法パターンの暗記な気もしている
  • 茶diffの問題を理解して全部埋めれば(解説ACも含めて)、本番のコンテストでも茶diffの問題が結構な確度で解けるようになる
  • ARCの問題難しすぎ
  • 数学得意ではない人間が緑になるためにはかなりの努力が必要なのではという気持ち

Discussion

コメントにはログインが必要です。