挨拶
にゃ～ん
本題
昨日のAtCoder Beginner Contest 347でAtCoderのレーティングが2000を超え、ついに入黄しました！
オンサイトやバーチャルコンテストでご一緒した皆様、日頃のコンテスト結果のポストにいいねを押してくださった皆様ありがとうございます！
話したい事
黄色になったけどコンテスト中に黄difの問題通せた記憶あまりないな。――と思って入青から入黄までのRated参加したコンテストのAC率を集計しましたがなんと打率1割以下。
ということで黄difがそこそこ安定して通せるならきっとすぐ黄色に上がれるだろうし、解けなくても青dif以下をしっかり素早く倒せれば黄色に上がれるぞというお話。青→黄を目指す競プロerの希望になれたら幸い。
精進
おすすめの精進方法について軽く触れます。
- コンテストに参加しましょう
- 体調不良/用事などでなければRatedで出ましょう。敵前逃亡は許されない
- AtCoderが当然一番のお勧めですがyukicoder(ほぼ毎週/金21:00頃)やCodeforces(週2くらい/深夜😿)などもぜひ
- バーチャルコンテストに出よう
- AtCoderでコンテストがない日は21:00からAtCoder Problemsでまよこんが開催されます。おおよそABCと同じようなセットが組まれているので実質一週間で7回ABCに出られると言っても過言ではない
- 解けない問題にしっかり悩みましょう
- 悩んだけど実は特定のアルゴリズムを知ってますかというだけ、というケースも確かにあります。しかし「～～の理由でこの問題にこのアルゴリズムは使えない」という経験を積めば、失敗した試行の分だけ次回から「はずれ方針」から早く復帰できます
- 手持ちのアルゴリズムを使い切るまでは悩みましょう
アルゴリズム
優先度の高いアルゴリズムの話。黄dif、橙difの問題に精進してると知らないアルゴリズムが無数に押し寄せてきます。一個一個埋めていきますが、ぶっちゃけこいつらは数年に1度しか出ない気がします。
なので汎用性の高いアルゴリズムを深く学ぶ方が期待値は高そう。このレベル帯で丁度良いのをいくつか置いときます。
- (Lazy) Segment Tree
- 最近ありえんくらい出てます。水dif、青difの重鎮
- 基本的なモノイドたちはいつでも使えるように(https://betrue12.hateblo.jp/entry/2020/09/23/005940)
- AtCoder Tagsにあるセグ木の問題をガンガン解きましょう(https://atcoder-tags.herokuapp.com/tags/Data-Structure/Segment-Tree)
- 平方分割
- 結構いろいろなパターンがあります
- 「数列＋クエリ」の問題でクエリを平方分割したり、逆に数列を平方分割したりなど
- Mo's algorithmはその場で書こうとして破滅する人を何度か見ているのでライブラリ化推奨
- 文字列アルゴリズム
- Rolling Hashは寒色でも必修になりました
- Suffix Array＋LCPは強力。Z_algorithmを系として得ることも可能
- Trie木勉強するならAho Corasick法もぜひセットで
末文
運よく黄色に上がれた側面が強いので今晩のARCで最速落青を決める可能性は割とあります。ちなみにCodeforcesはOrangeに上がった次のコンテストでVioletにひっそり転落してます。(ΔRating = -95)
お読みいただきありがとうございました。
追記
このあと無事落青しました。