はじめに
先週のコンテストで無事水色になれたので、今までやったことの振り返りを兼ねて記事をまとめます。
自己紹介
東京工業大学地球惑星科学科卒業
卒論でpythonのライブラリ使っただけで大学ではあまりプログラミングしてませんでした。
新卒でIT系の会社に入社し、業務でpythonを学び始めました。そこで、pythonとプログラミングの知見を深めるためにatcoderを始めました。
東工大入れるくらいには高校数学はできたので（大学数学、物理には跳ね返されたけど）、順調に
水色までは伸ばせました。
使っているライブラリ・チートシートのうち、完全にコピペでないものを投げるgithub
水色までにやったアルゴリズム
本番で実際使用して、解けてレートに寄与したもの
・bit全探索
・累積和
・配列二分探索(bisectモジュール)
・関数二分探索(めぐる式)
・unionfind
・逆元
・約数関連
・周期性に着目するテク
・セグ木
・遅延セグ木
・簡単めのdp
精進したけど本番で出なかったorできなかったもの
・BFS,DFS(wizard in mazeが解けなかった)
・ダイクストラ
・尺取り
・優先度付きキュー
名前だけ知っててやらなかったもの
・ワーシャルフロイド
・ベルマンフォード
・フロー関連
・全域木
・高速フーリエ変換系
水色までやって感じたpython競プロのメリットデメリット
多倍長整数
これが一番大きい！解く時間も大事な競プロにおいてオーバーフローという考える要素が1個減るのは大きい！特に一番感じたのはRoad to Millionaire
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_d
でした。これは、制約が小さいながら答えが膨大になり得るので、オーバフローしうるという罠がある問題ですが、python勢は何も考えず貪欲するだけでAC出来ます。なまじ問題が実生活に関連しているせいで、非現実的だが金が膨大に増える可能性を見落としやすいんですよね。しかもこのコンテストは残り2問が高すぎる壁になっていて、青まではDまでの早解きで勝負が決まる回でした。SNSではオーバーフローに気づかず30分も時間を溶かした報告もありましたが、これだけで数百もパフォが変わり得る恐ろしい問題です。このような人のパフォを吸ったのか、当時茶色ながら27分で4完して青パフォを出すことに成功しました。
また、多倍長整数特有のテクとして、bool列を1つの整数として持つテクがあります。こうすると記述が楽になったり、非常に大きい定数倍高速化になったりします。
https://atcoder.jp/contests/abc147/submissions/16047068
これはこのテクを使ってpythonで80msで解いた回答ですが、boolを個別に配列として持つと、80msがTLEになります。
豊富なライブラリ、関数
pow(a,-1,mod)で逆元が高速で出るのはずるいです。
itertoolsのproductでbit演算知らなくてもbit全探索できるのも便利です。
numpy,scipy,networkxも非常に便利です。
jupyter notebook
インタラクティブにプログラムの検証ができるので、特に始めたてのpython文法うろ覚えの頃にはお世話になりました。（C++に同じようなものがあるかは知らないけども）
遅い
まあこれはしょうがないですが、numpy,numba,pypyなど高速化できる手法や、先人の知恵が一杯ありますので、どうしても間に合わない問題はほとんど無いのでなんとかなります。
個人的な結論、意見
プログラミング初心者が競プロ始める言語は、C++とpythonの2択なら私はpythonを推します。
今後に向けて
次の目標は青ですが、さすがにしばらく時間かかりそうですので気長に頑張ります。