はじめまして
初めまして、天才見習い Qiita ライターの NokonoKotlin ことおこていゆ (昔はノコノコを名乗っていましたが、コンフリクトが発生したので今はおこていゆです) です。今回は競プロ初心者 ~ rating 緑ぐらいの人が必要以上に怖がっているものを、個人の経験に基づいて紹介してしていきます。
怖がられがちなものとは
みなさんコンテストが終わった後は何をしますか？Twitter はしてますか？コンテスト後の Twitter を眺めていると色んな解法ツイートが流れてきて、中には全然知らなかったー😭みたいなアルゴリズムもあったりしますよね。
自分は現在 AtCoder レーティングが青で、このレベル帯でまだ聞いたことすらないアルゴリズムは本当に怖いものだったりするのですが、レーティング緑あたりの人が怖がっているアルゴリズムは実は全く怖いものではないことがありますよ。というのが今回の記事の内容です。
怖くないんだよ
アルゴリズムが怖いという感想も、どう怖いかと感じるかは人それぞれなので、これから紹介するものが怖くないことの根拠を先に挙げておきます。
- 実装が長くない
- ベースの知識の要求が高くない
- 厳密にわからなくても、そういうツールだと割り切って使える
怖くない最大流
最大流は本当に怖くないです。シンプルなアルゴリズムで良いなら実装は一瞬で終わります。BFS が書ければ実装できるので、要求知識目安はAtCoder Rating 茶色 ~ 緑色 です。
以下に関連記事をいくつか貼っておくので、最大流が何かもあわせてぜひチェックしてみてください。
(外部サイトのリンクを貼るのが規約的にどうなのかわからないので、とりあえず Qiita にあるものを貼っておきます)
フォード・ファルカーソン法とその応用 - アルゴリズムクイックリファレンス８章の補足 by @sasanquaneufさん
怖くないセグメント木
セグメント木は本当に怖くないです。基本的なアイデア (木の高さを抑えるために区間の中間で分割する) は非常に直感的ですし、仕組みがわかれば実装に必要なことも見えやすいです。
セグメント木にも色んな種類がありますが、よく話題になる ACL のセグメント木は抽象化&遅延評価がついていてハードルが高いと思うので、ぜひ自分で実装してみるといいと思います。
マスタリング セグ木 by おこていゆ
要求される知識は AtCoder Rating 茶色程度です。
怖くない平衡二分木
平衡二分木は流石に怖いですが、ただ使うだけなら怖くないです。自分のスタンスとしては他人のライブラリを使うことを全く推奨していませんが、初心者のうちは存分に活用して後から自分で書けば OK だと思います (借りたライブラリは他人の著作物であることを忘れないでくださいね)。
C++ の std::set を補強する目的で平衡二分木が気になっているなら、わざわざ今勉強しなくても g++ 拡張の pb_ds の tree が std::set の上位互換らしい (使ったことナシ) ので、それを使えば良いです。
pb_ds の tree は std::set の操作に加えて以下を行えます。
- 先頭から i 番目の要素を取得
- x より以上の要素が先頭から何番目に初めて現れるかを取得
怖くない modint
modint は本当に怖くないです。怖いポイントは徐算の最適化なのですが、最初のうちは考えなくて良いです。強いて言うならクラスを書くのが競技プログラミング純粋培養の自分にとって難しいポイントでしたが、これはこれで良い勉強にもなると思います。
徐算の最適化とかはとりあえず考えずに、とりあえず書いておくと良いでしょう。
怖くない FFT
青ですら使う機会はほぼありませんが、全く怖くないのでここで紹介していきます。ちょうど最近記事を書いたので、ついでです。
FFT の実装はロジックがわかれば単純明快です。自分の記事ではお気持ちしか解説していませんが、計算量が良いこととその理由まで押さえておけばひとまず問題ないでしょう。
高速フーリエ変換 by おこていゆ
おこていゆ表明
rating を上げる近道はセグメント木と平衡二分木を使えるようにすることだと思っています。この二つは一刻も早くツールとして獲得しておくべきです。
おわりに
まだたくさんあると思います。
いざ書いてみると自分の記事紹介コーナーみたくなってしまいましたが、こんなはずじゃなかったんです😭
随時更新していきたいので、こーゆーのもあるよという意見はコメントまでよろしくお願いします🙇