黄色になった
こんにちは、まつかわです。
つい最近のAGCとdiv1でそれぞれ黄色と薄橙になりました!
競プロ始める頃に立てた目標が黄色なので一応達成できたって感じですね。素直にとても嬉しいです。
こういう記事書くの初めてなんでやってみたかった恒例(?)の〇色までに何したか書きます!文章力が壊滅的なので箇条書き風です。
灰色まで
2018年の10月頃だったかなんか競技プログラミングで先輩がすごいみたいな噂が流れてくる
(後から知ったけどてんぷらさんだった)
プログラミングの勉強にもいいしやってみるかーと、とりあえず目についたけんちょんさんの記事を読みつつ適当なABC過去問に挑戦するも、
A問題で30分くらい掛けたしB問題が普通に分からなかった
(今見るとdifficulty20らしい、人は成長する生き物だなぁ)
(これ: B - Stone Monument)
それでこれはやりがいがあるぞと思った記憶がある
そのあと土曜夜に都合がつかないのもあって初コンテストまでABC-B, Cを中心に20~30問解いた。
でその初コンテストはCまで3完だった(当時ABC-Cの勝率は2~3割くらいだったからラッキーだったと思う)
茶色まで
300の勝率を上げようということで、土日を使ってAtCoderProblemsにある300点問題を70問くらい解いた。今は1日30ACとかこなせないからこのせいでProblemsのDailyEffortが死んだ。
ただその甲斐あって二回目のratedで茶色になれたし結構効いた気がする。
緑色まで
当時は3完で水perf結構出てたんで300解ければ...っていうのはあったので、その点300解くのはいい戦略だったように思う。よく昔の方がパフォ出易かったなんて話を聞くけど人によってはそうなのかもしれない。(昔の方がC自体の難易度は高いと思うけど)
ということで300埋めを主にやって緑になった
水色まで
ここから結構停滞し始めて、300埋め終わった(当時)ので400を埋めていたんだけど、当時の方針としてはどちらかといえば自分の挑戦域を広げるよりは確実に解ける問題を増やしていたように思う。
個人的には水色になるにあたって押さえておくべき(知らないと同レート帯に差をつけられる)アルゴリズム的知識がジャンプするような気がしていて、自分も結構ライブラリを色々書いていたような記憶がある。
企業コンに負け続けつつもABC全完して何とか水色になった
(Various Sushiの回50分全完は何気にえらいと思う)
青色まで
twitterを始めた
Codeforcesを始めた
水色になってABCがunratedになったのでratedが激減した。丁度行き詰まりを感じ始めていた時期と重なり、自然とモチベが減っちゃったので、
精進グラフもかなり緩やかになってしまった。当たり前だと思うんですけど自分の適性以上の問題を解き続けないと天才じゃない限り実力は停滞(相対的に減少)しちゃうし完全に悪循環だったように思える。
ただ何の気なしに申し込んだ関西のオンサイトコンCPSCOに行ってめちゃくちゃ楽しかったので(コミュ障気味な自分でも凄い楽しかった)
それでモチベが爆上がりしてそのおかげで青になれました、感謝。
黄色まで
ちょっと他のことが忙しくなり精進とかは片手間でやりつつ帰省も兼ねてHUPCに行ったりした、すげえ楽しかった。
学生最強コン予選通過できて初の(予選がある)オンサイトに行ったりもした、前の方座ってたので表彰者写真撮影のとき頭が邪魔だから平伏することになって何かを感じた。9~11月は色々あってコンテスト以外で問題を解かないみたいな生活してたけど当然レートは停滞した、令和ABCが無かったらレート的にモチベ的にもやばかったと思う、12月入ってからは結構解き始めてProblemsの黄diffを埋めた。期間的には長いけど振り返ってみるとあんまり中身がないなぁ。やっぱりやらないと伸びないね。
で年末のtourist回AGCで黄色になれた、嬉しい、tourist最高!!
これから
丁度年始だし今年の目標みたいなのを残しておきます、とりあえず今半分弱終わった橙diff埋めを終わらせて赤diffをゆっくり解いていければなぁと思ってます、あとそろそろ自分の問題解くスピードが周りに比べて顕著に遅いと痛感しだしたのでCFdiv2バチャとかを(中々まとまった時間とりにくいけど)やっていきたいですね、TLで流れているやつとかは積極的に参加したいです。数字的な目標でいえばやはりもう一つ上の色に行ってみたいという思いはありますが、まずはAtC2200あたりを目指すべきかなぁと思ってます(そのくらいの人にあまり勝てるビジョンが見えないくらいには実力差ありそう)
pythonでやる競プロについて
まぁよく見る話題なので...実際雑談のネタとしてはありだと思います。正直使いたければ使えばいいという言葉に尽きる気もしますが、自分のレートの律速は使用言語ではなくまだまだ自分の頭の悪さや経験不足です。逆にそれが大きく響くくらいの実力に早くなりたいものです。
ライブラリ
上でもあったんですが、自分はパターンマッチングとかそういうのがまだまだ遅くて、それが響いてN完激遅とかN+1問目を逃すとかが多いです。後者は特に悔しいですよね、なので最近は意識的にライブラリを増やしたり、思考の類型分類をするようにしています。折角なので書いたやつを列挙していきます、気持ち使う頻度の昇順です
- オイラーパス復元
- 最大長方形
- BinaryTrie
- Baby-step Giant-step
- LiChaoTree
- 最近点対(分割統治) - 最近ランダムな軸でsortする奴の方が実用的かなーと思ってる
- GrahamScan
- Trie
- rollinghash
- SCC
- 行列累乗 - python使ってるのにこれ書くのあほくさすぎる
- LIS
- LCS
- LCA
- Dinic
- ランレングス圧縮 - 使うようで使わない
- メビウス関数求めるやつ(Aのすべての約数について求めるのと1..Nのを列挙するやつ)
- ガウスの消去法 - 任意modで2のときだけbit演算使ってるけどmod2以外使ったことない
- Z-algorithm
- 双対セグ木
- 遅延セグ木(RAQ, RSQ) - 二分探索も付けたけどいる?ってなってる
- トポロジカルソート
- オイラーツアー
- BIT - 最近セグ木で良くね?ってなりがち
- BIT上の二分探索でmultisetの真似 - 超便利, pythonにはstd::setがないからこういうのか平衡二分探索木は必携だと思う
- 二項係数とかの前計算 - まとめとくと便利
- 素因数分解等 - 色々できる
- dijkstra
- Union-Find - ctrz もつけてる
- セグ木 - い つ も の
- popcount - bin(x).count('1')はありえないほど遅いので。 多倍長でも使う
- 木のテンプレ - 便利,辺の入力と 親とトポロジカル順序と子を全て出す、主に木dp用
- 座圧 - とりあえずしちゃう
需要があればどこかに適当に置いておきます
まとめ
黄色になるとワートリの二期が決まる