どうもエンダーヒムふるカウDDアニです。トイコンは50強！ｗ *1 ←これ書いた日にトイコンクリアしました。やったね。
というのはおいといて……みなさんお久しぶりです，おはようございます！ヾ(❀╹◡╹)ﾉﾞ❀ つまぶきとボム兵とロトムが好きな Мороже……いや，amebicComber と申します。衝撃的なことになんと，この記事はこのブログで初のドイツ語以外のトピックの記事です……！*2
本題です。このたび AtCoder で水色になりました。やった～🎉🎉🐈🔋
やってなかった時期を含めるとだいたい 1 年くらいかかってますね。1 年で水色になれるみたいな話はよく聞くのでわりと普通な気もします。そういえばプロフィールとかには書いてないけど AtCoder だと amebicComber っていう名前なのでよろしくお願いします。*3
ここから雑に僕の競プロ人生を振り返ります。たまに強い主張がありますがあまり真に受けないでください…><
おことわり
この記事はクソ記事です。ポプテピピックでも読むような気持ちで読んでください。
始めたきっかけ
2 年くらい前の僕はプログラミングや情報科学についてほぼ全く知らず，競技プログラミングについてもどういうものか全くわかっていなくて，競プロerは全員めちゃくちゃ知能の高いガチプロだと思っていました……（今でも上位勢に関しては同じような認識です）
そのときは簡単な JS が書けるくらいで，いわゆるアルゴリズムもほとんど知りませんでした。たぶんその時知ってたのユークリッドの互除法くらいか……？
2017 年 11 月のある日，そのとき僕はたまたまとある緑コーダー(今はその人は青)の家にいて，目の前で ABC079 を全完するところを観測していました。*4
地味に昨日，目の前でABCが解かれているようすを見学していた
— 🍨卵生 Мороже💣 (@Morojenium) 2017年11月19日
ABC079 はたまたまかなり軽めの問題セット（…いや，最近のがおかしいだけ？）で，氏がすらっと全完するのを見てしまい， 「えっ，これなら僕でもできるのでは…？」 と思ったのです。
しかもコンスタントに ABC 全完できるならすぐ水色になれるみたいな情報もその後聞いたので，「じゃあ水色くらいならすぐなれるかも！」って思ってアカウントを取得，AtCoder を始めました。
……まぁ，はい，お察しの通り，そんな簡単になれるものではありませんでした。厳しいね。
道のり
始めてから 2 ヶ月ちょいくらいで ABC088 を全完して緑一歩手前(772)になりました。パフォは 1454，まぁこれ数日前に書いたコード引っ張ってきただけなのでたまたまなんですが……
この調子だったら緑にさっと昇格できるはずなんですが，現実は厳しい。全完どころか普通に C が解けない…！特に ABC089-C とか ABC102-C とかの回は B までの 2 完で普通にレートが暴落して緑行きを阻止されたのを覚えています。
緑になってからも ABC112-C とか ABC113-C が解けなくて 2 完やらかしたりしました。
ABC で 3 完できるなら水色に上がれると聞きますが，C まで書けてもレート落ちるときは落ちますし，上がったとしてもよほど速く解けてない限りそこまで上がらないので，体感的には「C までを速く解けてかつ ABC-D(400) がコンテスト中に通ることがあれば水色になれる可能性がある」くらいだと思います。
水色に上がれない
0AC でも WA が出ているとレートが下がることを知らずに大暴落した回とかもあったりしましたが，緑になってからは割と ABC 全完もたまにしつつコツコツレートを上げて，ABC116 でレートが 1175 になりました。
1175 って水色目前に見えるじゃないですか。僕もそう思っていました。
なにこれ？
強く生きる
それでも強く生きることは大事です。
配点を見ての感想
— chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) 2019年3月30日
茶：２００まで早く解こう！ミスらないようにテストはちゃんとしようね！
緑：強く生きて！
水・青：CDEのどれかを頑張って解いてみよう！
黄：CDEまで解こう！
橙・赤：全部解いて！
エクサウィザーズ2019 で強く生きた結果，制限時間をめいっぱい使って手慣れない実装をなんとか完成させ，コンテスト中に 500 点を通して青パフォを出し水色にようやく上がることができました🎉 これ XXOR とか Match Matching より簡単だから 400 でよくね？
ということで皆さん強く生きましょう。*5
int でオーバーフローして 400 点を逃したり，0 のときに -1 して mod 109 + 7 してコーナーに引っかかって WA を吐いたり，日本語が下手すぎて A 問題 で 2 WA 出して 20 分かけたり，音ゲー中に謎の感覚過敏をいきなり発症して死にかけたり，L-an!ma を逆ボしたり，EFFCH の提出が 5 秒くらい間に合わなかったりしても，どんなことがあってもとにかくちゃんと生きることは大事です。あと睡眠を取りましょう。
やってたこと
コンテストに出て復習する
コンテストに出るのはみんなやってると思うけどちゃんと復習もしましょう（やる気があるうちに）。解けなかった/解かなかった問題もできそうならちょっと粘って考えるようにしました。
ちなみに偉そうに言ってるけど僕もそんなに実行できてないです。ちゃんと復習したい。
バチャコンを開く
一人でバチャ開いて過去の問題をちょっとだけやってました。あと自習スペースを使って同じ大学の友人たちとちょっと古めの 100-200-300-400 を やってました。といっても 10 回くらいしかやってませんが……
まぁ目の前で近い地力の人が参加してるので普通に盛り上がるし，終わったあとに解説をその場でしたり・してもらったりできるしでわりと学習効率がいいと思います。
実際に書いてみる
これこの記事で一番言いたいこと！理解はしていても，実際にやってみるとバグらせまくって全然書けなかったりします（手書きの二分探索とか）。
とくに「存在は知ってるテクだけど書いたことないやつ」はそのテクを使う問題をいくつか引っ張ってきて高速で書けるように練習しましょう。ちなみにこれは自戒です。
ポイント(典型テク？)をまとめる
高校数学の美しい物語の勉強法のページの 2. で紹介されている方法です（ぜひ見て）。onepoint.txt みたいなものをすぐ開ける位置に作っておいて，問題を解く過程で教訓が得られたり，ちょっとしたミスで WA を出したりしたら，内容を抽象化してメモします。たとえば「MOD の引き算は気をつける」「区間が出てきたら累積和を疑う」「accumulate の 第 3 引数は ll なら 0ll を入れる」「真偽値の二分探索は常に true のところと常に false のところをまず考える」みたいな感じです。これをあとからたまに見返したりすることで身につけたものを確実に覚えておけるようになります。
海外コンに出てみる
一回だけ Codeforces に出ました(Div2 のえでゅふぉ)。C が普通に難しくて A, B の 2 完。多分 300-300-500-500 みたいな感じ……？AtCoder と違って実装するコードに対してやたら問題文が読みにくかったのは覚えてて，あとコンテスト中になんか 5 回くらい оповещение が出てやたら怖かった……。累積和は префиксная сумма というらしい。
使った知識・テク
水色になるまでに使った知識・テクを僕自身の復習も含めてまとめました。
各テクについてそのテクを使う問題へのリンク（一部提出コードのリンク）を貼っています。ぜひ練習に活用してください。ネタバレがダメな人は迂闊に押さないようにしましょう。
全探索
王道。あまりに王道過ぎて存在を忘れてこういうのでパニクりがちです。（僕だけ……？）
特に ABC で制約が小さい場合はすぐに全探索を思い出しましょう。
再帰関数による DFS，メモ化再帰
指数時間による列挙，グラフの探索，あと二項係数とかに使えます。定番とよく言われますが僕は再帰の感覚がうまくつかめず，最近になって再帰を 10 個くらい書いてようやくそれっぽくかけるようになりました……。
bit 演算
bit 全探索やフラグ管理で使います。一応 bitset も覚えました。
コンテナクラス(vector, map, set)関連
map は問題によってはかなり便利。これに限らず標準のライブラリとかに頼ると楽なことが多いので，使えそうなものはぜひ覚えよう！
一次元累積和，二次元累積和，imos 法
ある問題で累積和が思いつかなくてつらい気持ちになって以来，区間が出てきたら真っ先に疑うことにした。ほかにもクエリが与えられて各区間クエリについてなにか求めるみたいなやつとか，前処理で累積和を求めておいて全探索の過程で累積和の結果を使うみたいなやつとかがある。
二分探索
手書きのものと lower_bound の両方の書き方を覚えました。 値の検索や真偽値の境目の探索に使います。かなり使うイメージ。
ちなみにコンテスト中に通した 500 点は 3 つあって，2 つは二分探索でした。
整数問題関連
「約数は √N まで調べればいい」が分かっていると 300-400 の整数問題はたぶん解けます。ただし若干バグを埋め込みやすい気がするので注意。高校数学でやる「ax+by=c が整数解を持つなら c は g = gcd(x, y) の倍数（つまり c は g の倍数の中でしか動かない）」もたぶん使う機会があって，この問題とかはそれが本質だった。あと mod が扱えると見通しが良くなったりする問題もあったりします。
xor
drafear さんがよく出してるイメージが大きいです。一度遊んでみて感覚を掴みましょう。あと簡単なブール代数の知識があるといいかもしれない。
数学
実質数学コンテストみたいなことはよく言われていますが，実際ただの中学数学とか，数学をすることで O(1) にできる問題があったりします。（よく DEGwer さんがこういうの出してる気がする）
特に数A力があると期待値などの問題でアドです。
Union-Find
たまに出てきます。さすがに出てくるたびに毎回ゼロから組むのは苦痛なので，自分で一度組んだらアクセスしやすい場所に保管しておきましょう。AtCoder Typical Contestで学習できます。
知っていたがコンテスト(バチャを含まない)で使わなかったもの
全然使わなかった知識・テクです。多分そこまで気にしなくてもいいやつ。
DP
なんとコンテスト中に DP を一度も通したことがありません！！（←？） またこのくらい簡単なやつ出てくれないかな…
簡単なナップザックとかなら書けますが添字が多くなると混乱して書けなくなるのでダメ，しばらくは重点的に DP を練習したいと思います。
ワーシャルフロイド，ダイクストラ，ベルマンフォード
最短経路アルゴリズムはおそらく定番ですが最近意外と出てないみたいですね。蟻本の説明がわからん……
Kruskal 法，Prim 法
時々使えそうって問題に出会いますが一度も書いたことがない……蟻本の説明がわからん……（2 回目）
しゃくとり法
なんか O(N) の強いやつ。バグらせやすくて怖い
正規表現
多分どっかで使えますがまだ使ったことないですね……
priority_queue
寿司食べたい！
BIT
実はとある 400 点問題 でコンテスト中に思いついた解法が BIT を使うもので，そのときに使いこなせる地力もなかったのでそのまま沈没したという話があります。はい。ちなみに後日無事 AC しました。
セグ木
ついでに書きました。でもまだ 1 年くらい使わなさそう
半分全列挙
これで使えるらしい……
さっきから目の前にいる緑コーダーに「Cは教科書にも載ってる」ってめっちゃ煽られててしんどいhttps://t.co/I0IPtHuxyI
— 💣卵生ホエール🐳 (@323O65281) 2018年8月11日
まとめ
たくさん解いた上で典型っぽい流れは素速く書けるようにしましょう。多分新しいものを無理して身につけるよりも書けるものをちゃんと書けるようにすることが大事だと思います。（これは完全に自戒）
あと QuoN 乱とかヴェラム乱をやりましょう。カメレオン乱も楽しいのでめちゃくちゃおすすめです。
ちなみにこの記事を書いてる途中でパソコンがめちゃくちゃ重くなってやる気を無くしたため後半から少し雑になっています。ごめんね。*6
↑ 直感的に HDD がヤバそうだと思ったのでシステムの復元しようとしたら「復元ポイントが壊れているので実行できません」とか言われて死ぬかと思ったけど，chkdsk してなんとか一命をとりとめました。いまはサクサク動いています。本当に良かった…！
ここまで読んで頂きありがとうございました。(⋈◍＞◡＜◍)。✧♡*7
(von amebicComber geschrieben)
