Ver 1.00 2001/04/xx
すー：
ジャン：
すー：
ジャン：
すー：
ジャン：
すー：
ジャン：
すー：
ジャン：
問3 目的駅に最も早く到着する乗り方を求める問題に関する次の記述を読んで，設問1〜3に答えよ。
列車の時刻表が与えられ出発駅，時刻，目的駅（出発駅とは異なる）が指定されたとき，出発駅から指定時刻以降に列車に乗り，必要に応じて途中の駅で列車を乗り換えながら，目的駅に最も早く到着する乗り方を求める。最も早く到着する時刻を最早到着時刻と呼ぶ。
この問題で用いる時刻表の例を図1に示す。この時刻表は，列車を表す列車コード
（1，2，3，．．．の整数）及び駅を表す駅コード（1，2，3，．．．の整数）を添字とす
る発車時刻（5：00から23：50までの時分，又はNULL）の配列である。NULLでない各値は，列車が駅を発車する時刻を表している。問題を単純にするため，列車の駅への到着時刻は，その駅での発車時刻と同じとみなす。
計算結果は，駅0−列車1−駅1− 〜 −列車N−駅Nの形式で求める。ここで，駅0は出発駅，駅Nは目的駅，途中の駅は乗換駅である。
乗り換えることができるのは，到着時刻の3分後以降の時刻に同じ駅を発車する列車に限る。
最早到着時刻で目的駅へ到着する乗り方が禎数ある場合は，その内の一つを求めればよい。
なお，出発した当日中に目的駅に到着できない場合は，“不可能”・・と答える。
この問題に対して，まず次の解法を考えた。
〔解法1〕
選択可能な列車の乗り方は，図2に示すように，出発駅を根とし，（列車，駅）からなるレコードを節点とする木で表すことができる。ある節点に対応する列車と駅は，それぞれその親の節点の駅から乗る列車と降りる駅である。同じ列車で降車可能な駅が複数ある場合は，列車が同じで駅が違う別々の節点を作り，木の同じ深さの位置に置く。
時刻表を参照して，出発駅から幅優先で（すなわち深さの浅いものから順次）節点を追加しながら木を成長させていき，答えを求める方針とする。ただし，新しく追加しようとしている節点と同じ駅の節点が既に木にある場合は，到着時刻がその既にある節点の到着時刻よりも早い場合だけ追加する。このとき，その既にある節点には，以後そこから子をもたないようにするための印をつける。この処理を無効化と呼ぶ。無効化する節点が既に子孫をもっている場合には，それら子孫の節点もすべて無効化する。
追加された節点の駅が目的駅であれば，その節点を無効化するとともに，以後の節点の追加処理では，その目的駅到着時刻以降の到着時刻となる節点は追加しない。
追加できる節点がなくなるまで，この処理を繰り返す。
| 親節点ポインタ | 列車 | 駅 | 到着時刻 | 無効フラグ |
新たな節点を木に追加すべきかどうかを到着時刻に基づいて判定するために，図4に示すデータ項目からなるレコード（以下，最早到着レコードという）の1次元配列（以下，最早到着表という）を用意する。駅ごとに一つの最早到着レコードを対応させ，駅コードと同じ添字位置に置く。最早到着レコードは，木を作っていく過程の各時点で，それまでに分かっているその駅に最も早く到着する時刻と，それに対応する乗車レコードのポインタを保持している。
最早到着表は，出発駅については（指定時刻−3分，1）で，その他のすべての駅については（24：00，NULL）で初期化する。
節点を木に追加しようとするとき，その乗車レコードの到着時刻が，その駅の最早到着レコードの最早到着時刻より早いかどうか比較し，早い場合だけ追加する。同時に最早到着レコードが指している乗車レコードとその子孫の乗車レコードに対する無効化処理を行うとともに，最早到着レコードを更新する。
| 最早到着時刻 | 乗車レコードポインタ |
設問1 駅コード2の駅を出発駅，指定時刻を8：00，駅コード5の駅を目的駅とし，図1の時刻表を用い，解法1による処理を行った後の乗車表の状態を次に示す。
空白部分に値を記入し，表を完成させよ。
乗車表
| （添え字） | 親接点 ポインタ |
列車 | 駅 | 到着時刻 | 無効フラグ |
| 1 | NULL | NULL | 2 | 7:57 | 0 |
| 2 | 1 | 1 | 3 | 8:15 | 0 |
| 3 | 1 | 1 | 4 | 8:30 | 1 |
| 4 | 1 | 2 | 1 | 8:10 | 0 |
| 5 | 3 | 5 | 5 | 8:50 | 1 |
| 6 | |||||
| 7 |
設問2 解法1では，節点を一律に幅優先で追加したが，節点を追加する順番を工夫することによって処理を効率化するなど，次に示す改良を考えた。
木に節点を追加する場合には，その時点で最も早い到着時刻をもつ葉（まだ子節点が追加されていない節点）を選び，それを親として追加可能なすべての子節点を追加する。
この方法で節点を追加した場合，[ a ］の到着時刻は，その駅に到着できる最も早い時刻となっている。したがって，この節点は後から無効化が必要になることはなく，子節点を追加しないようにするための無効化処理は不要となる。
なお，子節点を追加する対象の親として[ b ］が現れた場合には，答えが確定する。
また，解法1は節点の追加に対応して乗車レコードを順次追加していく処理方式であるが，処理中の各時点において必要な乗車レコードとしては，[ c ］に対応するもの一つがあれば十分である。したがって，ある乗車レコードを追加するときに既に同じ駅のレコードがある場合は，それに上書きしても構わない。
さらに，必要なデータ項目を最早到着レコードで駅ごとにもつことによって，乗車レコードを使わない解法も考えられる。この場合，最早到着レコードが節点に対応することになる。
解法の改良に関するこれらの記述中の[ a ］ 〜 [ c ］に入れる適切な字句を，解答群の中から選べ。
解答群
ア 駅が目的駅となっている節点
イ 各駅について，それまでに分かっている中で到着時刻が最も早い節点
ウ 子節点を追加する対象の親として選ばれた節点
エ 子として追加された節点
オ 到着時刻がその駅の最早到着レコードの最早到着時刻より早い節点
設問3 上記の改良から，次の解法2を考えた。
〔解法2〕
解法1の最早到着レコードに対して，乗車レコードポインタを削除し，“最早確定フラグ”を含め三つのデータ項目を追加する。この最早確定フラグは，0で初期化し，そこに記録されている最早到着時刻がその駅に到着できる最も早い時刻となっていることが確定したときに1とする。
この拡張された最早到着表を参照し，最早確定フラグが0のレコードの中から最早到着時刻が最も早いレコードを，節点を追加するための親節点に選ぶ。最初の親は木の根に対応して出発駅の最早到着レコードとする。
その親に対するすべての子節点を追加することにし，解法1における乗車レコードの追加処理の代わりに，この拡張された最早到着表に必要なデータを書いていくことにする。親節点の最早到着レコードの最早確定フラグは1とする。
この処理を，答えが確定するか，又は追加できる節点がなくなるまで繰り返す。
設問1と同じ条件で，解法2によって処理した後の拡張された最早到着表の一部を次に示す。追加した二つの項目[ d ］，[ e ］に入れる適切な名称を，解答群の中から選べ。また，処理中に上書きされた最早到着レコードが一つだけあった。その添字（駅コード）と上書き前の最早到着時刻及び上書き後の最早到着時刻を答えよ。ただし，拡張された最早到着表は適切に初期化されたものとし，初期化された値の書換えは上書きには含めない。
ア 列車に乗った駅
イ 列車から降りた駅
ウ 乗った列車の本数
エ 乗って来た列車
オ 乗って行く列車
すー：
ジャン：
すー：
ジャン：
すー：
ジャン：
すー：
ジャン：
すー：
ジャン：
(c)斎藤末広，
2001
この資料は2001年4月13日まで，許可した方のみ閲覧可能です。もし，なんらかの手段でこの資料を読まれて，有効であると判断された場合は，ご入金をお願いします。許可無く再利用，公開を禁止します。なお，情報処理技術者試験問題(サンプル含む）はその限りではありません。