半年間で競プロを 546 時間やった振り返り（茶 424 → 緑 904）

年初に「今年の前半は競プロをがんばる！」と決めて半年間取り組んだので、その振り返りです。取り組んだこととその感想が主な内容です。
自分の備忘録目的で殴り書きした感じなので、あまりまとまりがない上に、箇条書きですがご了承ください m(_ _)m

結論としては、「競プロ楽しく取り組めてよかったなー！」です。

自己紹介

ざっくりと。

高専の非情報系出身です。¹
2021 年の 11 月から AtCoder で競プロを再開²しました
仕事は web サイト開発で主に PHP を書いてます³
競プロの使用言語は C++です⁴
好きなベーシストはピノ・パラディーノです

競プロを始めたきっかけ

現在プログラムを書く仕事をしているのですが、「プログラムを書く上での基礎」があまり身についていないと感じていました。具体的には、コンピュータの動作原理であったり、ネットワークの動作原理であったり、競プロで学べるアルゴリズムとデータ構造であったり、などです。
足りないものをあげるときりがないのですが、その中でも比較的楽しく学べそうな「アルゴリズムとデータ構造」の基礎を身に着けたいという理由で競プロをはじめました。
また、2022 年の年初に今年こそは目標を立てっぱなしにしないで、何かがんばりたい！と思って、競プロなら楽しくできそうだなと思ったためです。
一応年初の目標は、「半年で競プロに 700 時間使う」だったのですが、結局 546 時間で目標達成ならずでした、、残念。

レート推移と精進量

レート推移や精進量はこんな感じです。

レート推移

パフォ推移

解いた問題

月ごとのレート推移と勉強時間

月	レート推移	勉強時間
2022/01	424 → 547 (+123)	94h
2022/02	547 → 678 (+131)	110h
2022/03	678 → 800 (+122)	96h
2022/04	800 → 857 (+57)	99h
2022/05	857 → 919 (+62)	100h
2022/06	919 → 904 (-15)	47h

うーん、明らかにレートが伸びづらくなっているので、ここからが根性試されるなあ、、という感じがします。（そして、勉強時間が如実に減っていますね、、）

アルゴリズム・データ構造と習熟度

以下は、アルゴリズム・データ構造とその習熟度です。
茶〜緑 diff の問題が出た時を想定しています。

アルゴリズム	習熟度
全探索	書ける
bit 全探索	書ける
二分探索	書ける
尺取法	書ける(怪しい)
累積和	書ける
DFS	書ける
BFS	書ける
01-BFS	書ける(怪しい)
DP	書ける
ダイクストラ	使える(ライブラリ頼み)
ワーシャルフロイド	使える(ライブラリ頼み)
クラスカル法	使える(ライブラリ頼み)
高速な素数列挙、素因数分解	使える(ライブラリ頼み)

データ構造	習熟度
set	使える
map	使える
multiset	使える(怪しい)
セグ木	使える(怪しい)
BIT	使える
遅延セグ木	使える(怪しい)
UnionFind	使える

けっこう怪しいものが多いです。うーん、よくないですね。ポジティブに捉えると、課題がある程度明確とも言えます。

やった精進と感想

これまでやった精進と感想です。時系列にはなっていないです。

APG4b (AtCoder Programming Guide for beginners)

C++で競プロをやると決めてから、真っ先に一通りやりました。けっこうボリュームはありますが、大切な部分が分かりやすくまとまっていて、すごくありがたかったです。
最近は見返すことはほとんどないですが、1〜2 ヶ月くらいは頻繁に見返しながら問題を解いていた気がします。

典型 90（★2 ~ ★4）

まさに典型的なアルゴリズムやデータ構造を学べる良問ばかりな印象です。
★2、★3 は自力 AC できるようになるまで解きました。3 周目ですべて自力 AC できました。
★4 は 1 周しかしてません。（本当は自力 AC できるまでやりたいと思いつつ後回しで、なあなあに、、）
やった精進の中ではかなり効率的に力がついた感があります。

蟻本（初級編のみ）

灰色のころに読んだので、かなり時間がかかりました。
今思うと緑くらいまでに必要なアルゴリズムやデータ構造の網羅性が高く、とりあえず「ふーん、こんなアルゴリズムがあるのね」というのを知れたのはすごくよかったです。
中級編、読まねばと思いつつ、なあなあに、、

アルゴリズム x 数学本

競プロに必要な基本的な数学知識がギュッと詰まっていて、「数学無理ぃ、、」という感じの競プロ er 全員におすすめしたいです。
考察テクニックも書いてあって、勉強になりました。

AtCoder Problems Recommendation

最もお世話になったコンテンツです。
茶色の時はひたすら moderate に出てくる問題を倒していました。本当に moderate(= そこそこ難しくて力になりそうな問題たち)な問題がバンバン出てきて、本当にすごいです。
「今日疲れたなあ、、」って時は Easy からつまんで、「解けるぜひゃっほーー！！」ってやるのも結構楽しいです。
自分は毎日続けるのが性に合っているので、streak を伸ばしています（執筆時点で 161 日）

バチャ（あさかつ）

「コンテストで解けなかった 1 問を解けるようにするとよい」という直大さんのツイートを見て、それを早回しでやりたいと思ってはじめました。
自分は「あさかつ」という朝の 7:30〜の 6 問 60 分のバチャに何回か出てました。diff は灰灰茶緑水青です。
バーチャルコンテストというだけあって、コンテストに似た緊張感があります。なんとなくですが、コンテストに落ち着いて取り組めるようになった気がします。
コンテストより短くて、1 時間という時間が個人的にちょうどよかったです。
簡単な問題の早解き訓練と、難しい問題の考察訓練をいいバランスでできるのがうれしいです。

コンテスト出場(ABC)

コンテストはよっぽど大切な予定が無い限り出ると決めてました。理由は、長期で出続けるとレーティングに実力が反映されると考えたためです。
どうしても直近数回のコンテストだと、得意/不得意な問題でパフォーマンスがばらつくので、2〜3 ヶ月単位くらいで、自分のレートの変動を見るのがいいと思っています。
それでも、大きくレーティングを落とすと、ずーーーん、、、となって、寝るまでは引きずりますが、、、（寝たら忘れます）
ARCは1回だけ参加しましたが、基本的に出ない方針でした。ABCは優先参加するので、週末の夜に2回もコンテストに出るのは時間の都合上難しかったためです。また、自分の実力からするとパフォーマンスが大きくばらつくことが予想できたので、レーティングが実力に収束しにくくなるかも？とも思いました。

ACL(AtCoder Library)

C++ で atcoder 公式から提供されているライブラリです。C++で競プロしようと決めた時は知らなかったですが、頻出のデータ構造やアルゴリズムが簡単につかえてとても便利です。
自分が使えるのは、以下です。
- modint (一番お世話になってます！めちゃくちゃ最高です)
- fenwicktree(コンテスト未使用)
- segtree(コンテスト未使用)
- lazysegtree(コンテスト未使用)
- dsu

EDPC(Edupdational DP Contest)

苦手な DP を書けるようになったのは EDPC が一番効果が合った気がします。
A〜E までしかやってません。
けんちょんさんの EDPC 解説記事にもお世話になりました。

AHC

アルゴリズムの精進ではないのですが、とっても楽しかったです。レートが下がらないし、WA 仕放題なので気楽に取り組めるのもうれしいです。
詳しくはこちらの記事に書きました。

お世話になった解説

C++を利用しているので、主に C++の解説記事、動画に大変お世話になりました。特に、以下のブログと動画にお世話になりました。

はまやんはまやんさんのブログ
「うー、分からない、、検索してみよ」という感じで検索すると高確率ではまやんさんが解説を書いていて、何度も何度も助けられました。
けんちょんさんのブログ
解説のわかりやすさはもちろん、記事のタグがめちゃくちゃいい感じについていて、類題を探したり解いたりする時にすごく助かりました。
すぬけさんの公式解説動画
公式解説、解説記事を読んでも分からない、、という時に本当に助けられました。初心者の目線で同じことでも毎回丁寧に板書しながら解説してくれるのがとてもありがたかったです。

これらの解説のコードをそのまま読めるというだけでも、「C++にしてよかったなあ」と思いました。

お世話になった Twitter

コンテスト後の感想戦が楽しい＆勉強になります。
もちろんコンテスト外のみなさまのなんやかんやのつぶやきも楽しいし、勉強になります。
問題が分からない時につぶやくと、どこからともなく助けてくれる強い人が現れて的確なアドバイスをくれることがあって、すごく助かりました。
レートが近そうな人を見つけて、勝手にライバル認定してがんばるのもいいと思います。
ただし、Twitter にはとんでもなく強い人がゴロゴロいて、自分より後に始めた人が光の速さで色変していったり、ライバルだと思ってたのに瞬く間に遠くにいってしまったりします。そういう時は速攻でライバル認定解除して、心の平穏を取り戻すのが大切だと感じました。

精進について

精進について、自分はざっくり分けると以下のように捉えています。感覚的には、後半 2 つはかなり密接に紐付いている感じがして、スッと実装ができるので、考察が浮かぶみたいな感覚です。

知識をつける精進
- 内容：いわゆる座学。まだ知らないアルゴリズムやデータ構造を学ぶ精進。
- 精進方法：本、記事を読む。読んだ内容を書いてみる。
実装力をあげる精進
- 内容：解法が見えた時に、それを実装に落とす精進。
- 精進方法：身につけたい解法の類題を探して、立て続けに解く。
考察力をつける精進
- 内容：本番で問題を考察して、実装の手前まで持っていくための精進
- 精進方法：自分の色 or 1 色上の問題をノーヒントで解く。バチャとか AtCoderProblems とかでランダムに問題を解く

hamamu さんのこちらの記事にある 3 種の精進とほぼ同じですね。

コンテストの思い出

コンテストで印象に残っている回です。 DP への苦手意識が強かったので、思い出回が DP 回に集中してますね。

ABC237
atcoder 再開してから、唯一の 2 完回。パフォも再開後ダントツの最低(273)でした。けっこう凹みましたが、全然力がついてないという事が自覚できてとてもよかったです。ちなみにこの問題のコーナーケース？が取れませんでした。
ABC240
コンテストで初めて DP を AC した回。問題見た時はダメだ〜って思ったけど、なんとか書けてとてもうれしかったです。
ABC244
初 5 完＆入緑した回。E 問題は DP。入緑もうれしかったけど、この DP が書けた方がうれしかったかも。
ABC247
はじめて再帰をコンテストで書いた回（たぶん）。そして茶落ちしました。灰diffの問題ですがコンテスト中、苦労した記憶があります。
ABC253
5 完 2 回目。E 問題で、その時に練習していた DP 高速化を書けてとってもうれしかったです。

やっぱり「はじめてコンテストで○○の使って解いた！」という時が、すごくうれしいです！

今後について

今後は水色タッチを目指してがんばりたいです。現状と今後の課題は、多分こんな感じです。

水色になるために明らかに不足している知識はなさそう
簡単な問題の早時きがイマイチなので、C 問題まで 15 分くらいで片付けられるようにしたい。D、E にしっかり時間を残したいので。
D、E 問題を考察して実装に落とす力が不足している。緑 diff 後半〜水 diff の問題をたくさん(50〜100 問)くらい解く必要がありそう。
実装が苦手なアルゴリズム、すぐバグらせるアルゴリズムの「型」を決めて、頭を使わずに実装できるようにした方が良い(尺取りを que で管理したりみたいな)

ただ、今年の後半は競プロ以外で取り組みたいこともあるので、精進とコンテストの参加ペースは少し落とそうかなと思っています。なので、どの精進を優先してやるかは、また計画立てないとな〜という感じです。

結論：競プロ楽しかったので、やってよかった

競プロ、とても楽しくていい趣味見つけたな〜という感じです。

はじめは仕事に役に立つかも？と思って始めたのですが、趣味としてすごく好きです。やっぱ問題解けた時、とりわけコンテストで解けた時の「解けたーーー！！！！！」が最高に気持ちいいです。
けっこう長く続けていけそうな気がしています。

また、仕事に役に立つか？はあんまり言及したくない気もするのですが、⁵あくまで個人的な感想として、

計算量がどれくらいになるか？
どう書けば処理をバグらせにくく、可読性高く書けるのか？
簡単な処理をパッと書けるか？

みたいな部分が仕事で役に立ったような気がします。

だいたい書きたいことはこんなところなので、この辺で終わりにします。
最後まで読んでいただいてありがとうございます！

正確には高専の専攻科です。
↩
再開というのは、2019 年に 3 ヶ月ほど競プロやってすぐに辞めてしまった時期があるためです。
↩
転職したので、仕事でプログラムを書くようになったのは 3 年前くらいからです。
↩
2019 年にやっていた時は、Python でした。C++は 10 年以上前の高専の授業ですこーし書いたことある程度です。↩
Twitter でこの話題になる度、割と燃えてそうだからです。↩

nakashiiiの自由帳

自由に書きます