私文競プロerがAtCoderで水色になるまで

はじめに

　一ヶ月くらい前に水色になりました。自分でも今更、色変記事かよって感じなんですが、なんとなく書きたくなった（自己満足）ので書きます。

言語はPythonです。遅い遅い言われてますが暖色の方もいらっしゃいますし、水色とかまでなら早解きの重要度も高いので実装が軽いメリットも大きいと思っています。

元々、水色を目標にしていてわーいって感じなので、これまでのことでも振り返って行こうかと思います。

背景

　内部進学私文です！！！

　一目で尋常でない数弱だと分かったよ！

　はい、ということで大学受験どころか高校受験もしてません。

　ABCで余弦定理が出たときがありましたが、「余弦定理...？あー分かる分かってるよ！」って言いながら汚いごり押しで解きました。（分かってない）

　こんな人でも水色になれるんだよーっていう希望を与えられたと思います(？)

　特に競プロのために追加で数学を勉強したということはなかったので、割と競プロって中学受験要素も多いのかなーと思ってます。

　一応、文系の中では数学を使う機会が多い経済学部だったということだけ付け加えておきます。

灰色から茶色になるまで

　勿論、中高でプログラミングとかいう強そうなものはやったことがありません。ということでゼロからのスタートです。グラフを見ると、始めた当初の墜落寸前の低空飛行レートが見れますね。

　まずね、入力を受け取る方法が分からなくて辞めてやろうと思ったよね。mapってなんやねん。競プロの初心者挫折の90％はこれだと思ってます。（適当）

　とりあえず、やったことはABCのC問題までの過去問を解くことです。茶色まではアルゴリズムとか考えず、これだけで十分だと思います。全探索とかDFSとかBFSとか強そうな名前を知らなくても、過去問を解いてればなんかそういうのできるようになってます。C問題までを安定して解けるようになれば茶色にすぐなれると思います。

　でも、お前、2ヶ月半かかってるじゃんｗ

茶色から緑色になるまで

　茶色になった瞬間になんか青パフォが出ました。どうやら僕はドワンゴだったみたいです。緑色なんてすぐやろ！勝ったなガハハ

とか言ってたら2ヶ月くらい境界で停滞しました。

　緑になるためにはCまでの早解きでは難しく、簡単なDは解く必要が出てきます。Dまで解くとなるとアルゴリズムもそうなのですが、Pythonのライブラリや仕様を把握する必要があります。dequeやheapqの使い方・floatの計算精度・切り捨て時にint()ではなく//を使った方が精度が高い等、こういう落とし穴にはまらないことが重要です。まあどうせ初見じゃ分からないのでコンテストでハマりながら学習するんですけど

　dpとかもここらへんで学習すると思うのですが、それよりまず10**9+7で割った余りを求める際に使うライブラリを作った方が良いです。発想力じゃなくて持ってるか持ってないかで結果が決まるのって頭に来ませんか？私は来ます

　ということで作りましょう。あなたが天才でないなら逆元とかの証明を見ても分からないと思うので、概略だけ理解したらコピペしましょう。そのあと、自分で使いやすいようにカスタマイズしましょう。

　どんなアルゴリズム勉強したかよく覚えていないので、その辺は他の人の色変記事でも見てください。（最低）

緑色から水色になるまで

　水色になるためには水diffを解く必要があります。水diffなので。

　なに当たり前のこと言ってんだって感じですが、とにかく水diffを解きました。下限を上げるための精進もあると思いますが、事故死というのはある程度避けられないので、それより上限を上げるべきだと思っています。ということで虚無埋めは非効率だというのが僕の考えです。

　やってみると分かると思いますが、知らないアルゴリズムだから無理！という問題はあまりないと思います。僕自身、ダイクストラやベルマンフォードのライブラリを作ってません。また、セグ木も未だに勉強してません。いや、まずいと思うのでここら辺は早めにやろうと思ってるのですが、逆に言えば水色になるために必須ではないということです。

　蟻本を精読するというより実際にABCのDやEを解いていく方がいいと思います。天才は知りません。天才なら新しいアルゴリズムを勉強して青diff以上を狙っていくなどして上限を上げた方が良いかもしれません。

精進

　偉そうになんか言ってるけど、こいつ全然精進してないじゃんｗ

　......すみません、精進して青色目指します...