|
2007年12月21日
情報オリンピック日本委員会
|
船舶が次々と運行を開始していく状況の中で,指定された二点間の現在の最小運賃を計算する問題である.
現在までの二点間の最小運賃を格納した二次元配列(例えば,二次元配列 fares は,fares[a][b] の中に,島 a から島 b へ向かうときの最小運賃を表す値を格納する)を用いて, 新たに運航を開始した船舶の運航情報を受け取るごとにこの二次元配列を更新し, 客からの注文票にはこの二次元配列を参照し最小運賃を出力する.
二次元配列の初期化
入力を読み込む前に,船舶が一隻も運航していないときの状態を表した現在までの二点間の最小運賃を表す二次元配列を生成する.
二次元配列の添え字が i == i のときは,同じ島であるので一隻も船舶に乗らずに島 i から島 i へ移動できるため 0 を格納する.
その他のときは,船舶は一隻も運行を開始していないので,別の島に移動することができないため,移動できないことを表した十分に大きな値を格納する.
この十分に大きな値とは,(運賃の最大値×島数)よりも十分に大きく,
3倍してもオーバーフローしない程度に小さい値とする.十分に大きな値にこのような上限を設けるのは,以下で述べる現在までの二点間の最小運賃を格納した二次元配列を更新する際に,オーバーフローを起こさないようにするためである.
また,もしこの十分に大きな値が最小運賃となった場合,
島 a から島 b へ向かう航路が存在しないものとし,出力するときは -1 を出力する.
各入力に対する処理
新たに運航を開始した船舶の運航情報の場合
新たに運航を開始した船舶の運賃が,その船舶が運航する島 a と島 b を結ぶ航路の最小運賃(現在までの二点間の最小運賃を格納した二次元配列に格納されている値)と比較して,以下のように,高い場合,等しい場合,安い場合に場合分けをして考えると,安い場合のみ現在までの二点間の最小運賃を格納した二次元配列を更新すれば良いことが分かる.
客からの注文票の場合
現在までの二点間の最小運賃を格納している二次元配列を参照し,出力する.
二次元配列に格納されている島 a から島 b への最小運賃の値が十分に大きな数であった場合,島 a から島 b に移動する航路が存在していないことを表しているため,-1 を出力する.それ以外の場合は,この二次元配列に格納されている値を出力する.
よって,出力に要する計算量は O(1) である.
以上から,全体の計算量は,船舶の運航開始情報の数をkとおくと,O(kn2) である.
別解法
各島を頂点,船舶を辺,船舶の運賃を辺の重みとした重み付き無向グラフを構築すると,重み付きグラフに対する最短経路を求めるアルゴリズムを使うことによって,この問題を解くことができる.
最短経路を求めるアルゴリズムには,DijkstraのアルゴリズムやFroid-Worshalのアルゴリズムなどがある.
Dijkstraのアルゴリズムの場合の計算量は,新たに運航を開始した船舶の運航情報の場合は一件あたり O(1) であり,客からの注文票の場合は一件あたり O((k + n) log n) である.よって,全体の計算量は,客からの注文票の数をmとおくと,O(m (k + n) log n) である.
Froid-Worshalのアルゴリズムの場合の計算量は,船舶の運行情報一件あたりの計算量は O(n3) であり,客からの注文票で最小運賃を計算する場合は O(1) である.よって,全体の計算量は,O(kn3) である.
入力データの大きさから三つの解法の中でもっとも時間のかかるFroid-Worshalのアルゴリズムを用いた場合であっても,各入力に対し高々10秒程度プログラムを実行すれば解ける.