pythonでatcoder黄色になるまでにしたこと

ansainです。
ABC194でatcoder黄色になったので振り返りを兼ねて2週間かかりましたが色変記事を書きました。
#バックグラウンド

・地方出身→地方進学校→東工大理学部地球惑星科学科卒→某IT企業でデータサイエンス関係の仕事をしている。
・小中高時代は囲碁や数オリ(1回だけ本選出場)やって頭脳鍛えてた。でも東京進学校のすごい人たちの界隈とは全く接点なかったのでどういう生態か全く知らなかった。
・大学時代は東工大版進振りに負けて情報科学科落ち。なのでアルゴリズムの授業は何も受けてない。
・大学時代は趣味でプログラミングせずにボドゲサークルや音ゲーサークルで遊んでた。atcoderやABCの話題もtwitterのTLの片隅に見えるくらい。
・学部1年のプログラミングの授業でRuby,学科のプログラミングの授業でFortranをやったけどほとんど忘れた。
・卒研ではpythonを使って、天体観測情報データ分析用ライブラリのドキュメントを読んで、欲しい星の観測データを頑張って取り出してた。¹
・就職と研修で、pythonとSQLを本格的に勉強したのをきっかけに、業務で使うpythonの理解を深めることを兼ねてatcoderをpythonで始めることに。以降黄色までpython一筋。C++はほとんど読めない。²

#コーディング環境
・メインコードエディター　visual studio code
・サブコードエディター(動作確認,手元テスト,実験用)　jupyter notebook
・コードテンプレート・ライブラリ・vscodeスニペット https://github.com/ansainbdg/my_kyopro_library
・提出ツール AtCoder Easy Test,AtCoderLanguageButtons³

#精進記録

##記録画像

##やったこと
・基本的にatcoder ploblemsの問題リストやから現在の適性難易度の問題を解いて、公式や他サイトの解説を読んで思考を補完することをひたすら行っていた。自分にはこれが一番性に合っていたと思う。
・たまに、学ばなければならないアルゴリズム等があると感じたら、解説記事等を読んでライブラリの作成・コピペを行い、atcodertags等から類題を探してverifyをしていた。
・たまに、他サイト(paiza,techful,yukicoder)の問題を解いていたりしていた。paizaは偶然かやったB,Aランク問題が実装ゴリゴリ問題だったので敬遠していたが、Sランク問題は意外とABCでありそうな教育的な問題が多かったので割とオススメ

##やってないこと
・定期バチャ 解いたことある問題を再度コーディングするのがあまり性にあってない。
・書籍購入　そこまで趣味にお金かけたくなかったので。蟻本含めて書籍0でここまで来れることは証明した。
・海外レーテッドコンテストサイト　英語苦手なので。
・下埋め　実力には結びつかないと思う。

#色変までの軌跡

###初めてから水色付近まで

この頃はひたすら新しい知識を得てひたすらコンテストに出てレートを伸ばしていた。たいていの場合レートが上がるのである意味一番楽しい時期。簡単めのABCを遅全完して青パフォ下位だして興奮していた。逆に言うと上限が青パフォ下位なので、水色下位で少し停滞していた。⁴

###水色から青下位まで

AGC049でrobotsを終了3分前にACしてアドレナリンを大量に放出して2200パフォ取って「こんなパフォもう2度と取れない」と思ってたらARC108で4完早解きして2300パフォ取ってレートが爆増して青に。レート1321からコンテスト2回で青になってしまったので全く心準備をしていなかった。
その後は今まで大成功だと思ってた青パフォを取らないと冷えるプレッシャーに押しつぶされたか緑水diffの解法が見えなくなることがいくつか起こり停滞することに。

###青下位から入黄まで

最初2回の黄パフォ以上がAGC,ARCだったためもしかしてABC苦手？と思ってたけど間違いで、ABCで突然2200パフォ以上が面白いように出続ける。その勢いのまま、極めつけにABC194で31位,rated内3位を出して入黄。なぜABCで突然2200パフォ以上が出まくったかはよく分からないが、pypyでTLEに苦心することがほぼ無くなったおかげかもしれない。admin交代でpypy運営解が保証されたおかげか、自分の実装が上手くなって自然に定数倍軽い解が書けるようになったか...

学んだアルゴリズム・使ったライブラリ

必要なアルゴリズムの中でも2種類あると思っている⁵。表面的な使い方だけ覚えておけばよいアルゴリズムと、原理・内部実装まで覚えておく必要があるアルゴリズム。

例えば私はセグ木・遅延セグ木は問題を見て、セグ木に渡すモノイドの作り方だけしか把握しておらず、内部実装はあまり理解していないのでセグ木のライブラリをソラで書くことができないが黄色になた。JOI等のコピペ禁止コンテストに出るのでなければこれで十分だと思っている。セグ木の内部実装を理解する時間でセグ木を使う問題を演習した方がatcoderのレートを伸ばす上では有意義。

対してBFS,DFS,ダイクストラ等は原理を理解して、問題に合わせて内部実装を書き換える問題⁶などが出題されるので原理・内部実装を理解しておく必要がある。

とはいえこういう精進の仕方ができるのは先人がライブラリを作ってきてくれたおかげなので感謝。⁷

###原理・内部実装まで覚えておく必要があるアルゴリズム
重要度順
・二項係数mod計算(一発計算用と、階乗前計算用)
・BFS
・二分探索
・ダイクストラ
・素因数分解,約数列挙
・ワーシャルフロイド
・ベルマンフォード
・DFS⁸

###使い方だけ覚えておけばよいアルゴリズム
・UnionFind
・逆元,繰り返し二乗法⁹
・Fenwick Tree
・Segment Tree
・Lazy Segment Tree
・拡張ユークリッド,CRT
・SCC
・最大流
・最小費用流
・ACL文字列アルゴリズム系

###履修してない
・形式的べき級数
・grundy数
・畳み込み系
・HL分解
・幾何系

#問題を解く時に意識していること
###問題設定には意図がある
問題中の設定や、制約には作者の意図が含まれているので、そこから意図を推測すると、解法に近づくことがある。
・TLが2secより長い→定数倍や、log等でTLがきつい問題が出る。(少なくともN=10^5でO(n)みたいなのは出ない)
・制約が明らかに小さい箇所がある→そこをベースとした全探索やDP¹⁰

とはいえ、ABC195D等設定から回答者に解法を誤認させること自体が意図である可能性もあるので過信は禁物。

###サンプルにも意図がある
サンプルにも意図がある。
特にサンプルが弱い場合、サンプルを増やすと簡単に推測されてしまうような単純な解法を隠蔽したくてサンプルを弱くしている可能性があると推測できる。
また、構築問題では、サンプルの構築は解法の構築方法とは意図的にずらした方法であることが多い。

#競プロpythonのお気持ち
###良いところ
・オーバーフローしない。二分探索の上限を脳死で設定出来たり、でかいbitを脳死で持つdpもできたりする
・公式ライブラリが豊富でnetworkxやscipyでたまに殴れたりする。しかもscipyは遅くない
・早くコードを書ける。早解き大事。
・遅いけど高速化する手段が豊富。numpy,numba,pypy,cythonなど。遅いけど多機能か、機能が制限される代わりに速いかを問題に応じて選べる。

###悪いところ
・それでも遅い時は遅い。想定解とは違うデータ構造で殴るときとかはきついこともある。でも新adminの方針もあってかpythonでどうしようもない問題は減った。
・C++で書いた有志実装解説記事が読めない。頑張ってpython実装を探している。
・参考に出来る他人の提出もC++に比べて少ない。でも大抵maspyさんがいたりする。本当にすごい。

#今後の目標
黄色になってABC卒業した後が修羅の道すぎて登れる気がしない。¹¹SNSで見ても橙以上の知識量が違いすぎて橙になれる気がしないし、今までのARCの成績鑑みても黄色維持すら辛そうなので一旦アクティブ外れない間くらいは黄色で保存¹²して作問や解説記事とかやってみたい。色落ちすると解説記事書けなくなるし今のうち

1. この頃はif文もfor文もよく知らずドキュメントのpython文を星の名前以外そのままコピペしてjupyternotebookに貼り付けたりしてる異常な状態でプログラミングしてた。 ↩

2. C++読めすらしない純粋pythonistaの中ではかなり高い方な気がする。pythonista上位勢も、C++一応読める人が結構多いイメージ(主観) ↩

3. 結構前までは、online-judge-tools,atcoder-cli使ってたけどコマンドプロンプトにコマンドコピペするより提出欄にコードコピペする方が早いので乗り換えた。実行時間も自分の古めのPCだと信用ならないし。 ↩

4. 水色に灰黄の崖を突き付けて遅解き緑パフォ叩きつけたARC104マジで許されない ↩

5. 少なくとも黄色までは ↩

6. ABC184E,ARC111D,ABC164E等 ↩

7. 他人のライブラリは、ACLコンテストの提出一覧などから拾ってる。今は新adminの方針のおかげで公式提出もあるので、pythonなら困ることはほぼ無いかと ↩

8. なぜBFSに比べてDFSがこれだけ重要度低いのかというと、グラフ探索系アルゴリズムは基本的にBFSを使うべきだと思っていて、DFSを使うシーンはBFSではダメな時だけだから。そのような問題は青diff以降(ABC165E,ARC111D,木dp系等)にしか出ないので重要度は薄い。 ↩

9. pythonではこれらがビルトイン関数になっているため自力実装する必要が無い。 ↩

10. ABC194C,ABC193E,ABC195F,ABC190E等 ↩

11. 3月22日現在、アクティブユーザーで赤が上位144人,橙が上位375人,黄色が上位1282人,青が上位3202人,水が上位6955人。倍率で見ると1色上がるハードルが高いのは明らかに黄→橙 ↩

12. これだけ語彙力が豊富なatcoder界隈で「保存黄色」みたいなワードが無いくらい、界隈の向上心が高いことに驚いている。 ↩