AtCoder緑になるまでにやったこと

色変のタイミングで書くようなことを、緑になってから半年間、Highest900を超えないまま緑と茶色を行ったり来たりしてる現状で書きます。

### AtCoder参加前
競技用の勉強は全くといっていいほどやってなくて、GoogleCodeJamはQualificationRoundは通過できるレベル。
PaizaはぎりぎりでSにはなってた。ちなみにPaizaは今こんな感じ
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/911987/d41b5fd1-c89d-979a-ba90-1f99f465a823.png)
※Sランク問題を他言語に翻訳して再提出することで言語マスターは埋まるぞ！！

### AtCoderのコンテストに参加し始めてから
5回で茶、20回で緑だったそうで、
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/911987/1c9c98db-588b-fd8a-b8b0-4595f3350f36.png)

AtCoderProblemsによると、緑になるまでで過去問含めて約150ACだったそうです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/911987/3fb31f3f-75d3-cab2-e3a8-e6d5d72c2fac.png)
現在約420ACくらいだけど、この間で全然成長できてないっぽいですね。
まあ、灰色diffの問題をやってもあんま意味ないレベルなので茶色と緑合わせて100くらいしかやってないと読んだ方がいいか。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/911987/3b164c12-4de0-addb-8dd0-34c69b42ebbc.png)

参加者全体のレベルアップも恐らくあり、赤の女王仮説みたいな感じですかね。走り続けてやっと維持できる状態。


### 緑になるまでで使ったアルゴリズムとデータ構造
参考 ： https://qiita.com/e869120/items/eb50fdaece12be418faa

- 全探索
    - bit 全探索
        - スイッチのオンオフなど、二値の組み合わせの全パターンを試す時用
        - スイッチ20個までなら10^6パターンしかないので、いけると思う
    - 順列全探索
- 二分探索
    - 自力で実装できるに越したことはないが kotlinでやる場合、```List<T>.binarySearch()``` を使えるはず
        - ソートしてからじゃないと使えないので注意
- 深さ優先探索（DFS）
    - 順列の全探索とかでも使うので要理解
- 幅優先探索（BFS）
    - 迷路の経路探索の問題が出た場合ほぼこれを使う
- 動的計画法（DP）
    - 色々あるので典型問題の反復練習が必要
- 高速な素数判定法
- べき乗を高速に計算するアルゴリズム
    - Kotlin や Java の math.pow は、IOがdoubleなので、誤差が出る可能性がある。整数用を用意した方が良い
- 組み合わせの求め方
    - アルゴリズムというか単なる数学の範囲になるけど、結構使う
- 逆元を計算するアルゴリズム
    - 答えを「10^9+7」で割った余りで求められる問題で必須なので、modintライブラリを用意しておいた方が良い
- 累積和
- 木
- Union-Find

DPはそれなりにできるけどパターン多いし完璧ではない。セグ木は400点問題までで使うことないでしょう、たぶん。
あと、「ソートしてから累積和」みたいな複合的なのは、個人的にはすぐ思いつける日とそうでなくてハマる日があり、その日の睡眠や食事で結構調子が違う。

茶色までだとDPとかUnion-Findは必須ではないかもしれないけど、Union-Findを使う問題が出る場合、ABCのDの問題ならコピペするだけで解けるレベルの問題の可能性が高いので、理解してライブラリを用意しておいた方が良い。
AtCoderのC++用ライブラリで色々簡単に使えるようになったので、Union-Findが使えないのは不利。


### コードスニペットの準備
IntelliJだとライブテンプレートと言われてる奴（メニュー File > Settings > Editor > Live Templates）
問題読んで意味を解釈する間に、入出力の例を見て、入力だけはざっと書いてしまいたいと思っている。ので、そこで頭を使わないで済むようにスニペットに色々登録しておく。
こんなの用意しても数秒の差だけど、モタついて得することはないのでやっておく。

#### 入出力
入力のパターンはそんなにないので、
 ```val $PARAM1$ = readLine()!!.split(" ").map{ it.toInt() } ```  
 ```val ($PARAM1$, $PARAM2$) = readLine()!!.split(" ").map{ it.toInt() } ```  

みたいなのを何パターンか用意して、問題によって使い分ける。N行入力取ってListにするのとかもあると良い。自分が過去に提出したコードから拾ってスニペット化する。
出力も ``` println( if(flg) "Yes" else "No" ) ``` こんなのとかを少し用意しておくと使えるかも。


#### main
```
import java.io.PrintWriter
@JvmField val _writer = PrintWriter(System.out, false)
fun main() {_writer.solve(); writer.flush() }
fun PrintWriter.solve() {

}
```
こんなのを用意しておいて、solve()の所に具体的なコードを書く。
これを書いておくとAutoFlushされないようになるので、出力がN行あるタイプの問題だと出力の速度に若干の差が出る。
（これをやってるかやってないかでTLEになるかならないかの差までは出ないはず。多分）

### コンテスト中に意識すること
#### 制約を見る
ループの回数はだいたい 10^7 以内になるようにしたい。N や M の制約に応じて、概ね以下のような対応を考える

- 10^10
    - この回数のループは不可能
    - 計算式一発でいける系の問題の可能性を強く感じる
    - √N や logN ならいけるが、果たして…
- 10^9
    - この回数のループは不可能
    - 計算式一発の可能性もある
    - √N や logN なら可能
- 10^7
    - 軽い処理でN回ループならあり得る
    - ループ内で重い処理が要る場合、重い処理を外に出せたりするかも
    - ソートしたら途中で終われるかも
- 10^6
    - この回数のループ1～2回で処理するはず
- 2*10^5
    - この回数のループなら2～3回やってもセーフ
- 10^4 以下
    - これは全探索してもいける

参考 ： https://algo-logic.info/how-to-think-cp/

#### 提出前
最低でも入力値が N だけの場合は制約の最小と最大くらいは試したい。最大値を入れて2秒以上かかるようなコードでは絶対無理なので。
また、たとえば

```
N
A1 A2 … AN
```
こういう入力でNが10^6とかのときは最大値を手入力で試すのは不可能。できればツールを用意した方が良いけど、茶色までならまあ…

#### CEが出たとき
AtCoderは優しいのでコンパイルエラーはペナルティに含まないんだけど、まずそのレベルであればローカル実行かAtCoderのコードテスト機能を使って一回動かす。
一回も動かさずに提出して、コンパイルエラーが解消できてもし動いたとしても想定通り動くと思えるか…？

#### TLEが出たとき
制約を見直す。あたりまえだけど何か見落としてるかも。
「いや、この制約なら間違いなくいけるはず」でTLEが出た場合、ループの終了条件をすり抜けて無限ループになるパターンがある可能性あり。

#### WAが出たとき
ここでもやっぱり制約を見直す。たとえば計算の途中で10^8*10^8が含まれうる場合、32bitIntでは収まらないためオーバーフローしてるかもしれない（TLEになる無限ループもこれで起こり得る）。
落ち着いて分岐条件を見直す。「<」と「<=」の違いや、「>=」と「>」の違いでしくじってるかも。
配列の添え字でミスってないか見直す。実装の途中で配列の使い方を変えたときなんかに修正漏れがあったかもしれない。座標の縦横が逆転してたりするかもしれない。
条件の見落としや思い込みなどはないか見直す。安直に「～が3以上のパターンはないな」などと思い込んで実装したけど実は3以上になるパターンもあるとか、N個あるAがソートされた状態で入力されるかソートされてないのかとか、いろいろ。
ここまで見直しても大丈夫っぽく見える場合、変な動きをしそうな特殊なケースを頑張って考える。とにかく頑張って考えるしかないが、こういうの考えられる奴が実務でも強いのでこういうところこそ頑張らないといけない。


#### どうしようもなくなったら順位表を見る
1時間経った時点でハマっている場合、順位表を見て「あれ？今回CよりDの方が簡単なのかも」みたいな逃げを考える。
自分とレベルが近くて参加頻度が高い人をお気に入りに入れて監視するとやりやすい。

#### tourist出し（もどき）
今、世界一強い競技プログラマーで tourist という人がいます。GoogleCodeJamも5連覇とかしてて圧倒的に強いです。
この人は、全ての問題が解けた時点で一斉にすべての解答を提出して、突如1位に現れるというプレイスタイルを持っていて、そのような提出は「tourist出し」と呼ばれています。
AtCoderでは、参加登録を行って、リアルタイムで問題を見ても1回も提出しなければレート変動はありません。たとえば「今の自分のレートならDまで解ければ上がりそうだけどCまでだと微妙だな」と考えたとき、「Dが解けなかったらAもBもCも出さない」とするのも一つの手です。
ただし、この方法だとA～Cの提出は送れるので、タイムによる順位は下がる可能性が高く、その上Dを一発ACできなかったらかなり悲惨なことになる可能性があることに注意してください。


### おわりに
平時の練習で素振り的な基礎練習の一つもしないプロスポーツ選手は多分いないわけですが、（年俸何千万ともらっているわけではないとはいえ）プロプログラマーが平時に練習として素振りめいたことを実施するなら競技プログラミングが一番シンプルでやりやすいんじゃないかなと思います。
まあ、具体的に作りたいものがある場合はそれを作った方が良いと思います、その方が楽しいし。