アルゴリズム

Last-modified: 2016-08-16 (火) 14:15:06

アルゴリズムとは

アルゴリズムとは、大まかに言って「計算の手順」をまとめたものです。
競技プログラミングでは、計算の過程を考え、プログラムを作成するにあたって、アルゴリズムの知識が必要になる事があります。

基礎的な探索

このページはアルゴリズムのページなので、ガンガンアルゴリズムの解説をしていきたいところでですが、まずは基礎体力をつけましょう。そこで基礎的な探索をしっかりできるようになりましょう。計算時間の見積もりのやり方はあとから説明しますが、これができていて単純に探索するだけでは間に合わないような場合でも一回書いてみるとどこで時間をかけてしまっているのかが明らかになるかもしれません。

この探索アルゴリズムとして、深さ優先探索と幅優先探索があります。

深さ優先探索

言ってみれば、行けるところまで行ってしまう探索方法です。

深さ優先探索(wikipedia)

stackを使った非再帰的実装例

このコードでは、二回以上同じ場所を探索しないようにしているような探索を考慮しているので、それとは別の場合を実装したい場合は適宜変更するようにしてください。

stack<int>sta;
bool used[N];
sta.push(init);
for(int a=0; a<n; a++) used[a] = false;

while(!sta.empth()) {
  int k = sta.top(); sta.pop();
  なんか処理(initを含むのでそのあたりを考慮)
  for(int a=kの近傍) if(!used[a]) {
    used[a] = true , sta.push(a);
  }
}

幅優先探索

近いところから順々に調べていくような探索。深さ優先探索と比べると出番が少ないかもしれない。
しかし、priority_queueという特別なqueueではDijkstra法を簡潔に書けたりと、活躍する場合もあるのでこれもきっちり押さえておきたいところです。。

queueを使った非再帰的実装
que<int>qu;
bool used[N];
qu.push(init);
for(int a=0; a<n; a++) used[a] = fasle;

while(!qu.empty()) {
  int k = qu.front(); qu.pop();
  なんか処理(initを含むのでそのあたりを考慮)
  for(int a = kの近傍) if(!used[a]){
    used[a] = true , qu.push(a);
  }
}

練習問題

POJ2386
POJ1164

共通のヒント・戦略

・usedという配列を利用して、探索時に二回以上同じところに入らないように工夫をしましょう
・配列は大きめにとるように心がけましょう。50の制限だと55など。細部の変更で少し大きな領域を取りたくなった時にいちいち変更する場所数が減ります。
・探索時に近傍をうまい実装で探索するために配列を利用しましょう。


int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int dx[8] = {1,1,1,0,0,-1,-1,-1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
POJ2386解答例

//
//  Author : tokoharu
#include
#include
#include
#include
using namespace std;

const int maxSize = 105;

typedef pair<int,int> PII;

string field[maxSize];

int N,M;

int dfs() {
          //usedを管理して既に訪れたところに訪れないようにします。
	bool used[maxSize][maxSize];
	for(int a=0; a<N; a++) for(int b=0; b<M; b++) used[a][b] = false;
	int ret = 0;

	for(int a=0; a<N; a++) for(int b=0; b<M ;b++) if(!used[a][b] && field[a][b]=='W'){
		ret++;
		//ここからdfsのひな形
		stack<PII >sta;
		PII init = make_pair(a,b);
		sta.push(init);
		while(!sta.empty()) {
			PII k = sta.top(); sta.pop();//一番上を取出して一番上を消す。
　　　　　　　　　　　　　　 //まわりの8マスを探索
			for(int i=-1; i<=1; i++) for(int j=-1; j<=1; j++) if(!(i==0 && j==0))  {
				int x = k.first+i;
				int y = k.second+j;
				if(x>=0 && x<N && y>=0 && y<M) if(!used[x][y] && field[x][y]=='W') {
                                                //各種更新
					PII next = make_pair(x,y);
					used[x][y] = true , sta.push(next);
				}
			}
		}
	}
	return ret;
}



int main() {
	cin>>N>>M;
	for(int a=0; a<N; a++) cin>>field[a];
	cout<<dfs()<<endl;
	return 0;

}

主要なアルゴリズム

の前に参考ページ。

  • 以下に無料で閲覧できる参考ページ（英語）があります。無料で閲覧できるページの中では最高レベルで内容が充実しています。
    Algorithms Course Materials
  • 初心者向けではないですが様々なアルゴリズムをC++の実装とともに書いているページがあります。
    SpaghettiSource
  • TopCoder内にもいくらかtutorialがあります。
    Algorithm Tutorials

O記法(アルゴリズムを考えるための前準備)

概要

(厳密な説明は省きます、詳しく知りたい人は調べてください)

アルゴリズムは「計算の手順」をまとめたものですが、同じ事を実現するのにも、複数のアルゴリズムが存在する場合があります。ここで各アルゴリズムが、他のアルゴリズムと比べて、どの程度速いか遅いか、どの程度のメモリを食うのかを、おおまかにを測ることができるとより便利です。そこで、入力の個数に対して、速度や使用されるメモリがどの程度かかるのかを比で考えた、O記法というものが考えられ、これは「ランダウの記号」などと呼ばれています。

例えば、時間計算量でいけば、n個の入力に対して、入力の大きさに左右されない操作をn回こなすのならO(n)、入力に対して2乗回の操作をこなさなければいけないのならそのアルゴリズムはO(n^2)、log n回の操作をこなさなければいけないのならO(log n)、などと表わされます。

…ぐらいの認識で競技プログラミングをする上では概ね問題ない筈、です。

このO記法はアルゴリズムを実行するときにかかる時間や必要なメモリ(空間ともいいます)の分析に用います。時間についてあらわすときには「時間計算量はO(n^2)」、「空間計算量はO(n)」などといった呼び方をします。

補足

  • 足し算ができる。例えばO(n)+O(m) = O(n+m)とできる。
  • 掛け算ができる。例えばO(n)*O(m) = O(nm)とできる。
  • 実際にあるアルゴリズムの解析をするときに出てきた結果3nとなったのでO(3n)と書きたくなります。これは実際に正しいですが、O(n) = O(3n) のようにO-記法では定数はいくらにしても変わらないルールがあります。これによって解析の時には最も簡単なO(n)と書くことができます。(「ルール」と書きましたが、定義を正しく見ればわかります。)
  • O(n^2+n)と書きたくなることもあるでしょう。しかし、nの部分はnが大きくなるとほとんど影響がなくなってしまいます。もしnが0付近なら影響がかなり大きいですが、実際にはもっと大きな数を扱います。そのときにはnの大きさはn^2に比べて大変小さくなってしまい、無視することができます。よって、O(n^2)のようにすっきりとした形にすることができます。
  • 「時間計算量O(1)」は、どんな入力でもかかる時間が変わらない、というものです。

例題

ソート(sort)

数列があることを考え、これを小さいもの順にならべることを昇順にソートする、大きいもの順にならべることを降順にソートするといいます。単に"ソートする"の言い回しだけだった時には小さいものから順に並べる昇順だと考えてよいでしょう。

単純なswap処理でO(n^2)

バブルソート:
簡単に組めるソートです。
array[i]とarray[i+1]との比較・入れ替えをi=0からn-1まで行い、これをn回行えばソートされていることが保証されます。

実装例
#include
#include
using namespace std;
int main(){
	int n , array[10];
	cin>>n;
	for(int i=0; i<n; i++) cin>>array[i];
	for(int i=0; i<n; i++) for(int j=0; j<n-1; j++) if(array[j]>array[j+1]) {
		swap(array[j],array[j+1]);
		//swapで中の値を交換できます。中では
		//int tmp=array[j] ; array[j]=array[j+1] ; array[j+1] = tmp;
		//を行っています。
	}
	for(int i=0; i<n; i++) cout<<array[i]<<endl;
	return 0;
}

高速な処理でO(nlogn)

競技プログラミングで難しい問題になってくるとO(nlogn)の時間でソートをしなければ間に合わなくなってしまうような問題が多く出現します。時間計算量O(nlogn)で実行するアルゴリズムにはクイックソートとヒープソートの二種類がよく知られています。

単純にクイックソートを実装し、特にピボットの選び方を決め打ちしておくと、時間計算量がO(n^2)となるような入力を作れてしまいます。なので、例えばピボットをランダムに選択することによってO(n^2)となる確率をかなり減らし、よい性能を保つことができます。

おまけ

  • 低速ソートというものが存在する。
  • ボゴソートやボゾソートといったソートがこれにあたる。

ライブラリ(C++)

これだけをみるとソートだけでも大変だとなってしまうが、例えばC++ではSTLで簡単に実装することができる。
vectorに数列が保存されていればalgorithmをincludeすればsort(array.begin(),array.end());のようにかけば昇順ソートができる。

実装例
#include
#include
#include
#include
using namespace std;
int main(){
	int n ;
	vector<int>input;
	cin>>n;
	for(int i=0; i<n; i++) {
		int p;
		cin>>p;
		input.push_back(p);
	}
	sort(input.begin(),input.end());
	for(int i=0; i<n; i++) cout<<input[i]<<endl;
	return 0;
}

二分探索 (binary search)

前処理としてソートを行うことによって、ある数字nが存在するか、何番目の位置にあるか、の処理を高速に行うことができるようなアルゴリズムのこと。

ライブラリ(C++)

binary_search
upper_bound
lower_bound

ライブラリ(Java)

Arrays.binarySearch (java.util.Arrays)

貪欲法(greedy algorithm)

関連リンク
Greedy Algorithms
AlgorithmsCourseMaterialsのページの一つ。

区間グラフの最大独立集合

終了時刻でソートして先頭から貪欲にとっていけばok。

最小全域木(クラスカル法)

長さの短い辺から順番にチェックし、その辺を使って連結成分を貪欲につなげていく。

動的計画法

DynamicProgramming(DP)とも呼ばれる。再帰的な構造を持つ問題に適用し、その問題を効率的に解くもの。

動的計画法を用いる有名なものとしては以下のものがあげられる。
・ナップザック問題
・最長共通部分列問題(LCS/LongestCommonSubsequence)
・最長増加部分列問題(LIS/LongestIncreaseSubsequence)
・巡回セールスマン問題(TSP/TravellingSalesmanProblem)

関連リンク
DPの話 DPの話(追記)
両記事ともtayama氏による記事(AdventCalendar2011)

グラフ

ここでのグラフとは、円グラフなどのグラフではなく、頂点とそれを結ぶ辺を持つ構造のものです。この構造のもとでできる様々な問題を解くアルゴリズムを見ていきます。
グラフそのものに関して定義などをさらに詳しく知りたければ、
グラフ理論(Wikipedia)
グラフ理論(北海道大学の講義ノート)
などを見るとよいでしょう。グラフ理論やGraphTheoryで検索すればこれに関する内容を見つけることができます。

 

日本語のグラフの解説を見るときには少々厄介なことがあります。それは解説によって同じ概念に対応する用語が異なってしまっていることがあります。慣れればそこまで困りませんが最初のうちは混乱することもあるでしょう。
以下によくある同じ名前の用語をまとめておきます。

頂点ノードnode
辺エッジedge
路/道パスpath
木ツリーtree
全域木/全点木spanning tree

基礎的な用語

最低限必要となる用語をここに書いていきます。

有向グラフ
辺が向きを持つもの。つまり、「頂点1から頂点3へ張る辺」と「頂点3と頂点1へ張る辺」とを区別したいときにこのようなものを使います。
無向グラフ
辺が向きを持たないもの。
路/道(path)
辺(u,v)を、頂点uと頂点vの間に張られている辺であるとします。
このとき路とは、
頂点v1 -> 辺(v1,v2) -> 頂点v2 -> 辺(v2,v3) ->頂点v3 ->...-> 頂点vn　
となっているようなもののことを言います。
閉路
路の説明の中でv1=vn、つまり頂点v1と頂点vnが一致しているもののことを言います。
連結
グラフGの中の任意の頂点u,vに対して、v1=u , vn=v とできる路が存在するとき、グラフGは連結であるといいます。要するに、すべての頂点がつながっていたら連結と呼びます。
木
閉路を持たない連結グラフのこと。
頂点がn個あれば、辺の数はn-1個になります。
部分グラフ
グラフHがグラフGの部分グラフであるとは、GとHの頂点集合が同じで、Hの辺集合がGの辺集合の部分集合になっているもののことを言います。
全域木
木TがグラフGの全域木であるとは、木TがグラフGの部分グラフであるような木であることを言います。
つまり部分グラフと木の定義から、グラフGのすべての頂点を行き来できるような木であることがわかります。

最短路問題

「辺にあるコストを持った有向グラフと特別な2つの頂点s,tが与えられるとする。このとき、sからtに辺と点を伝ってたどり着くときに、通った辺のコストの総和を最小化するような路(path)を求めたい。どのようにすれば求めることができるか。」
これが最短路問題です。
具体的には、「スタート地点とゴール地点、それから地図が与えられるので、スタート地点からゴール地点までの最短ルートを求め方を求める。」といった状況を考えるとわかりやすいでしょう

 

ただし、注意点がいくつかあります。

  1. 有向グラフですから、行き帰りで異なるコスト(時間)がかかるような問題(飛行機を思い出しますね)でも解くことができることも頭の隅に留めておくようにしましょう。また、有向グラフだからといって、無向グラフで解けないわけではありません。u->vのコストとv->uのコストを同じ値にするだけで変換できます。
  2. コストは負でないとは限らないことに注意しましょう。先ほどの具体例ではありえないことですが、問題によっては負のコストを持つ最短路問題を解かなければならないこともあります。
  3. 解をもたないパターンが複数あります。
    まず一つ目は始点sから終点tまでたどり着けないというものです。
    二つ目は始点sから終点tまでの解で、ある解をとってもそれよりさらに小さいコストの解が存在し、無限に小さくなってしまうようなものです。このような状況は負閉路(閉路の辺のコストの総和が負の数となるもの)を持つグラフに出現します。
  • 単一始点最短路問題
    Dijkstra法 , Bellman-Ford法が実行可能である、ひとつの始点からすべての終点への最短路問題を、単一始点最短路問題と呼びます。
  • Dijkstra法
    ダイクストラ法(deq notes)の内容がすでに詳しいです。
    要点だけまとめます。
    1.すべての辺のコストが0以上の時にのみ適用ができるアルゴリズムです。
    2.時間計算量は、priority_queueを使用することによってO(E log(V))で求めることができる。(ただし、Eを辺の数、Vを頂点の数とする。)
    3.始点sを決めると、他のすべての頂点への経路も同時に求めることができます。つまり、複数の終点tに考えたいときにも再計算の必要はなく、1回の前計算をすればよいということになります。
  • Bellman-Ford法
    ベルマン-フォード法(Wikipedia)　にすでに記事があります。
    ここでも要点をまとめておくと、
    1.コストが負数のものが存在するときにも適切な答えを返す。また、負閉路の存在を確認できるので、このことによる解の存在性についても確認することができます。
    2.時間計算量はO(EV)です。つまりDijkstra法のほうが高速です。
    3.Dijkstra法と同様に、事前に1回アルゴリズムを走らせることによって、一つの始点に対して複数の終点を求めなければいけない場合にも対処することができるようになります。
  • 全点間最短路問題
    任意の頂点対(u,v)の最短路を求める問題です。
  • Warshall-Floyd法
    ワーシャル-フロイド法
    ここでも要点をまとめます。
    1.時間計算量はO(V^3)です。
    2.実装がとても簡単(重要な処理は1行で終えれてしまう)
    3.解が存在しない場合の解なしについてはdist[u][v]が初期値のままかどうかで判定ができる。
    4.頂点i->別のところ->頂点iの最短路(つまり自頂点を含む閉路)はdist[i][i]に保存されている。
     
    特に2は競技プログラミング的には重要な意味があります。それは、効率的解法が知られているような問題に対して、そういった実装が面倒なときにこのWarshall-Floydを用いることによってショートカットすることができる場合があることです。例えば無向グラフが連結かどうかを確認したければ、頂点対(u,v)に対して辺が張られていればdist[u][v]=0として実行をします。こうすることによって、最終的にdist[u][v]=0であれば、uからvへ到達可能であることがわかるので、連結性を調べることができます。
発展的内容
  • 俯瞰的立場から
    最短路問題の一部は最小費用流問題の部分問題とみることができます。(流量1で、各辺の容量は1)
    また、この最小費用流問題は線形計画問題の部分問題となっています。

最小全域木問題(Minimum Spanning Tree Problem)

一部では最小全点木問題ともよばれています。
辺にコストがあるようなグラフを考え、そのグラフの全域木の中で最小コストとなるような木を求める問題です。

  • Kruskal法
  • Prim法

最大流問題/最小費用流問題 (Maximum Flow / Minimum Cost Flow Problem)

  • Ford-Fullkerson
  • Dinic

DFS木

文字列処理

  • LCS
  • KMP
  • Z algorithm
  • SuffixArray
  • Trie木,Aho Corasick法
  • 最長回文アルゴリズム