お品書き
競技プログラミングとは何か
みなさんは競技プログラミングというものをご存じでしょうか。
競技プログラミングとは、「アルゴリズム」というものを使って、与えられた問題を制限時間以内に解いていくというコンテストになります。
日本だと「AtCoder」というコンテストが有名です。
海外だと「CodeForces」や「TopCoder」というのがメジャーなコンテストです。
私は「AtCoder」に約2年ほど参加しています。
「アルゴリズム」というのは、ある種類の課題を効率よく解いていくための数学的な道具、と思ってもらえればいいと思います。
その道具を使って、問題を解決するためのコードを作成していく、という作業を競技プログラミングのコンテスト中では行っていくことになります。
今回の記事はどういう内容か
今回の記事では、競技プログラミングで使う道具である「アルゴリズム」で必要なものを厳選して、競技プログラミングにおいてどのレベルを目指すかで分類したロードマップをお送りしようと思います。
つまり、みなさんのレベルに合わせて必要なアルゴリズムを限定して挙げるのと、それらアルゴリズムの簡単な説明をします。
私自身、競技プログラミングがめちゃくちゃ強いというわけではありませんが、AtCoderでは上位数パーセントに入るくらいのレーティングは維持できているのかな、という感じです(青色、という上から4番目のレーティングを踏んでいます)。
そんな私が、初級者・中級者の方に向けて、どういったアルゴリズムを勉強すれば、競技プログラミングの腕前が上がっていくのか、という疑問を解決すべく、ロードマップ的なものを作成しましたので、それをもとにして勉強してもらえればと思っています。
簡単に表を作成しました。
| 対象者 | 必要なアルゴリズム | アルゴリズムを用いる問題 |
| 初心者 | ・全探索 ・剰余定理 → 最大公約数 ・ フェルマーの小定理 ・データ構造 (多次元配列・スタック・キュー) | ・いろいろな基本問題 ・最小公倍数・互いに素な数 ・様々な問題の基礎 |
| 初級者 | ・二分探索 ・素数列挙 → エラトステネスの篩 ・bit全探索 ・グラフの基礎知識 ・ データ構造 (ヒープ・優先度付きキュー) ・累積和の処理 | ・アドレス取得 ・ 高速な素数判定が必要な問題 ・ 場合の数の全探索 ・幾何的な問題 ・bfs , dfs の実装など ・合計を求める問題 |
| 中級者の入り口 | ・グラフの基礎探索 → dfs , bfs, ダイクストラ法 ・動的計画法 ・順列の生成 ・木の実装 | ・経路問題系 ・本当にどこででも登場 ・巡回セールスマン問題 ・島を渡る、移動するタイプの問題 |
| 中級者 | ・Union-find ・逆元 ・木・グラフの探索 → クラスカル法 | ・分類問題 ・数を復元するタイプの問題 ・最小全域木 |
私がAtCoderを2019年から参加して、主観的に「こういった優先度で勉強していけばいいんじゃないかな」と考えてみた結果の表が上になります。
太字になっているものは、記事で解説が入っています。
それ以外のものは、参考にすべきリンクのみが貼ってあります。
難易度よりも、使用頻度を重視して作ったので、「絶対このアルゴリズムの方が難しい」という意見も多数あるかと思いますし、私もそう思うのがいくつかあります。
表の見方としては、「対象者」のところが今自分のいるレベルだと思ってください。
それで、次のレベルにいくために必要なアルゴリズムのリストが右に書いてある、って感じです。
自分の必要と思う部分だけ見てもらえればと思います。
1. 初心者の方が必要なアルゴリズム
まず、初心者の方が競技プログラミングに参加するときに必要なアルゴリズムを紹介しようと思います。
ここでいう初心者とは、
- プログラミング言語の知識がある
- アルゴリズムの知識はない
- 競技プログラミングって何？
という条件に合った人を想定しています。
では、早速紹介していきましょう。
1.1 全探索
全探索とは、その名の通りで、「考えうるすべてのパターンを探索していく」という愚直なアルゴリズムのことです。
もはやアルゴリズムと言っていいのかもよく分かりませんが…
例えば、3次元配列で考えうるパターンを全て調べようと思ったら、
for i in range (max_i):
for j in range (max_j):
for k in range(max_k):
search_method()という風にforループを3回回せば、全探索を行うことができます。
簡単で直感的なアルゴリズムですよね。
数学的な知識がなくても、プログラミング言語を使ったことがあればだれでも実装できると思います。
こういった全探索のメリットとデメリットは以下の通りです。
[メリット]- 実装が簡単
- アルゴリズムの第一歩として最適
- 計算量が多い。
- 実用性が低い
デメリットについて補足で解説します。
計算量が多いというのは、例えば1つの次元の長さが\(10^{6}\)であった場合を考えてみてください。
これを上にあげた「3重forループ」の全探索で実装するとどうなるでしょうか。
そう、計算量は\(O(10^{18})\)となってしまい、スパコンを使っても現実的な時間で解くことができなくなってしまいます。
さらに派生して、実用性が低いというのもデメリットです。
競技プログラミングというのは「数学的なアルゴリズムをいかに効率的に使うか」を問うためのコンテストなので、全探索のような単純明快なアルゴリズムで、コンテストの問題が解決することはほとんどありません。
というわけで、全探索の実際の出番は少ないというのが現状です。
とはいっても、全探索がすべてのアルゴリズムの基本となります。
「全探索した場合と比較して、これだけ計算量が違うんだよ」というのが、今後のアルゴリズムを勉強するモチベーションにもなります。
よって、初心者には「全探索」がまずはオススメというわけです。
1.2 剰余定理
初心者の人に勉強することをオススメするアルゴリズム2つ目は「剰余定理」です。
アルゴリズムの記事と言っておいて申し訳ないのですが、「剰余定理」はアルゴリズムというよりも、競技プログラミングでかなり頻繁に用いるテクニックということで、先に紹介しておきます。
剰余定理といっても、初心者の人が実際に覚えてほしいのは以下の2つです。
- 最大公約数\((gcm)\)の求め方
- フェルマーの小定理
順番に解説していきます。
最大公約数 \((gcm)\)の求め方
最大公約数をご存じでしょうか。
定義を説明すると、「数個の数において、それらすべてを割り切るような最大の自然数」のことです。
簡単な例を考えます。6と12の最大公約数を考えてみましょう。
これら二つの数を割り切る自然数として、『1, 2, 3, 6』がありますね。最大公約数とは、この中で最大のもの、つまり『6』ということになります。
これを簡単に実装できるようになっておいてほしいということです。
特に、2つの数の最大公約数を求めるアルゴリズムは以下のようになります。
def gcm(x,y):
if y%x == 0:
return x
else:
return gcm(y,y%x)簡単にいえば、「互除法」という数学の考え方を使うことで、このアルゴリズムの正しさがわかるのです。
競技プログラミングでは、最大公約数を用いたアプローチが効果的な問題が多数存在します。
フェルマーの小定理
次に紹介するのは、「フェルマーの小定理」です。
定理の内容を先に説明すると、こんな感じです。
\(pが素数で、aがpの倍数でない自然数のとき、\)
\(a^{p-1} \equiv 1 (mod\, p)\)
が成り立つ。
この定理を知っているか知っていないかで、問題が解けるかどうかが変わったりするのはもちろんとして、計算量に大きな違いが出たりすることがあります。
本来なら\(O(10^{n})\)かかるような問題が、たった\(O(n)\)の計算量で解ける問題もありましたね。
証明は高校数学を理解していれば難しくはありません。
詳しくは以下のサイトに掲載されています。
参考 フェルマーの小定理の参考サイトフェルマーの小定理の証明と例題1.3 データ構造 (多次元配列・スタック・キュー)
1.3.1. 多次元配列
参考 多次元配列の参考サイト【Python入門】2次元配列の使い方をマスターしよう！1.3.2. スタック
参考 スタックの参考サイトスタックとキューを極める！ 〜 考え方と使い所を特集 〜1.3.3. キュー
参考 キューの参考サイトスタックとキューを極める！ 〜 考え方と使い所を特集 〜2. 初級者の方が必要なアルゴリズム
さて、初心者の方に必要なアルゴリズムを紹介しました。
次に競技プログラミングに少し慣れてきたあたりで勉強した方がいいアルゴリズムを2つに厳選したので、紹介します。
2.1 二分探索
まず紹介するアルゴリズムは「二分探索」です。
アルゴリズムの中ではかなり代表的なもので、情報系の大学に通っていた方はCS(Computer Science)の授業で必ず習ったと思います。
二分探索の考え方は単純です。
「規定値より高いか低いか」を、「中間地点にある値」に対して適用し続け、配列を半分に、半分にとしぼっていく方法になります。
例えば、大きさ\(n\)の配列\(a\)で「\(m\)より大きい最小の値は配列の何番目にあるか」というのを求めたいとします。
そのアルゴリズムを二分探索で実装すると、以下のようになります(配列は大きさに関して昇順にソートされているとします)。
lower_bound = -1
upper_bound = n
while upper_bound - lower_bound > 1:
mid = lower_bound + (upper_bound - lower_bound) // 2
if x == a[mid]:
return mid
elif x < a[mid]:
r = mid
else:
l = midC++では、STL(標準ライブラリ)に、二分探索を1行で記述できるようなメソッドが含まれています。
pythonだと、上のように関数を別で定義する必要があるでしょう。
上の問題は、計算量\(O(logn)\)で解くことができます。
こういった感じで、対数をとって計算量を記述できるようなアルゴリズムは、大体の場合かなり汎用性が高いです。
2.2 素数列挙
次に必要となるアルゴリズムは、素数列挙を行うためのアルゴリズムとなります。
競技プログラミングでは、「ある決められた範囲の素数を列挙する」という操作が必要になる場合があります。
今回紹介するのは、最も使用頻度の高い「エラトステネスの篩(ふるい)」というアルゴリズムです。
これを簡単に説明すると、
数を小さい方から順番に見ていって、「除外」されていないものは素数として判定する。
そして、その倍数を最大数を超えない限り除外し続ける。
というものになります。
つまり、2を素数として認識すると4,6,8…を除外します。
次の3は「除外」されていないので素数として判定し、3,9,15…が除外されます。
これを、求めたい範囲の最大数まで行うというわけです。
計算量に関して、今回の記事で細かい説明は避けますが、\(O(nloglogn)\)になることが知られています。
数式的には、計算する量は
$$ \frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + …$$
よりも小さくなるのですが、これが上から\(nloglogn\)という量で抑えることができるのです。
\(loglogn\)という量は、よほどnが大きくない限りかなり小さな数とみていいと思います。
というのは、\(n=10^{10}\)でようやく\(loglogn = 1\)になるからです。
\(n\)が1000万くらいの量であれば、本当に一瞬で素数を列挙することができます。
かなり強力なアルゴリズムですよね。
ちなみに、全探索でそれぞれの数に対して素数判定アルゴリズムを使うと、\(n\)が100万でも計算が間に合うことはありません。
2.3 bit全探索
参考 bit全探索の参考サイトbit全探索について簡単にまとめる2.4 グラフの基礎知識
参考 グラフの基礎知識の参考サイトグラフと木2.5 データ構造 (ヒープ・優先度付きキュー)
参考 データ構造 (ヒープ・優先度付きキュー) の参考サイト優先度付き待ち行列2.6 累積和の処理
参考 累積和の処理の参考サイト累積和を何も考えずに書けるようにする！3. 中級者になりたての方が必要なアルゴリズム
競技プログラミングに大分親しんできた人のことを中級者と呼ぶことにします。
具体的な基準としては、
- 初級までのアルゴリズムを理解している
- AtCoderで最初の3問は安定して通すことができる
- 高校数学までを理解している
という感じでしょうか。最後は部分的に必要という感じなので、高校数学すべてを理解する必要はありませんが。
ここら辺から、ちょっと複雑なアルゴリズムが混じってきて、かなり頭痛がしてくる時期と言っていいと思います。
特に、初めに紹介する「グラフ」という概念は、数式的と言うより幾何的な感覚が必要になるので、かなり苦労するかもしれません。
ちなみに、私は約1年間グラフを全く理解できずに、あきらめていた時期がありました。
さらに2つ目の「動的計画法」もまぁまぁ癖が強いです。
考え方としてはそこまで難しくないかもしれませんが、なかなか実際の問題で動的計画法を実装するには大変です。
かなり慣れが必要なアルゴリズムという感じですね。
さて、それぞれの概要を説明することにしましょう。
3.1 グラフの基礎問題
グラフの基礎問題には、以下の3つがあります。
- 深さ優先探索
- 幅優先探索
- 単一始点最短経路問題
最後のだけ難易度が高めです。
順番に解説します。
3.1.1. 深さ優先探索 \((dfs)\)
深さ優先探索\((dfs)\)とは、その名の通り「あるグラフ(特に木が多いです)を探索するときに、できるだけ深いところまで探索して、その後に横方向の幅を変えていく」というアルゴリズムのことです。
\(dfs\) をそのまま実装するという問題はほとんど出ませんが、ある木・迷路において経路が連結(つながっている状態のことと思ってもらえれば大丈夫です)しているか判定するによく使います。
コードは長いので省略します。
以下のサイトに問題例・実装例が掲載されているので参考にしてみてください。
参考 深さ優先探索の参考サイト深さ優先探索(Depth First Search)の基本3.1.2. 幅優先探索 \((bfs)\)
幅優先探索\((bfs)\)は、ある意味深さ優先探索とは対照的なアプローチのアルゴリズムです。
深さ優先探索が「深さを優先して、(横方向の)幅を後回しにする」というものだったのに対し、幅優先探索では「幅を優先して、深さを後回しにする」というものになります。
幅優先探索の方が、深さ優先探索よりも頻繁に用いるイメージがありますね。
こちらも詳細なアルゴリズムの説明は省略します。
詳しくは以下のサイトをご覧ください。
参考 幅優先探索の参考サイトBFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜深さ優先探索と幅優先探索の2つの違いをまとめると、以下のようになります。
| 計算量 | メモリの使用量 | |
| 深さ優先探索 | 若干多くなる場合が多い | 少ない |
| 幅優先探索 | 少なく済む場合が多い | 多い |
問題によって使い分ける必要があることがわかりますね。
メモリの使用量が激しいようなら深さ優先探索、計算量をできるだけ抑えたいなら幅優先探索、といった感じで使い分けることが多いです。
3.1.3. 単一始点最短経路問題
単一始点最短経路問題という、ちょっと名前は長めですが、内容はシンプルな問題があります。
簡単に単一始点最短経路問題を説明すると、
グラフにおいて、ある始点Sから、他のそれぞれの点への最短経路の大きさを求める問題のこと
という風になります。
この問題を解くに当たっては、「ダイクストラ法」というアルゴリズムを用います。
厳密には、ダイクストラ法を用いるには、グラフの辺の重みが正の数である必要がありますが、中級者レベルの問題ではあまり気にしなくて良いでしょう。
ダイクストラ法の詳しい証明は省略します。
手順だけを説明すると、
- 最短距離が分かっている点の集合{S}から、その補集合{V-S}に向かって出ている最短の辺に注目する。
- その辺の出ている点をSをする。辺の向かう先の点Tの距離の値と、Sの距離の値 + 辺の重みの値を比較する。
- 短い方の値で最短経路を確定し、Tを{S}に含める
- これを{V-S}が空になるまで繰り返す
という風になります。
私は、ダイクストラ法を理解して自分で実装できるようになるまでに大分苦労しました。
ダイクストラ法の詳しい説明は以下のサイトを参照してください。
参考 ダイクストラ法の参考サイト初心者のためのダイクストラアルゴリズム3.2 動的計画法
さて、中級者の方が2つめに勉強すべきアルゴリズムは「動的計画法」です。
一応簡単に動的計画法の説明をすると
動的計画法(Dynamic Programming)は、作成した配列を再利用することで、配列が動的(Dynamic)に変化するようなアルゴリズムのこと。
競技プログラミングでは、メモ化再帰などを用いて、再帰的に配列を変化させる場合が多いです。
こちらに関しては、私が専門的に解説した記事があるのでご覧ください。
3.3 順列の生成
参考 順列の生成の参考サイト順列の全探索をするプログラム（競技プログラミング向け）3.4 木の実装
参考 木の実装の参考サイト明日使える便利な木構造のアルゴリズム4. 中級者の方が必要なアルゴリズム
4.1 Union-find
参考 Union-findの参考サイトUnion-Find木の解説と例題4.2 逆元
参考 逆元の参考サイト競技プログラミングにおける剰余の基礎と mod 逆元4.3 木・グラフの探索 → クラスカル法
参考 クラスカル法の参考サイトクラスカル法による最小全域木を求めるアルゴリズム5. 終わりに
今回の記事では、競技プログラミングでのアルゴリズムの実力をつけたい人に向けて、厳選してアルゴリズムを紹介しました。
正直、これらだけでは足りないですが、紹介したものは全て必須で、自分が最も使用頻度が高いと思っているものばかりです。
なので、「上を目指したい」という方は全てのアルゴリズムを勉強しておいてほしいと思います。
また、アルゴリズムに関する詳しい記事も随時投稿予定です。
それでは、またお会いしましょう。
