[AtCoder] 入緑しました！

はじめに

　入茶から1年が過ぎ、ようやくABC363にて入緑しました。

　入緑まで2回の停滞がありました。この停滞を取り上げて、やったことを振り返ります。(時期とレートはだいたいですのでご了承ください)

1回目の停滞(12月 / レート650→600)

　緑パフォを出したり、灰パフォを出したりするなど、かなり不安定な時期でした。不安定ではあるもののレートは650くらいまで伸びていたので、レートが自分の実力より偶然高く出ていることに気付けませんでした。

反省点

　正直に言うと、特になにも考えていませんでした。興味があるアルゴリズムを勉強して、とりあえずC問題までを埋めていました。アルゴリズムを知っていて素直に実装すればいい問題や、AtCoder Problemsで解いた問題の類題が解けているだけでした。
　計算量を落とすために、どの部分は必要でどこなら改善できそうか、どうやってアルゴリズムに落とし込むかみたいな視点が完全に抜けていました。

精進内容

• AtCoder Problemsで過去問を解く
• アルゴリズムとデータ構造の勉強(Qiitaの記事や蟻本)

具体的な対策

以下の3点に注目して、WAした問題を中心に整理した。

1. 問題の解釈
   　問題を正しく解釈しないと、適切な方針が立てられないので、何を意図した問題なのかを自分の言葉でまとめました。かなり面倒です。
2. 方針
   　詳細に記述することで、解説を読んだ時に、そもそも方針はあっていたのか、方針を立てる際に注目するべき箇所はあっていたのかなどが分かる。これを怠ると、解説を読んだ時に、分かった気になってしまいます。
3. 実現する
   　方針が正しくても、その実現に必要なことを頭の中から正しく引き出せないと解けない。(ex. ダイクストラ法 : 仮の最短距離がいま見ている最短距離より小さい場合はcontinueするを書き忘れるとTLEしてしまう)

効果

　アルゴリズムとデータ構造をただ知っているという状態から一歩抜け出せたと思います。あと、解き方という意味ではずいぶん引き出しが増えたなと感じました。答えを二分探索で決め打ちしたら解けるくね？とか、逆からやればいけそうとか、そんな感じです。

2回目の停滞(6月 / レート750→700)

その後、順調にレートは伸びましたが、かなりの遅解きで、思うようなパフォーマンスはなかなか出せませんでした。(AtCoder Type Checker)

反省点

　本番想定の精進をしていませんでした。AtCoder Daily Training(以下、ADT)を時々活用していましたが、回数が圧倒的に少なかったと思います。

精進内容

• AtCoder Problemsで茶diff埋め
• アルゴリズムとデータ構造の勉強(Qiitaの記事や蟻本)
• バーチャルコンテストに参加

具体的な対策

　バーチャルコンテストに参加し、終了後、YouTubeにある実況動画を観ました。周りにAtCoderをしている人がいないので、実況動画の存在は本当にありがたいです。理由は、自分よりレートが上の人がどれくらいのスピードで問題を解いているのかイメージできるのと、解き方が分からない時にどうやって対応しているのか分かります。また、ただバチャをやるよりも、今日はこの人に負けないぞと思いながらやると本番っぽくて効果があるような気はします。順位表があるので、これは気持ちの問題ですが...
　あと、他の人のコードを見るのはかなり大事だなと感じました。ABC363に関連して例を挙げてみます。

// A問題
int R;
cin >> R;

// 問題文の通り素直にやる
if(1<=R&&R<=99) cout << 100 - R << endl;
else if() ...
else if() ...
else ...

// ちょっとラクする
if(R<=99) cout << 100 - R << endl;
else if() ...
else if() ...
else ...

// うまくやる
R%=100;
cout << 100 - R << endl;

// B問題
// 直観的に分かりやすいので間違えない
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

for(int r = 0; r < 4; ++r){
    int nx = x + dx[r];
    int ny = y + dy[r];
}

// コードは短いけど慣れてないとミスしそう
int d[5] = {1, 0, -1, 0, 1};

for(int r = 0; r < 4; ++r){
    int nx = x + d[r];
    int ny = y + d[r+1];
}
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

// 直観的に分かりやすいので間違えない
int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};

// 実装がラク(どれが上移動で...とか考えなくていい)
for(int dx = -1; dx <= 1; ++dx){
	for(int dy = -1; dy <= 1; ++dy){
        int nx = x + dx;
        int ny = y + dy;
	}
}

// E問題
// すでに訪れた箇所をどう管理するか

vector<vector<bool>> vis(H, vector<bool>(W))
if(vis[i][j]) continue;

set<pair<int,int>> st;
if(st.count(make_pair(i,j)) continue;

　最終的に、自分にとって分かりやすくて間違えない、書きやすいものを選択して、こういう場合はこう書くと固定すれば、かなりスピードが速くなると思います。

効果

　コードを書くスピードがかなり速くなりました。あと、1回目の停滞の時の対策で書いた、実現するというところで言えば、頭から引っ張り出すまでのスピードも速くなったと思います。

おわりに

　あまり触れませんでしたが、アルゴリズムとデータ構造の勉強は、基本的に問題が解けなかった時に必要なところだけ確認しました。トポロジカル順序が結構苦手だったので、そこは定期的に確認していました。あとADTは実況動画がないので、そんなにやってないです。
　今は緑埋めを中心に精進しています。アルゴリズムを組み合わせて解いたり、解説を見てこういう風に解けるんだと感心したり、やればやるほど面白いなあと感じています。水色目指して頑張るぞ！！