Day 2 Task 4: 保存せよ (Saveit)

ゼデフ (Xedef) 宅配便社はいくつかの都市 (city) の間で荷物を空輸するサービスを提供している.これらの都市の中には荷物の処理のための特別な設備が設けられている都市もあり,ゼデフの ハブ (hub) と呼ばれる.ゼデフが所有する各航空機は 2 つの都市の間を往復しており,どちら向きにでも荷物を運ぶことができる.

荷物をある都市から別の都市に届けるには,ホップ (hop) を繰り返すことで運ぶ必要がある.ここでホップとは,航空機のどれかが運航する 2 つの都市のうち一方から他方へ荷物を運ぶことである.さらに,荷物の経路の中にはゼデフのハブを少なくとも 1 つ含む必要がある.

荷物の仕分けを容易にするため,ゼデフでは都市とハブのすべての対について最短経路の長さを荷物の出荷ラベルに符号化 (encode) して記入しておきたいと考えている. (あるハブから自分自身への最短経路の長さは 0 である.) 当然ながら,この情報をコンパクトに表現する方法が必要である.

encode(N,H,P,A,B)decode(N,H) という 2 つのプロシージャーを実装せよ. N は都市の個数であり, H はハブの個数である.都市には 0 から N-1 までの番号が振られており, 0 以上 H-1 以下の番号の都市がハブである. N ≤ 1000 であることと H ≤ 36 であることを仮定して良い. P は航空機で結ばれている都市の対の個数である.都市の対は (非順序対として) すべて相異なる. AB は配列であり, 1 番目の対は (A[0],B[0]), 2 番目の対は (A[1],B[1]) のようになっている.

encode がビット列を生成し, decode がそのビット列を使って各都市から各ハブへのホップ数を決定できるようにせよ. encodeencode_bit(b) (b は 0 または 1) を繰り返し呼び出すことで採点サーバーにビット列を送信する. decodedecode_bit を繰り返し呼び出すことで採点サーバーからこのビット列を受信する. i 回目の decode_bit の呼び出しでは, i 回目の encode_bit(b) の呼び出しにおける b の値が返される. decodedecode_bit を呼び出す回数は必ず encodeencode_bit(b) を呼び出した回数以下でなければならないことに注意せよ.

decode は,各ハブから各都市へのホップ数を復号 (decode) した後,各ハブ h と各都市 c (すべてのハブを含む.つまり c=h の場合も含む.) について hops(h,c,d) を呼び出さなければならない.ここで dhc の間で荷物を届けるのに必要な最小のホップ数である.つまり, hops(h,c,d) を N*H 回呼び出さなければならない.呼び出す順序は自由である.任意のハブと任意の都市の間で荷物を届けることができることは保証されている.

注意: encodedecode はここで指定されたインターフェースでのみ通信できる.共有変数やファイルのアクセスやネットワークのアクセスを用いてはならない. encode または decode が変数を共有することなく情報を保存しておくための永続変数 (persistent variables) を使いたい場合, C または C++ では static として宣言すればよく, Pascal では提出ファイルの implementation 部で変数を宣言すればよい.

例として右の図を考える.ここでは 5 個の都市 (N=5) が 7 機の航空機 (P=7) によって結ばれている.都市 0, 1, 2 はハブである (H=3).ハブ 0 と都市 3 の間で荷物を届けるには 1 ホップが必要であり,ハブ 2 と都市 3 の間で荷物を届けるには 2 ホップが必要である.この例に対応するデータは grader.in.1 にある.

decode は次の表の通りに d の値を指定して hops(h,c,d) を呼び出さなければならない.

d都市 c
01234
ハブ h001111
110111
211022

小課題 1 [25 点]

encodeencode_bit(b) を呼び出す回数は 16 000 000 以下でなければならない.

小課題 2 [25 点]

encodeencode_bit(b) を呼び出す回数は 360 000 以下でなければならない.

小課題 3 [25 点]

encodeencode_bit(b) を呼び出す回数は 80 000 以下でなければならない.

小課題 4 [25 点]

encodeencode_bit(b) を呼び出す回数は 70 000 以下でなければならない.

実装の詳細