pythonでatcoderで黄色になりました
はじめまして、くまざきといいます。
いきなりで恐縮ですが、先日atcoderで黄色になりました。
いわゆる色変記事というものを書こうと思います。
お品書きです。
自己紹介・バックボーン
- 1989年生まれ
- 2019年8月、競プロ初参加
- 主にpython,pypyでコンテストに参加
→ numpy,numba,cythonなどは使っていません。 - 中学受験勢
→ 中学受験当時、算数はかなりできる方でした。が、その後の数学は適当です。
特に大学以降の数学はサボっていたのでほとんどわかっていません。 - パズルや謎解きが好き
→ 二コリ系パズルで暇をつぶす日々を過ごしていたのですが、
それなら競プロのほうが有意義なのでは？と思ったのが、
競プロを始めたきっかけの一つです。 - 頻度高くないが、一応仕事でプログラミングすることもある
→ データ分析チックな仕事をすることがあり、
その際pandasやscikit-learnなどを使ったりしていました。
じゃあpythonは完璧かというとそういうわけでもなく、
list型とかdict型とかの仕様はあまりよくわかっていなかったです。 - 始めた時点で競プロ知識はほぼ０
黄色になるまで
- 初期（～2019年12月）
Twitterの謎解きクラスタでatcoderの話をしている方がおり、
プログラミング＋数学＋パズルみたいなものなら得意分野かなと思って始めました。
得意分野だという読みは外れてはいなかったのですが、世の中にはもっと上がいるのだということにすぐ気づくことになります。
入出力だけのお作法だけ勉強して、特に過去問を解くわけでもなくABC137に出たのが初回で、2完灰パフォでした。
C問題とD問題にも手を出していますが、どちらもTLEしており、この時点では計算量の概念がなかったことが伺い知れます。
その後もうすこし勉強して、数回コンテストに出ています。
この時緑～水パフォでしたので、初期能力はこれくらいだったようです。
2019年は年末にかけて忙しい時期だったため、10~12月はコンテストに参加していません。 - 水色まで（2020年1~3月）
本格的に競プロ活動を再開し、これ以降ほぼ週1ペースでコンテストに参加しています。
2月からは200日程度streakをつないでいました。
精進内容ですが、そこまでの経験でDPに苦手意識があったので、ひとまずEDPCをやれるとこまでやりました。
あとは、仕事で毎週泊りがけの出張をしていた時期があり、
夜ご飯を食べると何もすることがなかったので、ひたすら令和ABCのバチャをやっていたり、蟻本の初級編あたりを読んでみたり。
コンテストでは水パフォが安定するようになっていたので、
しばらく続ければ水色にはなれそうだな、と思っていました。
この辺で「とりあえず黄色」を当面の目標にしようと決めたような気がします。
（水色になったタイミングのatcoder problemsスクショ）
（当時は今よりもだいぶ情報が少なかったですね。）
- 1800くらいまで（2020年4~5月）
競プロでも急に伸びる時期がある、みたいな話をよく聞きますが、
私もこの時期にrateが伸びました。
ABCで全完したり、黄パフォが出たり、みたいなことが急に発生したりしました。
学んできた競プロ基礎知識がある程度定着して、コンテスト中に発揮できるようになったタイミングだったかな、と思います。
精進内容としては、令和バチャが一通り終わってしまったタイミングで、JOIレベル7埋めに着手した時期です。
自分の競プロ力を見つめなおしたときに、実装力が足りないという感覚があり、下記の記事で実装力向上にJOI過去問が勧められていたので手を出した、という感じです。
JOIの古めの問題はpythonだとTLE,MLEが厳しいものもあり、pythonユーザにはオススメしづらいのですが、逆にそこでいろいろなテクニックを身に着けた感じもします。
あと、勢いでmaspyさん主催の組み合わせ論輪読会に参加したのもこの時期です。
私は参加者の中だとかなり数学レベルが低い方なので、めちゃくちゃ必死に準備して、それでも置いて行かれている感じです。
内容が高度過ぎて、今のところあまりrateに結びついてはいないと思われるのですが、いろいろ知識は増えています。
（ちゃんと知識定着していればrateにつながっていたであろう場面は何度か観測しています。）
（青色になったタイミングのatcoder problemsスクショ）
- 停滞期（2020年6～11月）
ここから半年ほどrate1700~1850の間で停滞します。
半年もあったのでいろいろな精進をしていました。
「やっぱ黄色になりたかったら黄diffを解くべきだよね」と思って黄diffで40日ほどstreakをつないでみたり、
「ABCで速度負けするし、青diff以下の速度上げよ」と思って平成ABCのバチャをしながら青diff埋めをしたり、
「いや、ARCでパフォ出せた方が強い！」と思ってARCバチャをやってみたり
今考えると迷走していますが、どの営みも悪くはなかったと思っています。 - 黄色まで（2020年12-2021年1月）
競プロでも急に伸びる時期がある、みたいな話をよく聞きますが、また急にrateが伸びだしたのがこの2か月です。
久々にABCで黄パフォが取れたと思ったら、翌週のARCで橙パフォが出て、これは流れに乗ったな、という感じでした。
何がよかったのかこじつけで考えてみると、下記のような感じでしょうか。
①知識の抜けが減ってきて、～青diffが少ない考察で倒せるようになってきた
→ ABCの速度負けが減り、パフォが安定
②相性の良い黄diffなら短い時間（30~60分）で処理できる力がついてきた
→ ARC級で黄パフォoverが出せるケースが発生した
停滞期は「青を安定させるか」「黄以上を解くか」で悩んでいたのですが、結局両方やればよかったということですかね。
というわけで、先日のキーエンスコンでめでたく黄色になれました。
（黄色になったタイミングのatcoder problemsスクショ）
ライブラリ
個人的に、色辺記事には持っているライブラリの情報が記載されていると嬉しいと思っており、それ故に手持ちのライブラリを書きます。
→ 参加者の大半が持っているライブラリを持っていないとすれば、該当する問題が出た際にかなりのハンデとなるため、把握しておきたいという気持ちです。
うろ覚えですがざっくりの作った時期などの情報を併記します。
→ ◎：水色まで ○：青まで ★：コンテスト未使用
ACL移植を除けば、決して多く持っている方ではないのでは？と思っていますがどうなのでしょうか。
- ACL（Atcoder Library）以外
■データ構造系
◎ UnionFind木
◎ segment tree（最小値・最大値のみ）
BITはACL移植をするまで持っていませんでした。先にセグ木を履修すると要らないと思ってしまいます。
最近はセグ木はACL移植のものを使っています。抽象化は慣れるまで大変ですが、慣れるとかなり便利に感じます。
■グラフ系
◎ ダイクストラ
◎ ベルマンフォード（★）
◎ ワーシャルフロイド
◎ rerooting
○ LCA（★）
BSF,DSFはいろいろな場面・用途で使うのでライブラリにしておらず、その場で都合の良いものを書いています。
LCAも毎回書いていたのですが、さすがに面倒だと思って最近ライブラリにしました。が、その後利用場面に出くわしていません。
rerootingは一時期ABCで出ていたイメージがあり、都度書くのはつらかったのでライブラリにしました。が、ここ半年以上見かけていない気がします。
グラフは入力から様々な関数を一つにまとめた汎用関数・クラスを作って持っている方もいるそうなのですが、そこまで手を出していません。
また、グラフ系は、pythonユーザの場合networkxを使うのも十分選択肢だと思います。が、私はpypyメインなので使っていません。
■素数・素因数など
◎ 素因数分解
◎ 約数列挙
◎ エラストテネスの篩（奇数だけ見て高速化）
◎ エラストテネスの篩（区間l-rの間の素数を列挙するもの）（★）
■その他
◎ bitDPでの部分集合列挙
◎ 二項係数算出（前処理o(N), クエリO(1)）
〇 転倒数算出（★）
二項係数の計算は頻出で、無いと戦えないので、ACLにも含まれていてよいのでは？と思っています。
また、以上の他に、入力とよく使うパッケージのimport文については、すぐコピペできるようにまとめてあります。 - ACL移植
全部青になった以降の作成です。
セグ木以外は使ってないです。
〇 convolution（★）
〇 fenwicktree(BIT)（★）
〇 segtree / lazysegtree
〇 scc（★）
〇 twosat（★）
〇 string（★）
〇 maxflow（★）
〇 math（★）
コンテストではほとんど使えてないですが、「万が一出たときに持っていないと著しく不利になる」「アルゴリズム読むと勉強になる」の観点から、pythonユーザの方は積極的に移植したらいいと思っています。
ちなみに、進行形で細々と移植作業を進めていて、残りの大物はmincostflowぐらいになっています。一方、現時点で「pypy向け」＆「完了済」の公開移植PJが無いようなので、移植完了後、需要があれば公開するかもしれません。
その他ポエム
かなり長文になってきたので簡潔に。今後の目標など書きます。
黄色になったタイミングでコンテストを卒業する案もあったのですが、もう少しくらいはrateが伸ばせそうな感触があるので、当面は2200を目標にARC・AGCに参加していこうと思います。
それとは別に、python,pypyユーザ向けのtipsなどを発信できるといいのかな、と考えています。（今回ブログを作ったのもその辺が目的だったりします。）
https://atcoder-circles.herokuapp.com/circles/pythonista
上記のサイトによればpython,pypy使いで現在（2021年1月27日時点）黄色以上になっている人数は36人しかいません。
言語を絞らなければ黄色overは1000人以上いるので、全体の1/30程度だということになります。
一方、これより低いrate帯だと、相対的なpythonユーザはもっと多いです。
元々競プロガチ勢はC++を選択するのでしょうがない傾向ではあるのですが、C++以外の教材・情報が少ないこともこの一因かと思っています。
一昔前は「pythonだと〇色は無理」みたいな発言もあったようですが、最近ではmaspyさんがその反証をどんどん進めてくださっていますし、python界隈を盛り上げるために私もなんらか貢献できるといいな、という感じです。
