この記事は競プロ Advent Calendar 2021 4日目の記事です。

この記事を書いている人と記事の内容について

初めまして、まーぼーです。
以前行われたARC129で、水色コーダーの仲間入りを果たしました。やったね。

この記事では、私がAtCoderで水色になるまでにやったことをまとめます。

この問題を埋めることで自分は何を得たいのかといった目的意識を持っていると、
精進効率が格段に上がる印象があります。
私は綺麗な実装方針で綺麗なコードを書くことを大事にして過去問を埋めていました。
参考までに、緑⇒水色になるまで700時間程かかりました。

★傾向と対策をする

コンテストに出ている中で、自分が苦手な問題の傾向が見えてくることがあると思います。
私の例を1つ挙げると、迷路の問題でよく配列外参照を起こしていました。
問題例:https://atcoder.jp/contests/abc007/tasks/abc007_3
これについてはライブラリを作ることで解決しました。
使用例を下に貼っておくのでよければ使ってみてください。

迷路の外側を#で埋める.cpp

#include <bits/stdc++.h>
#define rep(i,n) for(long long i=(long long)(0);i<(long long)(n);i++)
using namespace std;
int main() {
    long long h,w; 
    cin>>h>>w;
    vector<string> str(h+2); 
    rep(i,h) cin>>str[i+1];
    rep(i,w+2) str[0]+='#'; 
    rep(i,w+2) str[h+1]+='#';
    rep(i,h) str[i+1].insert(str[i+1].begin(),'#');
    rep(i,h) str[i+1].push_back('#');
    rep(i,h+2) cout<<str[i]<<endl;
}

これを使うと、こんな入力が

4 4
.#.#
#.#.
.#.#
#.#.

str内ではこうなります。

######
#.#.##
##.#.#
#.#.##
##.#.#
######

このライブラリを正しく使用すれば、配列外参照を起こさなくなります。
自分に合ったライブラリを作成して、コンテスト開始前から優位に立っていきましょう。

★目標を上げる

私はレート1200を目標に長らく競技プログラミングに取り組んできましたが、
パフォーマンス1200をずっと取り続けたとしても、レートが1200になるまでは時間がかかる
ことに気付きました。
仮に目標とするレーティングの数値があるのであれば、
目標とする平均パフォーマンスはその数値よりも少し上に設定することがおすすめです。

★IDEを導入する

100回コンテストに参加しているうち、前半の80回程はprintfのみでデバッグを行っていました。
IDEのデバッグは非常に強力です。
緑上位(レート1000)以上を目指すなら導入することをおすすめします。

★コンテスト(ABC,ARC)に毎回出る

私はコンテスト時間中の集中度合いとコンテスト外で過去問を埋める時の集中度合いが大きく異なる
ため、コンテストに数多く出て深く集中する時間を増やしました。

★Codeforces(Div2,Div3)に出る

同じくコンテストに多く出てより深く集中する時間を増やしました。
また、AtCoderのレートが伸びない時でもCodeforcesのレートは伸びて青色になったこともあり、
競技プログラミング自体のモチベーション維持に役立ちました。

★バチャに出る

好きな過去問を好きな時間に埋めるという行為は時間に追われないので、
コンテスト中とはかなり条件が異なります。
バチャに出ることで制限時間のある環境での練習ができます。

生活習慣を固定する

コンテスト開始5分前に目覚めて、コンテスト中に全然頭が回らないことが何度かありました。
検討の結果、コンテストのある日は14時に起きて18時までに夕食を済ませ、
20時前にエナドリを飲み、21時前まで運動して血圧を上げてコンテストに参戦するという
謎の専用ルーチンが完成しました。
ここまでする必要はないと思いますが、
少なくとも20時前後には起きていた方が良いパフォーマンスが出ると思います。

Google Chromeの拡張機能を入れる

入れるだけでパフォーマンスが上がる拡張機能があると私は思っています。
AtCoder Clansで自分に合ったものを見つけましょう。

Twitter

自分と同じくらいのレートの人をフォローすると、モチベーションの維持に繋がります。
コンテスト後に自分が想定しなかった解法をつぶやいてくれることも多く、学びがあります。

4.参考

水色になった今の私が大体理解しているアルゴリズムとデータ構造


全探索	二分探索	深さ優先探索	幅優先探索
動的計画法	ダイクストラ法	ワーシャルフロイド法	クラスカル法
高速な素数判定法	べき乗の高速な計算	逆元の計算	累積和・いもす法
座標圧縮	半分全列挙	最大流	最小カット
グラフ理論	木	Union-Find	セグ木

水色になった今の私が理解していないアルゴリズムとデータ構造


行列累乗	ダブリング	Grundy数	Rolling Hash
平方分割	二部マッチング	二部グラフ判定

5.おわりに

記事を書き終わって気付きましたが、
実力UPに強く効果のあるものはやはりどれも時間がかかりますね。
AtCoder 青色を目指す気になったら帰って来ますので、その際はまたよろしくお願いします。
最後までご覧いただき、ありがとうございました。
それでは皆様、良い競技プログラミングライフを。

社会人1年目がAtCoderで水色になるまでにやったこと