PythonとC++でAtCoder黄色になった話
はじめに
先日のABC159で無事黄色になることができたので、いわゆる色変記事を書こうと思います。
黄色になりました！！！！！！！！！！ pic.twitter.com/9BO5Zo0LqN
— まさよし＠今日も１日１AC (@masayoshi361) March 22, 2020
やったこと
AtCoderを始めるまで
atcoderのアカウント自体は１年生の6月くらいに作っていたのですが特に問題を解くでもなく時間が過ぎて行きました。ところが1年生の2月にとあるきっかけがあり、競技プログラミングやってみようかなぁと思い始めることになりました。一応Pythonを独学でやっていたのと、授業でも扱ったことがあったので言語は自然にPythonを選んでいました。とはいえライブラリとか細かい部分は全然知らなかったので手探りという感じでしたね。また高校数学は一通り学んでいたので初めの方はかなりスムーズだった気がします。また計算量の概念も授業でちょっと扱っていたので基本は理解していたつもりでした。
灰色＆茶色編
これをやりました。
あと蟻本も買いました。これ系の本は一冊手元にあるといいと思います。
形から入る人間なので蟻本を買った
— まさよし＠今日も１日１AC (@masayoshi361) February 28, 2019
緑編
蟻本とけんちょんさんの記事を参考に問題を埋めて基礎的な知識を得て行きました。 qiita.com
水色編
旧abcのdらへんを埋めていました
この辺からは問題を解きながら知らない知識を得ていく感じになります。また、蟻本に乗っているような名前のついたアルゴリズム以外に「典型的な考え方」（操作を逆順に考えるとか）も吸収するのが大事だと思います。
青色編
atcoder problems の青difficultyと黄difficultyを埋めていました。この辺から新ABCのF問題がいい感じに解けるようになりレートも好調に伸びて行きましたが、青後半になると最後の一押しが足りない状態が続き、青上位をゆらゆら揺れていました。そこで黄色になるには青diffくらい全部埋めなきゃ駄目だろうと考え、取りあえず全部埋めました。ここからも時間がかかるのですが、春休み＋コロナで持て余した暇を利用して精進していたら何とか黄色にたどり着くことができました。
現状
現在の精進具合はこんな感じです。一応青diffは全て、黄diffは半分くらい埋めました（が、パフォ推定の仕組みが変わったため今は青diffもちょっと残っています...） いわゆる虚無埋めをしていないので問題数は少し少ないかもしれません。
最近はcodeforcesもちょっとやっています（生活リズムが正しいのであんまり出れていませんが）。
まとめ
とにかく問題を解こう！！
C++とPythonの使い分け
去年までは完全にPythonオンリーだったのですが、少し定数倍をサボるとTLEするなど辛かったのでC++を勉強し始めました。やっぱりC++は早いです（当たり前）。とはいえPythonが光らない場面がないわけではなく、多倍長を扱いたい時であったり、そうでなくとも制限時間に余裕があれば簡潔に書けるpythonは強いと思います。またnumpyやscipyが使えるのも大きな利点です（僕は全然使いこなせてませんが...）。今はまだPythonの経験値の方がはるかに高いので、これは間に合うだろうという問題はPythonを使って、ちょっと怪しいなぁというものだけはC++を使っていますが、これからはC++オンリーになるかもしれません。
結局どっちがいいのか？
青までならpythonでも全然大丈夫だと思いますが、黄色以上だと少し計算量の悪い解法（logが付いてしまうなど）でもC++なら通せたりと少し不利に働くことも多いと思います（もちろんpythonで橙に行ったmaspyさんのような人もいるので無理という話ではありません）。あとは情報の問題もあります。いろんな人の解説記事や蟻本は大体C++で書かれているので、そうしたものを参考にするのにもC++はできた方が良いと思います。なので「自分は競プロを無茶苦茶頑張るぜ」っていう人はC++を勉強すればいいんじゃないでしょうか。もちろん今できる言語があるなら僕みたいに取りあえずそれでやってみて辛くなったらC++を勉強してみるのでもいいと思います。
ライブラリ
今ライブラリ（コピペできるようにしているコード）として持っているアルゴリズム、データ構造は以下の通りです。
- グラフ系
- データ構造
- segment tree（遅延も）
- BIT
- UnionFind
- 文字列アルゴリズム
- rolling hash
- suffix array
- 数学
- combination
- 行列累乗
- 約数列挙、素因数分解
高速フーリエ変換はscipyにあるので持っていません。
知識とか典型
メモ程度に今ある知識を書いておきますが、ライブラリとは異なり当然抜けも多いと思います。また、個人的メモの側面が強いので独自の呼び方とかが混じってるかもしれません。
