1.はじめに
2023年の1月半ば、本格的に競技プログラミングをやろう！と思い立って4ヶ月ほど経った2023/05/27のABC303にて晴れて入茶したので区切りとして色変記事を書いています。
2.自己紹介
情報科にいる高専4年生です。競プロを始めるまではPythonを少しやっていたくらいでちょうど競プロを本格的に始めたあたりからRustを始めて、Rustは今でも僕の大切な相棒として活躍してくれてます。
Rust,大好きです。
授業でCをやってますが内容的にはAPG4bくらいのことしかしていません。ファイル操作は一応やりましたが競プロの文脈ではさほど関係ないのでまあいいでしょう。
3.競プロを始めるきっかけ
そもそもアカウント自体は2021年くらいから作ってはいましたがよくわからず放置しており、初めてコンテストに出たときも乏しいPythonの知識で軽いノリで出たのでアルゴリズムなどは全く知りませんでした。そして12月ごろ、Rustを勉強し始めて基本的な文法の勉強がてらAtCoderのA,B問題を埋めていました。そしたらコードを提出してACが出る快楽に溺れてしまい、そのまま現在まで続けています。少し話がそれますが、最初は「競プロはアプリ作りたいとかWeb開発したい人はやらないでいいじゃん..なんでみんなやるんだ...？」と思っていました。YouTubeやネットの記事を見てもそう思っている人はそれなりにいるみたいです。が、今自分が感じているのは競プロは自分の技術どうこうではなく、何より
「楽しいからする」
これに尽きるなあ、と実感しています。やってみて面白ければ続ければいいしそうじゃなかったら辞めたっていいわけです。正解は人それぞれです。
4.解いた問題数など
AtCoderProblemsに表示されているものの中で関係ありそうなものを載せます。解く問題の量など、参考になれば幸いです。
4 - 1.難易度別AC数
なぜかわかりませんがそんなに解いていません。Streak(何日連続で解いたことのない問題をACしたか)を維持させたくて一時期、毎日1日1問Aを解く、みたいなずるいことをしていたのでその分少し多くなっているかもしれません。Bはコンテスト中に解いたものが半分、精進として解いたのが半分くらいです。Cはそれよりも少しコンテスト中に解いたものの比重が大きいです。Dに関しては1回だけ時間内にACできましたがそれ以外は解説ACです。
これの他にも典型90問を何問か解いています。あそこにある問題は難しいものが多いので最初のうちは避けがちですが☆2個のものから少しずつ解いてみたりわからないものは解説見たりして色々解いてみることをとても強くお勧めします。というのも典型90問に載っている問題はほとんど重要な考え方だったり計算量を落とすテクニックが必要だったりで学ぶことがとても多いです。まだ手付けてない方いらっしゃればぜひ取り組んでみてください！
4 - 2.言語別AC数
昔Pythonを書いていたのでPython系が少しありますが大抵Rustで解いているのでまあ妥当と言えば妥当です。C言語は暇な時に簡単なA問題を解きました。あと解説のコードが大抵C++のためC++を読めるようになりたくて勉強してた時期があったのでC++も少し混じっています。
それ以外のSed,Vim,Bashたちですが、これらは灰色のうちはやらなくてもいいと思います。もちろん、これらをある程度習得すれば簡単な文字列操作をするような問題を超短いコードで解けるので早解きにつながります。ですがこれらをやるくらいなら他の優先すべきアルゴリズム(DFSなりbit全探索なり)を学んで解ける問題を増やしたほうがはるかに有用でしょう。自分はとある方に憧れたので少し手を出してみましたが、、まあ、、やらなくていいでしょう、、、。「これSedでどうやって解くんだっけ？」とかなって解くのが遅くなってしまっては本末転倒ですから...
4 - 3.その他アチーブメント
AC数に関しては個人差があるのでなんとも言えないので多いか少ないかはみなさまの手に委ねます。ここにあるLongest Streakを伸ばすために先述した1日1問簡単なAを解く、というあまり意味のないこと(いわゆる虚無埋め)をしていました。振り返ってみると、これで力がついたとは言えないかもしれませんが毎日1問は解こう！という習慣づけとしてはまあ悪くなかったんじゃないかな〜と思っていますが真偽の程は定かではありません。やらないよりはやった方がいいのかもしれませんがまあやらないと上達が遅れるかと言われるとそんなこともないでしょう。
5.身につけたアルゴリズムやデータ構造たち
アルゴリズムと呼んでいいかわからないものも混ざっていますがとりあえず列挙していきます。かなり丁寧に解説しているので知っている項目はスパスパ読み飛ばしてもらって差し支えないです
- n重のfor文を使った全探索 : 一番の基礎です。一見ややこしそうなものもこれだったりするのでパッと見使わなそうに見えても一回は疑ってみるといいかもしれません。難しめのを挙げるとB - Find snuke でしょうか。
- bit全探索 : コンテスト中に解けたことはありません(というか一回しか見かけませんでした)がCで出ているのでやっといて損はないはずです。C - Coverageがお勧めです。
- UnionFind : グラフが連結かどうかをみるやつです。茶色に行くのに必ず必要かと言われると怪しいですが何回か出ていたのと最初はあまり難しくないので割とコスパは高い方だと感じます。 C - Don't be cycle と C - Count Connected Components がお勧めです。
- 文字列の置き換え : かなり大事です。大抵の言語に文字列のXXの部分をYYに変換するメソッドが標準でついているのでそれを使うとかなり楽です。先ほど述べたVim,Sedを使うとこの問題は驚くほど短く書くことができます。B - Cat がお勧めです。C - PC on the Table のようにC問題でも出ることがありますがやることは同じです。
- Set(集合) : 今回これが一番言いたいかもしれません。setは本当に優秀でsetだけ別で記事を書きたいほどです。配列に対して毎回Nが含まれているか？みたいなことをしているとTLEになって計算量的に厳しそうな問題はsetを使いましょう。Xが含まれているか、Xを追加する、Xを消すの3つを覚えていれば十分やっていけます。使う問題はあげればキリがありませんがこれ なんてどうでしょうか。中級編としてこれも挙げられます
- 座標圧縮 : 地味によく使いました。D - Change Usernames みたいにUnionFindを使いたいけど入力が文字列で与えられる時、文字列をsortすることで各文字列に対応する値が使えるので解きやすくなります。Rustだとvecに
binary_search(&K)という配列内で二分探索してくれる便利な機能があり、値を簡単に手に入れられるため便利です。 - Zobrist Hashing : 茶色になるためならやらなくていいですがD - Three Days Ago を解いてる時たまたま見つけました。bitを使ってなんやかんやするタイプのやつなのでbitという概念に慣れて余裕がでたらで大丈夫です。重ねて言いますが茶色になるだけなら本当に学ばなくて大丈夫です。
- 正規表現 : 知らなくてもなんとかやっていけますが知ってるととても便利です。B - chess960 のような問題を正規表現を使って解くか使わないで解くかだとやはりだいぶ変わってきます。使わないで解いているとプログラム内の変数が変に散らかったり頭がゴチャゴチャになったりする(自分がなりました)のでやってるとバグらせることが少なくなるかもしれません。お役立ちテクニック程度なので知らなくてもやっていけはします。
- デック(Deque) : 先頭や末尾に追加したり先頭や末尾を取り出したりできるデータ構造です。Rustにキューがなかったことも相まってよく使っていました。最近だとB - Same Map in the RPG world で使いました。
- 累積和 : 本番では解いてないですが典型をはじめとした色んなところで使いました。中には少し工夫が要るものもあるのである程度知っている人もおさらい程度に見ておくといいでしょう。例題としては010 - Score Sum Queries がお勧めです。累積和かどうかわかりませんが004 - Cross Sum も基本的にやることは同じなのでやるとよいでしょう。
- DFS : 再帰、非再帰どちらでも大丈夫だとは思いますが大体の考え方とざっくりした実装方法は頭の片隅に入れておくことをお勧めします。自分はC - Make Takahashi Happy で大体の仕組みと実装を理解しました。制約が大きくないので実装しやすいです。
- 約数全列挙 : たまに使いました。約数が欲しいという用途より約数の個数が見たい時に使うことの方が多かったような気もします。例としてはC - Four Variables が挙げられます。
- 素数判定、素因数分解 : ある自然数Nに対して$O(\sqrt{N})$で素数判定ができるのはもちろんのこと、C - Happy New Year 2023 のように$O(\sqrt[3]{N})$で素因数分解する、みたいなプチ応用みたいなこともできると頼もしいです。
こんな感じでしょうか。細かすぎるもの(大文字、小文字の判定など)を挙げるとキリがないので粒度があまり統一されていませんが例題として挙げた問題は頻出のものが多いのでやっておくとかなりいいと思います。(Zobrist Hashを除く)
6.あまり理解していないアルゴリズムたち
- 二分探索 : Rustの
binary_searchでなあなあにしてきたのでちゃんと実装できるかと言われると、うーん...仕組みは理解してますが自力で通すのはまだ難しいです。 - 順列全探索 : 灰コーダーが習得すべきアルゴリズムとして順列全探索がよく挙げられますが自分はまだコンテスト中に使ったことはありません。一回だけ使う問題がありましたがUnionFindを使って通したせいでまだ耐えています。そろそろやらないといけませんね...
- DP(動的計画法) : 本当に苦手です、、この問題はDPを使ったら解ける！と気付くことくらいはできますがどう落とし込むかまでは思いつかないのでこれはEDPCをたくさん解くなりして慣れるしかないでしょう、がんばります。
- 最小全域木 : クラスカル法の仕組みは頭に入ってますがだからと言ってコンテスト中に解けたことがあるわけでもないのでまあ優先順位はまだ下の方です。
7.コンテストの問題を解く以外にやったこと
- 典型を数問埋めました。数問とはいえかなり力がついている実感が湧いているのでやはり典型は偉大です。
余談:アルゴ式を埋めてる方もいるみたいで、自分もやろうかと思ったのですがRustの標準入力を簡単にしてくれるproconioというクレートが非対応だったのでしませんでした。(Rustは標準入力がとてもややこしく、めんどくさいのです...気になった方は調べてみてください) - 鉄則本を買おうかと思ったのですが伸び悩んでからでいいかな〜と思ってまだ買っていませんが、近々買うかもしれません。代わりと言ってはなんですがこちらのツイートに記載されているPDFを暇な時に読んでいました。2次元累積和や部分配列の最大和を求める問題、枝刈法などはこれで学びました。無料とは思えないボリュームとクオリティなのでぜひダウンロードして読んでみてください！
「競技プログラマーハンドブック(Antti Laaksonen氏著)を翻訳・公開しました
— Akira KANAI (@recuraki) January 7, 2023
基本的テーマから発展的テーマが300ページ超に渡って記載されており目次を見るだけでも興味深いハンドブックです。
「こんなのあるんだ！」という皆様のわくわくの助けになれば幸いです。
PDF: https://t.co/in2H7x6QdW pic.twitter.com/QaaXOvs7yc - 自分が今まで解いてきた問題はWeb上に解法提出したコードをセットで残してあります。類題が出た時どうやって解いたか見返しやすくしたり、自分がどういう経緯でその考えに至ったかなどを書き残しておくと解法の正しさを言語化しやすくなって論理的に考える力がつきやすくなるので何かしらに残しておくことをお勧めします。
自分の書いた備忘録一覧はこちら
8.終わりに
茶色とはいえ、初めての色変、とても嬉しかったです。なかなか茶色になれなくて伸び悩んでいる方やそもそも競技プログラミングを始めるか迷ってる方、競技プログラミングをはじめたての方にこの記事が届いて、役に立ってくれると幸いです。かなりざーっと書いたのでもしかしたら追記を入れるかもしれません。
2023/05/28 - sou31415