2002/Contest/世界大会

Problem H : A Spy in the Metro †

問題概要 †

一本道・複線の鉄道で、できるだけ駅で立ち止まらずに、目的の駅に目的の時間にいるようにしたい。このとき、駅で立ち止まることになる最短の時間を求める。

解法 †

動的計画法。

time 分時点で station 駅にいれば standing time 分の待ち時間で目的地にたどり着ける、ことを表す表 :

table[time][station] = standing time

を用意し、 time = T から時間をさかのぼって表を埋めていく。 (三廻部; Mar 21, 2004)

議論 †

• 純粋な思考三十分、コーディング一時間半程度だったか...?
  時間はかかったものの、動的計画を一から構築できたのには一応満足。 (三廻部; Mar 21, 2004)

ファイルを添付する †

mikurube_h.c