どこで会える ?
寺田 実（電気通信大学情報通信工学科）����������������������������

����

�����

東京に住んでいて，最も安く会うためのプランを考え�����

若くて，お金がなくて，しかも忙しい 2 人が函館と東京

��

www.fun.ac.jp/icpc/ から入手可能）．

��

問 題 の F, "Young, Poor and Busy'' で あ る（http://�����盛岡��

未 来 大 学で 行 われた，アジア 地区予選函館大 会の��

今 回 取 り 上 げ る の は，2001 年 11 月 に は こ だ て�����

函館

�����

■問題

�����
�����

terada@ice.uec.ac.jp

図 -1 ダイヤグラムによる表現るのが目標である．
入力データとして，駅を結ぶ列車の時刻表が与えられる．列車は始発駅と終着駅とを直接結んでおり，途中に停車駅はない．料金は列車ごとに決まっている．
それらの列車を利用して，函館駅からは Ken が，東京駅からは Keiko がそれぞれ出発し，どこかの駅で落ち合い，またそれぞれの出発地に戻る（落ち合う駅

Morioka 15:30 Hakodate 18:00 3000
Morioka 14:30 Tokyo 17:50 3000
Tokyo 08:30 Morioka 13:35 3000

は函館や東京でもよい）．
制約事項は，列車は 5 本ある．同じ情報をダイヤグラムとして表• 出発は午前 8 時以降，現したものが図 -1 である．縦軸に路線の距離，横軸• 帰着は午後 6 時以前，に時刻をとり，列車は斜めの線として表される（通常• 30 分以上会っていられること，の列車ダイヤには料金は書いてないが，ここでは線にであり，問題として要求されているのはその条件を満沿った斜めの数字として料金を示す．また，起点の駅たす最も安いプランの総費用である．もし制約条件をを上にするのが普通だが，コンテストの開催地に敬意満たす解が存在しない場合には 0 を結果とすることを表して函館を起点としよう）．になっている．

この例では，明らかに函館や東京で会うことはでき

入力データはデータの組の並びであり , ひと組のデない．そこで，唯一の可能性である盛岡を考えると，ータは，列車の総数を表す行と，そのあとに各列車の東京からの往復は 1 通りに定まるが，函館からは帰り発駅，発時刻，着駅，着時刻，料金を示す行が続く．の列車の選び方が 2 通りあり，そのいずれでも 2 人はデータ全体の終了は 0 だけからなる行で表す．

30 分以上一緒にいられるので制約条件を満たす．総問題文に含まれている入力データの組の具体例を見よう．

2500 ＋ 2500 ＋ 3000 ＋ 3000 ＝ 11000 円 で あるのに5Hakodate 08:15 Morioka 12:30 2500
Morioka 14:05 Hakodate 17:30 2500

192

44巻2号

費用は，早い列車（14:05 発）で函館に帰る場合には情報処理

2003年2月

対して，遅い方の列車（15:30 発）では 500 円だけ高くなってしまうので，結局求める総費用は 11000 円ということになる．

なお，規模に関する条件としては，�������となっている．

��■考え方����• 列車の数の上限は 2000��• 駅の数の上限は 100��

この問題を解くための中心となる値は，たとえば函館を午前 8 時以降に出発して盛岡に向かう����� ���� ��として，ある時刻に到着するためにはいくら払��

図 -2 時刻の離散化う必要があるかである（その時刻までに到着する列車がない場合には無限大の費用がかかるとする）．この値の変化を，到着時刻を変数とみて考えると，値に変化があるのはその駅に列車が到着したときに限られ，また，その変化

���

���

�� ���� � � � �����

�������� ��

は減少だけに限られる．なぜなら，仮にその列車でのとなる．t の上限の 17:30 は，目的地での 30 分以上の到着がそれまでよりも費用がかかるものであったとし滞在を考えに入れてのことである．

たら，その列車を利用しなければよいだけの話だからである．つまり，この値は時刻変化に対して単調減少■ fr_h を求めるの階段状関数となる．上記の例でいえば，08:00 から12:29 までは無限大であるが，12:30 以降は 2500 円である．

以 下 で， 前 章 で 用 い た 4 つ の 値 の 代 表 と し て，fr_h(st, t) の求め方を考える．

この値を fr_h(st, t) と書くことにしよう．h は函館

まず，時刻 t を離散化する．函館からある駅までの起点を表し，st は目的の駅（ここでは盛岡），t は到着到達費用に変化が生じるのは，その駅にどこかから列時刻である．もちろん函館の代わりに東京を起点とす車が着いたときだけである．そこで，すべての列車をる同様の値 fr_h(st, t) もある .

到着時刻順に並べて，T0, T1, ..., Tnt1 とする．ここで，また，それとは逆にnt は列車の総数を表す．列車 Ti の発駅を FRi, 発車時

盛岡を出発して函館に午後 6 時までに帰着す

刻を Di, 着駅を TOi, 到着時刻を Ai, 料金を FAREi, とするとして，ある時刻まで盛岡にいるためにはいる．また，8:00 を A1 とする（図 -2）．これで，時刻くら払う必要があるかt のかわりに，列車到着事象の番号（つまり Ai の添字という値も定義できる．こちらは出発時刻に対して単i）を用いることができる．それによって，値 fr_h(st, t)調増加の階段状関数である．上記の例では，08:00 かは離散的な添字を持つ 2 次元の配列とすることがでら 14:05 までは 2500 円，15:30 までは 3000 円，それき，これを順に埋めていくことが可能になる．

以降は無限大となる．こちらは to_h(st, t), to_t(st, t) としよう．の時点では列車がどこかに着いていることは不可能

これが求まったとすると，駅 st において 2 人が時
刻 t から 30 分会うための総費用 cost(st, t) は，cost(st,t) 

まず，8:00 における値 fr_h(st, 1) を考えよう．こ

fr_h(st, t)
fr_t(st, t)

であるから，函館を除くすべての駅で無限大の値をとり，函館についてはすでにそこにいるのだから 0 円である．
次に，時刻を 1 つ進めて A0 を考える．これは列to_h(st, t30)

車 T0 が駅 FR0 から駅 TO0 に到着した時刻である．前

to_t(st, t30)出のデータ例でいえば，函館 8:15 発の列車が盛岡にとなる．最終結果はこれをすべての駅と時刻で計算し12:30 に到着した時点である．このとき，fr_h（盛岡 ,た最小値であるから，t) は無限大から 2500 円へと変化する．その他の駅については変化はない．
IPSJ Magazine Vol.44 No.2 Feb. 2003

193������������������������������

��

図 -3 change(i) の決定

図 -4

fr_h の再帰的定義

これを一般的にいえば，fr_h(st, i) は，i

時刻

函館

東京盛岡

• Ti の着駅 TOi が st でなければ，fr_h(st, i1) から変

1

8:00

0∞

∞

化なし

012:30

0∞

2500

1

13:35

0∞

2500

− fr_h(st, i1)

2

17:30

0∞

2500

− FAREi  fr_h(FRi, change(i))

3

17:50

05500

2500

418:00

05500

2500

• TOi が st と一致していれば，以下の小さい方の値

ここで change(i) は，列車 Ti に乗り継げる最も近い列車の着時刻 Aj の添字 j である（図 -3 左）（言い替えると，Di 以前の最も近くに FRi に到着す

東京を起点とした fr_t についてもまったく同様に求めることができる．

る列車の着時刻）．もし，そのような列車がない場合には，1 とする．

■ fr_h の再帰的定義として，順次求めていくことができる．
ここで，change(i) の定義について補足．いまの説

前章のように表を順次埋めていくのは，この問題に

明では，「乗り継ぎ」を条件として，駅 FRi への列車のついてはごく自然な発想であると思う（筆者はこの方到着時刻としたが，実は必ずしも駅 FRi への到着であ式を先に思いついた）．しかし，表を順次埋めるといる必要はなく，Di 以前の着時刻であればどこの駅へうのは動的計画法の典型的なパターンであり，その元の到着でもよい（図 -3 右）．この違いは，本章のようになる再帰的な定義が存在するはずで，それは前章のに表を順次埋めていくアプローチでは実行効率に何の漸化式から簡単に求めることができる（図 -4) ．人に違いもないが，次章で述べる再帰的な方法では，FRi

よっては先にこちらの再帰的定義を思いつき，それにへの到着まで再帰的に遡る必要が生じ，呼出の深さの動的計画法を適用する，という手順を踏むかもしれな点で大きな負担となる（図 -4 の 3 行目の再帰呼出）．

いが．

データ例について fr_h を求めると，以下のようになる．

いずれにせよ，実行効率を考えると，再帰的定義をそのまま計算するのは列車数の指数オーダになる可能性があり，現実的な方法ではない．問題文中に示して

194

44巻2号

情報処理

2003年2月

ある例（駅数 4 ，列車数 18）程度では解けても，審判団のテストデータ（これも Web ページで公開されて■データ構造いる）には駅数 25 ，列車数 1123 のものがあり，これはまったく望みがない．

まず，駅を表現する方法である．入力データでは駅は文字列として登場するが，これは整数値に変換する■ to_h を求めるのが定石である．そのためには駅名を表に登録する処理が必要であるが，これは省略．データを読み込む前次に，函館に帰着する方を考えよう．本質的には函館を起点とする fr_h と同様であるが，逆の処理が必に函館と東京を登録してしまうことによって，これらに 0 と 1 の番号をあらかじめ割り当てている .

要となる．まず，時刻は発車時刻を用いて離散化し，次に，列車の表現である．前述の通り列車は複数の列車は発車時刻順に並べておく必要がある．18:00 の値の組になるので，構造体を使うのがよいだろう（フ時点から時刻を遡るかたちで表を埋めていく．これをィールドごとに別の配列とする方法もあり，これもなその通りプログラムとするのに別に困難はないが，ほかなかシンプルでよいのだが，今回は列車データ全体

とんど同形であるにもかかわらず共用できないコードを着時刻をキーとしてソートする必要があるため，メが 2 組できる結果になってしまう．

モリ上でもまとまっていた方が扱いやすい）．

ここで，本連載の執筆者の 1 人の石畑氏に教示して列車の本数は変数 nconn で保持する．これはプロいただいた非常にうまい方法がある．
これを用いれば，グラムの入力データとして与えられた列車データ総数

to_h は fr_h と同じコードで求めることができるのでから，8:00 以前に発車する列車や 18:00 以降に到着すある .

る列車を除いた数とする．列車データはオリジナルの基本的なアイディアは「フィルムの逆回し」である．
午後 6 時から時間軸を逆転して見てみると，最後に到もの (trains[]) のほかに，前章で述べた「時間軸反転」データも rtrains[] として保持する .

着した列車が最初に発車する列車となり，もともとはまた，fr_h(st, t) なども 2 次元の整数配列として実始発駅だった駅に向かって進行する．ダイヤグラムで装する．ただし，第 2 の添字（離散化した時刻）に 1

説明すれば，時間軸を左右逆転することに相当する．

が現れるので，実装では 1 だけずらすことにした．

こうすると，盛岡をできるだけ遅く出発して函館に 18:00 までに到着するというプランが，#define MAXCITY 100/* 駅名の表 */char city_name[MAXCITY][18];int ncity;/* 駅数 */

函館を 18:00 に出発して，できるだけ早く盛岡に到着するとなり，これはまさに to_h を fr_h に変換していることになる．
この変換をプログラム上で実現するには，列車のデータに対して• 始発駅 FRi と終点 TOi の交換• 発時刻 Di と着時刻 Ai の時間軸反転と交換の処理が必要である．ここで，時間軸反転とは，元の時刻 t を t にするだけでよい（実際には，デバッグの都合を考えると適当なバイアスを加えて正数にしたほうが都合がよいだろう）．
以上でアルゴリズムの設計は完了し，以下でコードを示そう．

#define MAXCONN 2000+1/* 列車の情報 */struct train {int from, to; /* 駅番号 */int dpt, arv; /* 0:00 からの分単位 */int fare;/* 料金 */} trains[MAXCONN], rtrains[MAXCONN];
int nconn;/* 列車数 *//* 重要な駅番号 2 つ */#define HAKODATE 0#define TOKYO 1#define INFINITE 99999999
int from_hakodate[MAXCITY][MAXCONN],IPSJ Magazine Vol.44 No.2 Feb. 2003

195

from_tokyo[MAXCITY][MAXCONN],
to_hakodate[MAXCITY][MAXCONN],
to_tokyo[MAXCITY][MAXCONN];p--;}return p;}#define BIAS ((18-8)*60)■列車データの準備
列車データを読み込んだ後（プログラムは省略），「時間軸反転」データを作り，オリジナルデータとそれをvoid make_table(int v[MAXCITY][MAXCONN],
int org,
struct train tv[]){
int ti;
int i;
int a;

到着時間順にソートする．ソーティングには，C の標

for(i = 0; i < ncity; i++)

準ライブラリ関数 qsort を使っている．第 3 引数とv[i][0] = INFINITE;
v[org][0] = 0;

して，要素の大小を判定する関数を渡す．
int cmp_arv(struct train *t1,struct train *t2)({ return t1->arv - t2->arv); }for(ti=0; ti<nconn; ti++){for(i = 0; i < ncity; i++){v[i][ti+1] = v[i][ti];}a = change(tv, ti-1, tv[ti].from,tv[ti].dpt);[[]][v tv ti .to ti+1] =min(v[tv[ti].to][ti],tv[ti].farevoid prepare_data(void){
int i;
for(i=0; i<nconn; i++){rtrains[i].from = trains[i].to;
rtrains[i].to = trains[i].from;rtrains[i].dpt = BIAS-trains[i].arv;
rtrains[i].arv = BIAS-trains[i].dpt;
rtrains[i].fare = trains[i].fare;}qsort(trains, nconn,sizeof(struct train), cmp_arv);
qsort(rtrains, nconn,sizeof(struct train), cmp_arv);+ v[tv[ti].from][a+1]);}}■解を求める
作成した表をもとに，解を求める処理である．関数calc_cost はまず駅を固定し，（列車到着で離散化した）時刻ごとに，30 分以上滞在する場合の費用の最小値を求める．それには，その駅への到着時刻を表す}

a と，発車時刻を表す d を，30 分以上で最短の間隔■表の作成を開けながら並行して動かしていく．関数 solve は，それをすべての駅に対して行うことで全体の最小値を動的計画法を利用して，fr_h(st, t) をはじめとする4 つの表を埋める処理である．関数 make_table は，埋めるべき表，起点／終点，列車の時刻データを引数として受け取る．
int change(struct train tv[], int p,int st, int dpttime){
while(p >= 0){if((tv[p].to == st) &&(tv[p].arv <= dpttime)) break;

196

44巻2号

情報処理

2003年2月

求めている．
int calc_cost(int city){
int a=0, d=nconn-1;
int stay;
int c, min_c=INFINITE;
while(1){stay = (BIAS - rtrains[d].arv)- trains[a].arv;(if stay < 30){

make_table(to_tokyo, TOKYO, rtrains);d --;if(d < 0) break;continue;

min_cost = INFINITE;
for(c = 0; c<ncity; c++){cost = calc_cost(c);if(cost < min_cost)
min_cost = cost;}}c = from_hakodate[city][a+1] +from_tokyo[city][a+1] +to_hakodate[city][d+1] +to_tokyo[city][d+1];
if(c < min_c)min_c = c;a ++;if(a >= nconn) break;}return min_c;}

if(min_cost >= INFINITE)
min_cost = 0;
return min_cost;}必要となる計算の手間は，表の作成，解を求める処

int solve(void){
int c, a_i;
int cost, min_cost;prepare_data();

理とも，（駅の数）×（列車の数）であり，問題の規模の制約のもとで，十分実行可能である．
ただ，このプログラムは単純化のために，不必要な計算を行っているのも事実である．具体的には，
fr_h(st, t) の表をすべての（離散化）到着時刻に対して構成している点が問題で，本当に必要なのはその駅に

make_table(from_hakodate, HAKODATE,trains);
make_table(from_tokyo, TOKYO, trains);
make_table(to_hakodate, HAKODATE,到着する時刻においてだけである．そうするなら表のサイズは，全体として列車の数でおさえられ，全体の処理時間も列車数でおさえられる．
（平成 15 年 1 月 8 日受付）

rtrains);

IPSJ Magazine Vol.44 No.2 Feb. 2003

197