スゴ技

平成24年度秋基本情報技術者試験【問8】

Blog：IT・情報処理BLOG | 2013.01.14

ソフトⅡコース担当　ブログのおにーさまこと高橋です。

3連休も今日で最後、明日から授業です。

今回は、平成24年度秋期基本情報技術者試験午後問8の解説です。問題はIPAのサイトをご覧ください。

この問題は、Warshall-Floyd法を用いて駅間の最短距離を求めるものです。難しく感じるかもしれませんが、アルゴリズムは問題に書いてあるので、その流れと疑似言語をしっかり対応させれば問題ないと思います。

最初の問題は、副プログラムCalcDistを実行したときに配列の内容がどのように変化するか、つまりトレースするだけです。空欄はViaが2のところだけで、その前後は記載してあります。Viaが1のときの結果からどのように変化するか、実際に試してみれば簡単です。Viaを2として、問題の副プログラム、点線内を実行すると次の図のようになります。

結果は次のようになります。従って空欄aにはウ、bにはアが入ります。

副プログラムは3重ループで、それぞれがN回の繰り返しです。計算回数はN×N×N、つまりNの3乗です。空欄cにはエが入ります。また、メモリ使用量は、N×Nの2次元配列を用いるので要素数はNの2乗です。空欄dにはウが入ります。

上の図で、黄の部分と青の部分では、対称なので同じ処理（発着を逆にしても同じ）を行っています。どちらかにまとめることができます。白の部分（対角部分）は、値が0なので条件を満たすことは絶対になく、計算する必要がありません。

黄の部分で考えると、TOの値は、FROMの次の値（FROM+1）から最後の値（N）までです。
青の部分で考えると、TOの値は、1からFROMの前の値（FROM-1）までです。

eの解答群でこの範囲になっているのは、黄の部分で考えたエです。

空欄fには、問題の説明(4)にある両駅が属する区間が異なるか同じかの場合分けが入ります。問題より、

両駅が属する区間が異なる場合、4通りの値D1,D2,D3,D4の最小値です。つまり、min(D1,D2,D3,D4)です。
同じ区間にある場合、期間駅を経由せずに直接行く経路も考慮しないといけないので、min(abs(ToKL[i]-ToKL[j]),D1,D2,D3,D4)となります。

空欄fが真のときmin(abs(ToKL[i]-ToKL[j]),D1,D2,D3,D4)となっているので、条件は区間が同じかどうか、つまり、Secの値が同じかどうかです。空欄fにはウが入ります。

表1の駅情報の行数は、各駅につき1行です。問題より、表1の1行は配列Distの5要素分なので、5倍します。更にDist表はK×Kの2次元配列になるので、合わせるとメモリ量はK×K＋N×5となります。この値がN×Nより小さくなれば削減できたことになります。Kが5の場合で考えると、
N×N≧25＋5×N
N×N－5×N－25≧0
Nが2から順に計算して、最初にN×N－5×N－25が正の数になるのはNが9のときです。空欄gにはウが入ります。