3/21のAGC043で青になったので、慣習に則って変色記事を書きます。
無→灰（自己紹介）
ハンドルsotanishyです。春から大学1年生です。それまでは浪人生のようなことをしていました。競プロ歴は半年弱で、Python使いです。
プログラミング自体を始めたのは約5年前、中3の時です。エクセルのマクロで遊んでました。その後JavaScriptやJavaでゲームを作ったりアプリを作ったりしました。アイコンは自分で作ったゲームのキャラクターです。
AOJをちょっとかじったことがあるけど、競プロは全然やらなかったです。Google Code Jamは2年くらい前から毎年出てますが、特にアルゴリズムの勉強したり過去問解いたりといったことはせず、地頭だけで特攻してRound 1で撃沈してました。
高2の時、Google Foobar Challengeというのに参加して、結構むずい問題も解けたのでGoogleのリクルーターからスカウトが来ましたが、高校生に仕事はないと言われました。泣。
去年の11月ごろ、受験勉強に飽きてきたので競プロを始めます。
最初はSRMに出て黄色になりました。（は？）
翌日AGCに出て灰になりました。
この時点で、計算量の概念、DFS/BFS、二分探索くらいは何となくしってました。DPってなに？令和ABCのD問題くらいまでは大体解けるが、E以降はきつい感じでした。能力初期値は緑上位くらいだったと思います。
灰→茶
コンテストに出ます。
茶→緑
コンテストに出ます。
緑→水
アルゴリズムの知識をつけるために、蟻本を始めました。思ったよりむずくて、例題が初見では全然解けません。練習問題も半分くらいは自力で解けるけどあとは適当にググって中国のサイトから答えを引っ張ってきました。
この頃コドフォも始めて青になります。
ABC148で初全完しました。めちゃ簡単な回だったけどはじめて全完+青パフォが出たので喜びます。
あとはRustをやろうとしました。Pythonは定数倍で落ちることが多くてもっと速い言語を試してみたかったけど、人と違うのがいいのでC++以外のやつで速い言語と言ったら、Rust。むずすぎて1か月くらいで挫折しました。
年末のAGCで2完、水色になります。2019年中に水になれたので良かったです。
水→青
蟻本の初級編を終えたころから、ABC-Eも解けるようになってきました。1月ごろに受験勉強が終わったので中級編を始めました。セグ木むずい。フロー楽しい。
水時代に特に印象に残っていることは、第5回Asprova Contestに参加したことです。初めてのマラソンでいろいろなことを学べました。入賞は逃しましたが、懇親会とかで初めて競プロerと絡む機会があったので楽しかったです。
大学でICPCとか出ようと思ったら、やっぱみんな知ってるC++の方がいいのかな…とか思って、C++の勉強を始めました。Rustはしばらく諦めます。APG4bにとてもお世話になりました。以降POJと虚無埋めはC++でやります。
水中位になったころから、レートがしばらく停滞しました。このまま収束して青になれないんじゃないかな…と不安になってきました。そこでほかの青以上の人たちを見ると、精進量が自分と全然違うことがわかりました。ほかの人は青精進とか黄精進とかしているのに、俺はまだ茶精進だったので、実力が停滞するのも当然かなと思いました。
そこでちゃんと目標をもって精進をすることにしました。片っ端から埋めていくのは限りがないし超絶めんどくさいので、色を埋めることにしました。水埋めを始めます。これがよかったらしく、レートがまた伸び始めました。
パナソニックコンテストで念願の黄パフォを出して、青まであと一回というところまで来ました。黄パフォはうれしかったけど、緑の早解きしかしなかったのであまり納得いくものではありませんでした。
そして3/21のAGC043で2完し、青になることができました！最後の5分までA問題しか解けてなくて、水パフォで冷える予定だったけど、何とかBを通すことができて青上位パフォを獲得しました。
青になるまでの能力・知識
- 数学力：高校数学は競プロの役に立つ。
- 実装力：これは強い人のコードを参考にしながらたくさんコードを書いて経験を積むしかないのかもしれません。俺は考察ができても実装が下手でTLEしたりすることがしばしばあるので、ここは伸ばしたいところです。
- 使ったことのあるアルゴリズム：DFS、BFS、全探索、DP、二分探索、三分探索、尺取り法、mod逆元、累積和/いもす、グラフ系（Dijkstra、FloydWarshall、トポロジカルソート）、幾何（線分や円の交差判定とか、三点の内心とか）、データ構造（PriorityQueue、UnionFind、BIT）、Manacher（回文である部分文字列を線形時間で見つけるアルゴリズム。最近コドフォででました。ググって貼っただけなのでよく理解してません）
- 個人的には、アルゴリズムの詳しい仕組みがわからなくても、それで何ができるか知ってて、計算量を知ってれば少なくとも青までなら十分だと思います。それよりも「これが効率的にできれば問題が解ける」ってとこまで帰着できる能力の方が大事だとおもいます。AGC043-Bも、「二項係数の偶奇がわかれば解ける」というところまで帰着できたので、あとはググってその方法を探すだけでした。方法はいまだによく理解してませんが、問題は解けました。
- アルゴリズムをたくさん知ってると思考停止して殴ることができることがあるので便利ですが、頭が固くなってくる気もします。昔は何も知らなかったので自分でいろいろ発明したりしていましたが、最近は自分が持っている知識だけで解こうとするので、創造的な思考をしなくなっている気がします。ただ今回のAGC-Bは使える知識がない状態で解けたので良かったです。
精進について
- 水埋めが永遠に終わらない。
- 現在緑精進です。
- 自分は色を埋めるようにしています。自分に合った難易度（自分の色かその1色下）の問題をたくさん解くと力になると思います、たぶん。青までは緑早解き+水で行けると思うので、水埋めは有効だと思います。
- 基本的にわからない問題は解説を見ずに後回しにするようにしているけど、9割ACでコーナーケースがわからないとか、計算量はいい感じなのにTLEが取れないとかってときは解説を見てます。
- 問題を解いたら自分より速いコードとか短いコード（これ明らかにコードゴルフだろっていうのは除く）を見て、上手な書き方を盗むようにしています。
- カスなので、ABC-Aとかの虚無はいざというときにストリークをつなぐためにとってあります。
Pythonについて
- ABC-D以降は下手な実装だとPythonで落ちる問題が多い感じです。一時期Pythonをやめようと思ってRustをやったりしたけど、maspyさんが言っている通りPythonでもすべてACできるはずなので、定数倍で落ちるのは俺の書き方が未熟だから。NumPyやSciPyを使ったり、PyPyで提出したりすると結構通ることが多いです。最近は文字列操作と再帰が多い問題（PyPyが人が変わったように遅くなるので）以外はもっぱらPyPyで出してます。
- PythonでだめだったからJavaとかC++で書き換えて投げてもTLEってことが何度もありました。TLEは多くの場合言語のせいでなく、計算量を落とせてないとか、実装が下手だからだと思います。もっと上のレベルになるとどうなのか知りませんが。
- Pythonの普通のinputは遅いので、input = sys.stdin.readlineを頭に書いてます。コドフォでO(1)のアルゴリズムがinputが遅いせいで落ちて発狂したことがあります。
- NumPyの整数型には上限があるので注意しましょう。Pythonの多倍長整数と同じだと思って何度もWAをいただきました。
海外サイトについて
TopcoderとCodeforcesをやっています。Topcoderは開催時間がやばいのでまだ3回しか出ていません。初回でなぜか黄色になったけど、その後レートは絶賛単調減少中。今青です。Div1easyが全然解けねえ。
Codeforcesはすぐ青になれたので楽しかったです。少しずつレートを上げていって、今は青中位くらい。体感的に、コドフォは考察は楽だけど実装がむずい感じの問題が多い気がします。コドフォのレートの方がAtCoderのそれよりも高いということは、そういう問題が得意なのかもしれないです。個人的にはAtCoderの方が解いてて楽しいんですけど。
これから
大学入学までに脱水できてよかったです。翌日のABCで再入水しないように頑張ります。今年のGCJはとりあえずRound 2を目標にします。そして11月まで（去年の11月に競プロを始めたので）にあっとこ黄、コドフォ橙を目指します。あとオンサイトとか出てみたいです。
