AtCoderで黄色に到達しました
こんにちは。この度は AtCoder で黄色に到達したため記事を書いてみようと思います。
解いた問題数とか
皆さんお馴染みの AtCoder Problems の画像を貼っておこうと思います。
割とバランスよく解いている方だと思っています。
精進について
上の解いた問題数とコンテストの参加回数を見るとわかるのですが、自分から過去問を解きに行くということはたまにしかしていません。
基本的にコンテストに参加して解けなかった問題を解きなおすということを繰り返しています。
これは成長が遅くなる理由の一つでもあると思いますが、ABCなどは開催頻度が高いため参加して復習を行うだけで十分な成長が見込めると思っています。(AtCoder だけでなく、Codeforces や yukicoder の参加もおすすめです!)
新たなアルゴリズムの学習方法
ABCでは、アルゴリズムを知っているだけで有利に立ち回ることができます。
AtCoder で水色から青色の人は、Library Checker を見て回ったり、ABC の G 問題を積極的に解いたりすると知らないアルゴリズムを見つけることができると思います。
正直なところ、考察力などは青色になった頃からはあまり変わっていないと思っていて、既知のアルゴリズム・テクニックが増えたことにより ABC で良い成績を取れる確率が格段に上がったと感じています。(実際、ARC などではあまり良い成績を取れていません。)
作問について
作問は学習したアルゴリズムに対する理解を深める良い機会になるので実力の上昇に繋がったなと感じています。
MojaCoder という誰でもコンテストを開催できるサービスで MMA Contest という名前のコンテストを開催したりしていました。(毎回 Tester をしてくれる sepa_38 くんに感謝......)
そういえば、2023/5/28(日) に電気通信大学で MMA Contest 015 がオンサイトで開催されるようです。
開催前にこの記事を見てくれた方はぜひ参加してみてください。
ライブラリ整備について
ライブラリの整備は個人的にはかなり重要な要素でした。
自分自身は実装速度やタイピングの速度がそもそもあまり速くないため、ライブラリを積極的に作成して補っています。
また、脳のリソースを余計なところに割かないで済むというメリットもあります。
ライブラリの整備に興味がある方は Library Checker を埋めてみると良いと思います。(最近は更新が活発になってきており良いです。)
学んだアルゴリズムなど
ここで自分が学んだアルゴリズムを書いても需要がないと思うので、ABC の G 問題に出題されたことのある学ぶだけで即効性のありそうなアルゴリズム・テクニックを箇条書きで書いていきます。(もしかしたらネタバレになるかもしれません)
- 拡張ダイクストラ
- 行列累乗
- 最小費用流、最大流
- 添え字和での畳み込み
- 半分全列挙
- 平方分割
- ベルマン-フォード法
- bitsetによる高速化
- xor基底を掃き出し法で求めるやつ
- Baby-step Giant-step
- Convex Hull Trick
- Euler Tour
- Heavy Light Decomposition
- Lazy Segment Tree
- LCP Array
- Mo's Algorithm
- Suffix Array
- Z Algorithm
終わりに
これからもぼちぼち頑張っていきます。
ここまでお読みいただきありがとうございました。