はじめに
みなさん色変記事は好きですか？ 僕は好きです
いろいろな人の、勉強方法・考え方・小ネタ・よくわからないものなど、読んでいてためになったり、そうでなくても面白いですね
ということで、このたびAtCoderのレーティングが1600を超え、ついに青コーダーになることができました！
という色変記事を書きたくて少しずつ書き溜めていたのですが、レートが伸びなくなってしまいました。
年内のコンテストも終わり、モチベも少し落ちてきて、いつになったら完成するのかわからない下書きを溜め続けるのにも疲れてしまい、もうめんどくさくなったので公開することにしました。
追記: 現実になりました！
自己紹介
大学生（理学部）です
PCを手に入れたのは大学生になってから（＝競プロもそれから）
コンテストではだいたいC++を使っています
VSCodeでコーディングしています
repの人です と言ったら伝わる人はいますか？
AtCoderを知るまで
僕は音楽ゲームが好きだったのですが、Twitterで音ゲーマーなフォロワーさんがたまに競プロ関連のツイートをしていて、それで初めて知りました。しかし当時高校生な僕はPCを持っておらず、さすがにスマホでやるわけにもいかないと思いスルーしていました。
その後ぷよぷよというゲームに興味を持つなどしたのですが、競プロerなぷよらーさんも結構いるんですよね。そんなわけでTwitterから競プロのことを知り、オタクならだれもが持つ「プログラミングやってみたい！」という気持ちもあり、大学に入学してノートパソコンを買ったということで始めてみることにしました。
これまでの紆余曲折
黒コーダー
登録
僕が黒コーダーになったのは大学一年生の春 2019-04-29、ゴールデンウイークというやつですね。みなさんゴールデンウイークには何をするんでしょうか？旅行？友達と遊ぶ？バイトや仕事の方はお疲れ様です。僕は、家に引きこもっています。そんなわけで、ある程度まとまった時間があったわけですね。いい機会だということで、AtCoderに登録してみることにしました。黒コーダーになりました！
同じ学科の人を軽く調べてみましたが、競プロerは見つかりませんでした...
初めてのプログラミング
とはいえ、それまでプログラミングの経験は０、C++ってなに？です。"Hello World!!"をすることすらできません。 そんなわけで、APG4bをすることにしました。29日の15時くらいに始めて、22時半くらいまでかかって L - 1.11 の問題をACしてその日は終了、次の日には S - 2.02 まで進めました。そして31日、U - 2.04 の問題をACした後に、その時行われていたコンテストに出ることにしました。
初めてのコンテスト
ということで初めて出てみたコンテストは いろはちゃんコンテスト Day2 です。なぜABCじゃないのでしょうか？案の定ぼこぼこにされました。LCSという概念すら知らなかったのでA問題はスルー、B問題は連立方程式を解いたら行けそうな感じ、分母を払って割り算もなくしたのですが見落としがあったようで39/49AC、C問題は座標圧縮をしろということですが、std::uniqueも二分探索も知らないので、頑張ってごりおそうとしましたが無事死亡、そこから先は自分なりの方針を立てることもできず、コンテストは終了。5ペナ0完という散々たる結果となりました。
次の日、APG4bを少し進めて、懲りずに いろはちゃんコンテスト Day3 に特攻、A問題の問題文が長くて嫌になりました。とりあえず書いてみるもWA、ほかの問題を見てみるとE問題がなんとなくできそう、バグらせまくりつつ頑張って実装して初めてのAC、運がよくて I 問題を一発ACしてコンテストは終わりました。初めてACを得ることができて、とてもうれしかったことを覚えています。
いろはちゃんコンテスト Day4も参加はしたのですが、テーマは "BossRush"ということで全く歯が立たず、すぐに諦めました。
初めてのABC
少し飛んで 2019-05-19、ついに初めてのABC、AtCoder Beginner Contest 126 です！当時知りませんでしたが令和初新生ABCだったようで、ちょうどいいタイミングだったのかもしれません。CEやWAを量産しましたが結果は3完、Dに木という謎の単語が出てきて混乱しつつコンテストは終了、解説放送があるということで、YouTubeを見に行きました。初めてのsnukeさんです！初参加の記念に というスパチャを投げてみると、Unratedになってしまい申し訳ない と謝られてしまいました。そう、ジャッジトラブルのためUnratedとなってしまった回です。あまり気にしていませんでしたが、Unratedになった影響で僕の黒レートはもう少し続きます。
初めてのrated
次のコンテストは 2019-05-25、AtCoder Beginner Contest 127 です。A,Bを通し、C問題、愚直にやってみるもバグらせていてWA、バグを取ってみるもTLE、何とか高速化を考えるもやはりバグっていてWA、何とか修正してついにAC！3ペナを出しつつも何とか3完、茶色パフォを出して灰色コーダーになることができました！
灰コーダー
ということでついにレーティングを手に入れることができましたが、特に何が変わったわけでもありません。APG4bはあらかた解き終わったのですが、次に何をするべきなのかということがよくわかっていなかったので、週末のコンテストに出る以外のことはしませんでした。要は、そこまで競プロにハマっていませんでした。
精進をしていないのでDPを知らず、ABC129-Cが解けなくて灰色パフォを出してしまったり、divertaさんの1完早解き大会（ごめんなさい）でなぜか緑パフォが出たり、初期なのでパフォーマンスがブレブレでよくわかりませんでしたが、とりあえずは「データ構造とアルゴリズムはわからん！数学は頑張る！」という典型的な理系競プロerだったのではないかと思います。とはいえAtCoderでよくいる数学つよつよマンさんたちほど数学ができるわけでもないので、だいたい茶色、よくて緑パフォという程度でしたが、まあ当時そんな世界を知らない一般灰色コーダーだった自分としては、レーティングが狭義単調増加しているだけで満足でした。
そんなわけで迎えた AtCoder Beginner Contest 133、A,B,C,Dすべて数学寄りのセットを引き当て、四完して1097パフォ！初めての四桁パフォという大成功とともにレーティング+149、茶色コーダーになることができました！
茶色コーダー
ここまでで10回くらいのコンテストを経験して、少しずつ競プロに慣れてきました。（ほんとか？）
相変わらず特に精進はしませんでしたが、数学問題をしっかりとって、700～1000くらいのパフォーマンスを連続で取り、なんとなく「このまま緑コーダーまでは行けそうかな～」とか考えていました。精進をしなさい。
しかしここで悲劇が起こります。AtCoder Beginner Contest 137、僕はC問題をACすることができず、結果は二完、茶色パフォは出ましたが、レート643に対して552パフォ、初めてレーティングが落ちました。特に努力をしてこなかったにもかかわらず、とても落ち込みました。
引退
そしてモチベーションを失ってしまった自分は、AtCoderを引退しました。今までありがとうございました。
復帰
まぁこうして記事を書いているということはでその後復帰をしているんですが、そこから約五ヵ月もの間、自分はAtCoderから離れていました。ガラスのハートにもほどがあるだろ！という感じですが、もともとそこまでハマっていなかったということと、当時僕の音ゲーモチベが高く休日の夜はゲームセンターにいたりしてコンテストと時間が合わなかったということもあり、結果として五ヵ月もの期間AtCoderをしていませんでした。今にして思うとあまりにも勿体無いという感じですが、まぁ仕方ありません。
引退前最後に出たコンテストが2019-08-10のABC137、そして復帰後最初に出たコンテストは年を越して2020-01-12の AtCoder Beginner Contest 151 です。ブランクがあったのでかなり不安だったのですが結果は三完で緑パフォ、何とかなってしまいました。
このころから、自頭だけでの挑戦に限界を感じました。（それはそう）
ということで、精進、というほどでもないですが、アルゴリズムの勉強を少しずつ始めました。
ここまで出たコンテストで解けた問題の次の問題ではグラフの問題が多かった印象があったため（なにも理解できなくて絶望したため印象に残っていた）、グラフ関連のアルゴリズム（DFS、BFS）をとりあえず勉強しました。いろいろな記事を見て全然理解できなくて挫折しかけて、最後に辿り着いた けんちょんさんのQiita のおかげでなんとか理解できたり、あとは 累積和 について勉強したりしました。
その甲斐もあり(？)四回ほど緑パフォを連続し、レーティングは793になりました！
これは緑コーダー来たか！？と意気込みつつ次のコンテストは 悪名高い パナコン です。Twitterでトレンド入りも果たした トラップは何とか乗り越えたのですが、B問題のコーナーケースに弾かれ、焦りに焦って4WAを出しましたが結局見抜くことができず、A,Cの二完で茶色パフォ、緑レート直前にして叩き落されてしまいました。
そしてモチベーションを失ってしまった自分は、AtCoderを引退しま
せんでした。いくら音ゲーマーだからと言ってそんなにポンポン引退したりはしません。音ゲーは引退しました。
今回は僕のガラスのハートも持ちこたえてくれて、ちゃんと次のコンテストに出ました。次のコンテストはABC159、パナコンの失敗を思い出して胃が痛くなりつつも、何とか四完して緑パフォを出すことに成功、落ちた分のレーティングを取り戻し、レート797になりました。なんでそんなギリギリで止まってしまったのでしょう。
そして迎えた AtCoder Beginner Contest 160、なんと初めての五完を達成！1497パフォです！ 初めての水色パフォを出すとともに、緑コーダーになることができました！
緑コーダー
さて、緑コーダーになれた僕ですが、ちょうど三月ということで大学も春休みになり、もう少しまじめにAtCoderに取り組もうという気持ちになっていました。とはいえ、大したことをしたわけではありません。みんな大好きkenkooooさん の AtCoder Problems にはRecommendation機能というものがあります。Easy, Moderate, Difficult の三段階の難易度から、おすすめの問題を表示してくれるというすごい機能なのですが、これらの三段階の難易度からそれぞれ一問ずつ、毎日三問は解く、ということにしました。サボらないために、毎日やる問題をTwitterに上げていました。
それと並行して、Educational DP Contest に挑戦したり、よく使うSTLの機能を勉強をしたり、UnionFindなどのデータ構造がわからなかったりしました。
その甲斐もあってか、ABC161～168の八回のコンテストでは、青パフォ一回,水パフォ四回,緑パフォ二回,Unrated一回ということで、ある程度安定して水色パフォを出せるようになり、レーティングは1191まで来ました！またギリギリで阻まれています。
ここで、2020/5/23、第三回 アルゴリズム実技検定 が行われました。第一回、二回は参加したかったのですがうまく予定が合わず、ようやくPASTに参加することができます しかも、この回は無料です！！ AtCoderは神、無料PASTの参加は義務です 当然、リアタイで参加しました その前に、無料で公開されている第一回、第二回のバチャをしてみて、感覚をつかみます。結果は、58点と70点、中級が取れるかどうかという感じでしょうか。中級が緑色相当であると聞いていたので、水色を目指している身としては何とか中級は死守したいところです
結果は、Hを除くA～Kまでが解けて、70点、中級ど真ん中です！ HはDPをバグらせました... 次の日に一行変えたら通ったので、本当に悔しいです
結果はそんな感じなのですが、三回分のPASTにより得られた知見はそれ以上のものでした。解けなかった問題の解説を聞いたり読んだりして、いろいろなアルゴリズムやデータ構造（ダブリング、最小全域木、セグメント木など）を知ることができました。また、受験者インタビューにも参加しました。全くうまいこと話すことができずとても申し訳ない気持ちになりながらも、同じくPASTを受けた方々のお話を聞くことができ、とても有益な時間を過ごすことができました
次のコンテストは AtCoder Beginner Contest 169、人々を苦しめたMultiplicationシリーズ1～3の回です。僕も例に漏れずB問題で2WA、苦渋の決断で飛ばしてC問題、焦っていた僕はlong doubleを使った嘘解法でACを出します（本当にごめんなさい）。C問題の罠に何も気づかないままD問題へ、Multiplicationを超えたら数学が待っていました！僕のフィールド（当社比）です！ACをしてB問題に戻ります。多少余裕が出てきて冷静になってきた僕は、3分弱でACをもぎ取ります。やはり焦りは怖いですね。落ち着いてE問題、なんとこれも数学です！ACをして五完！ここまでで最高の1649パフォ、青パフォを出して水色コーダーになることができました！
水色コーダー
ついに、AtCoderを始めてから、ずっと目標にしていた（気がする）水色コーダーになることができましたが、わりとやり切った感が自分の中で出てしまいました。学校が再開して使える時間が減ったことや、Recommendationを解く精進に出てくる青diffの問題が全然解けなくて挫折しかけていたこと、単純にモチベが続かなくなってきたことなどが原因です
Difficultの問題を解くのが個人的に苦しくなってきたので、とりあえずStreakを続けるためにModerateの問題だけを解くようになりました その後、それも続かなくなりました（Moderateも青diffになってしまった）
年度が変わって後輩が入ってきたようですが、COVID-19の影響で特に会うこともなく、競プロer探しもできませんでした。相変わらずボッチです
そんなこんなであまり精進もせず、モチベもあまりない状態で挑んだコンテストでは四連続で緑パフォを出してしまい、緑レートまで下がることはなかったもののとても胃が痛くなりました
そんな中、discordで一緒にAtCoderの勉強をする仲間ができました なぜか僕のレートが一番高かったので教える側になることが多かったのですが、AtCoderモチベがとても高くなりました。やはり、何事も一人でやるよりも複数人で楽しくやったほうがモチベは続くようです
その後、青パフォを連続することができレーティングを取り戻し、AtCoder Beginner Contest 177、なんと15分で5完をして180位、黄色パフォをたたき出します！！ レートは1500を超え、念願の青レートが見えてきました！！！
しかし人生そんなにうまくはいきません。現在そこから3か月、停滞しています
2020-08-29のレート:1522
2020-11-22のレート:1522
// ToDo 何かしらの変化
年内最後のratedコンテスト、パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186） を経て最終的なレーティングは 1514 となりました
来年の自分、頑張ってください
追記: 来年の自分です。 頑張りました！
青コーダー
なりたかったです
遠いなぁ...
コンテストでの立ち回り
参加判断
時間があるなら参加しましょう 人間は弱い生き物なので、「今回はいいや...」 などをしていると、モチベなどが一気になくなってしまいます どんなコンテストに出ても冷えるときは冷えるので、冷えてしまったとしてもそういうものです
解く順番
普通にAから解いています
ABCでEやFから解く などのことはしていません
初回提出
A問題から見ていって、解けたらすぐ提出しています 一問でも解けたら、NonSubはしません
コンテストの半分くらいの時間をかけてAが解けなかったらだいたい諦めています
潜伏ということではありませんが、なんとなくtourist出しをしてみたこともありました。しかし、よっぽどマルチタスクがすごい人じゃないとあまりメリットはないのではないかと感じました WAになったときの焦りがすごい
順位表
考察が行き詰ったときに、飛ばすかどうかの判断などで見ています
それ以外ではあまり見ないほうがいいと思っています （順位表観戦コンテストが自分の中で始まってしまう気がします）
完全に行き詰ってしまった後の順位表観戦コンテストはしています
実装方針
プログラミングに詳しくないので、「これが正しい！」というようなことは雀の涙ほども知りませんが、ある程度の可読性は意識しています 関数・ラムダ式などを利用して処理の一部を切り出す などは特に多いです 変数のスコープをできるだけ狭くしたいというお気持ちで、特にグローバル変数はあまり使わないようにしています
コンテスト中以外でのあれこれ
コンテスト後
出たコンテストの解説配信は時間の都合が合う限りはできるだけ見るようにしています 解けなかった問題の解説を聞くのはもちろんですが、解けた問題でも、よりきれいな考察・実装などを見る・考えることは大切なのではないかと思います （というよりは、楽しいので見ている という気持ちも大きいです）
最近は、解説・実装を見るため が 30%、 #今日のrep をするため が 40%、 なぜかモデレーターを頂けてしまったのでスパムなどに対応するため が 20%、その他 10% といった感じでしょうか
コンテストでギリギリ解けなかった問題は、次の日には解説ができるくらい理解しておきたいと思っています
虚無埋め
Streakをつなげるため、というわけではなく単に埋めたいという気持ちで低難易度の問題を埋めましたが、力が付いた気はしませんでした。パフォーマンスも特に上がった気はしていません。（早解きのためにはなるのかもしれませんが、個人的にそちらはもともと得意だったので...）
考察力を上げたり知見を得たりするためには、しっかりと適正難易度の問題を解くことが必要なのかと思います
言語選択
自分はC++が好きなのでずっとC++を使っていますが、多分ABC-CくらいまではPythonのほうが強いのではないかと思います 書くのが楽、オーバーフローを気にせず書ける、というところなど それ以降の問題では、C++のほうが定数倍やlogをそこまで気にせず書けるので強いのではないかと思います
Java、Rustあたりも多少書けますが、コンテストで使ったことはありません
結論: 好みの問題
C++の競プロ方言・マクロ
時たま話題に上がる、 #include <bits/stdc++.h> や using namespace std;
あたりは普通に使ってます（APC4bで育ったので）
rep などのよく聞くマクロもいろいろ使っています こういうのは賛否両論あるようですが、完全個人ゲーなので好きにすればいいと思います 個人的には、v.size() をそのまま使うと size_tになっていてfor文の比較などでエラーメッセージを吐かれたりして面倒なことも多いので、最初からintにキャストしてくれるようなマクロは用意しておいていいんじゃないかと思います （まぁその辺は個人の好み）
intで済むところはintにしたいので、#define int long long はしていません long long は LL 派です
モチベの保ち方
無理です
モチベが高い時期と低い時期が、だいたい1,2週間くらいで交互にやってきます 高いモチベを維持し続けるということは僕には無理だったので、あきらめてほかのことをしています モチベが高いうちに、たくさん精進しましょう
ただ、一緒にAtCoderを勉強する仲間ができてからは、一か月ずっとやる気がでないなどということはなくなった気がします 何事も、仲間やライバルなど高めあえる存在がいるととてもいい環境になるのではないかと思います
他人との比較
仲間やライバルなど高めあえる存在がいるといい とは言いましたが、限度があります
AtCoderに取り組んでいる方々の多くが天才であり、パフォーマンスに差があったとしても過度に落ち込んだりする必要はないと思います 強い人は強いので、比較をするなら精進量など、努力がそのまま数値に現れるものにしましょう
今まで勉強したもの
色変記事では今までに勉強したアルゴリズムやデータ構造などを書き連ねるのが定番だと聞きました
しかし、何をいつ勉強して何をしていないかとか正直覚えていません
強いて言うのなら、解いた問題で必要になったものすべてと、興味を持ったものいくつかです
とりあえず僕のライブラリにあるものを並べておきます
Union Find
定番ですね 重み付き・undo可能・部分永続なども作りましたがそれを使うような問題には遭遇して (たどり着いて) いません
Binary Indexed Tree
定番ですね 1-based-index で作ったのですが、最近 ちょっと困りました。 そのうち 0-based-index に改造すると思います
区間加算クエリ対応も作りました
複雑なことをやらせるときは脳死でセグ木を生やすのでそんなにいろいろ機能はないですが、K番目を探す二分探索は割とよく使う気がするのであったほうがいいと思います
Segment Tree
定番ですね 困ったことがあったら脳死で生やします 遅延評価セグメントツリーも作りました
とりあえず二分探索は乗せておきました
Sliding Window Aggregation
定番ではないですね スライド最小値を勉強した時に、それの抽象化というノリで勉強しました
脳死でスライド最小値を書けるので割と助かっています
ModInt
定番ですね 問題文にいつもの数字が見えたりしたらとりあえず貼っています
動的にmodを変えられるバージョンも作りました
Mod上でのCombination
正直これが一番助かっています O(N) で前計算、O(1)で取得です logは定数だと思っていますが取りました
エラトステネスの篩・素因数分解
定番ですね とりあえずのものは割と前に作りましたが、AtCoderで整数問題が流行った？ときに、もうちょっとちゃんとしたものが欲しくて直しました
座標圧縮
いつもやり方を忘れるので勝手にやってくれるやつを作りました
Z-Algorithm
これ の解説にあったので作りました
使ったことはないです
Lowest Common Ancestor
何回か使いました オイラーツアーなどはまだ勉強中なのでダブリングの方です
Strongly Connected Components
使ったことないです これが必要になるほど強くなれていません
2-Sat
上に同じ
Fast Fourier Transform
上に同じ
Maximum Flow
上に同じ
minカットとかよくわかってないです これ がわからなかったけど最大流にできそうだったので貼ったら通ってしまいました 想定解じゃないと思います
コピペできるようにしてあるのはこんな感じです BFSとかDijkstraとかは毎回一から書いています
終わりに
なにを書けばいいのかわかりませんでした とりあえず自分語りをすればいいと習ったので自分語りばっかりになってしまいましたが、許して欲しいです かなりごちゃごちゃしていますが、自分の思っていることはだいたい素直に書いたつもりです もし奇跡的に誰かの役に立つようなことがあれば、とてもうれしいです
