第１０回日本情報オリンピック　予選５

2010年12月23日
情報オリンピック日本委員会

解説

ねずみがすべてのチーズを食べるためには，柔らかい順にチーズ工場に行かなければならない． この問題は，最短経路を N 回求めることで解くことができる．

いくつかの点 (頂点と呼ぶ) と点と点を結ぶ線 (辺と呼ぶ) からなるものをグラフという． グラフ G の頂点 u から頂点 v まで G の辺を通って行くとき，通らなければならない辺の個数の最小値を u と v の距離という． この問題では，区画を頂点とし，隣り合う区画に対応する頂点の間に辺を張り，そのグラフ上で距離を求めればよい． 以下，グラフの頂点数を V，辺数を E とする．

解法１

全点間の距離を求めるアルゴリズムとしては，Floyd Warshall 法が知られている． 頂点 u と頂点 v の距離を dist(u,v) とおく．

foreach(vertex k in G){
	foreach(vertex i in G){
		foreach(vertex j in G){
			dist(i,j) := min{dist(i,j), dist(i,k) + dist(k,j)}
		}
	}
}

このアルゴリズムの計算量は O(V^3) である． この問題で Floyd Warshall 法を用いると計算量は O(H^3W^3) となり，5 データ中 2 データを解くことができる．

解法２

ある頂点 s から他の頂点までの距離を求めるアルゴリズムとして，Bellman Ford 法が知られている． 頂点 s と頂点 v の距離を dist(v) とおく．

repeat V times:
	foreach(edge (i,j) in G){
		dist(j) := min{dist(j), dist(i) + 1}
	}

このアルゴリズムの計算量は O(VE) である． この問題で Bellman Ford 法を用いると計算量は O(NH^2W^2) となり，5 データ中 3 データを解くことができる．

解法３

キュー (queue) と呼ばれるデータ構造は，次のクエリを O(1) でできる．

• 先頭の要素を参照する
• 先頭の要素を削除する
• 末尾に要素を追加する

キューを用いると，ある頂点 s から他の頂点までの距離をより高速に求める幅優先探索 (Breadth First Search) ができる． 頂点 s と頂点 v の距離を dist(v) とおく．

q := an empty queue
add s to q
while(q is not empty){
	v := the first element of q
	remove v from q
	foreach(edge (v,i) in G){
		if(dist(v) + 1 < dist(i)){
			dist(i) := dist(v) + 1
			add i to q
		}
	}
}

このアルゴリズムの計算量は O(E) である． この問題で幅優先探索を用いると計算量は O(NHW) となり，5 データ全てを解くことができる．