概要
WMMCの17日目の記事です。マイクロマウスについて書くことがなかったので、趣味の競プロについて話したいと思います。
競技プログラミングとは
競技プログラミング( 通称競プロ )というのは、アルゴリズムの問題をプログラミングで解く競技です。毎週AtcoderというサイトでAtCoder Beginners Contest（通称ABC）が開催されていて、1万人程度が参加して競います。解いた問題数や提出の早さで順位が決まります。その結果に応じてレート・色が変動します。
入水とは
レートには数値と別に色というものが存在します。具体的には、レートが400上がるごとに色が変更されます。低いほうから順に、黒・灰・茶・緑・水・青・黄・橙・赤と上がっていきます。この中の水になれました。
水色は真ん中ぐらいの色なんですが、色が1個違うごとに人数が指数関数的に変わるので、僕みたいな凡人には意外と厳しいです。僕は緑で1年以上沼りました。
始めた経緯・変遷
高校二年生の秋に同級生に勧められて始めました。オンラインで簡単にコンパイルできる環境や、レートという明確な報酬が飽き性の僕にも刺さり、ハマりました。まず最初に、「競技プログラミングの鉄則」という本を買って勉強しました。
緑色になったあとは、モチベが少し減ってしまってコンテストに出る頻度が減りました。大学入学して、競プロのサークルに入ったのでそこで強い人に教えてもらったりして練習も再開しました。
練習方法
AtCoder Problemsというサイトがあって、そこで過去問を閲覧したり、自分が今まで解いた問題を確認することができます。
過去問は色で難易度付けされていて、例えば緑色の難易度の問題は「緑色の人の約半分が解けた問題」を表しています。ちなみに同色難易度でも昔と今で結構難易度差があります。
練習するときは、Atcoder Problemsから自分と同色ぐらいの問題を適当に選んで解くというのをやっていました。
学んだ知識
競プロの問題では、様々なアルゴリズム・データ構造の知識を組み合わせて問題を解きます。学んだテクニック・アルゴリズムをまとめてみました。パッと思いつく範囲では以下の通りです。
・全探索
・数学（整数問題・幾何・外積など）
・二分探索
・幅優先探索（BFS）
・深さ優先探索（DFS）
・set・map
・ダイクストラ法
・ワーシャルフロイド法
・ベルマンフォード法
・DP
・木DP
・Euler Tour
・TRIE木
・全方位木DP
・累積和
・主客転倒
・Union Find
・Segment Tree
・Lazy Segment Tree
・BIT
・Rolling hash
・ダブリング
・半分全列挙
・Suffix Array
・FFT
・Flow
・その他
下の4つくらいは使いこなせるほどは習熟してないです... 。本番で問題が解けるようにするためには、アルゴリズムをただ知るだけじゃなく類題をいくつも解かないとダメでした。
ライブラリ作成
問題でよく出てくるような処理・アルゴリズムは事前にライブラリで用意しておきます。これによって解く時間を早めてパフォーマンスを上げることができます。僕は以下を用意しました。
・各種マクロ
・ランレングス圧縮
・素因数分解
・エラトステネスの篩
・最長増加部分列
・Rolling Hash
ランレングスは途中の処理とかで頻出で、滅茶苦茶役に立っています。
マイクロマウス競技に役に立ちそうな知識
僕はマイクロマウスに全然詳しくないので、イメージで書きます。あと参考になりそうな記事を貼っておきます。
・計算量の概念 (https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0)
・幅優先探索 (https://qiita.com/drken/items/996d80bcae64649a6580)
・深さ優先探索 (https://qiita.com/drken/items/a803d4fc4a727e02f7ba)
・深さ優先探索 (非再帰) (https://qiita.com/hakatashi/items/90c5835973bd062c1cf3)
・ダイクストラ法 (https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e)
・A*アルゴリズム (https://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7)
なんか思ったより少なかったです（普通にみんなが知ってるやつですね）。初めてのアルゴリズムを使うときは、Atcoderとかで上のアルゴリズムだけを使うような問題があると思うので、一旦そこで実装してみて提出してみるとイメージが掴めるんじゃないですかね?!
さいごに
みんなもやってみてね!