課題３
課題３
2010年 ICPC 2010年アジア予選 東京大会からの出題です。問題Bについて考えてみましょう。いつものように入出力までは済ませてあります。
- balloon.c
- sample: sample.in, sample.ans
- 検証データ： B.in, B.ans
問題の題意をまとめるとこんな感じです。
- 上から落ちてくる風船をロボットで集める
- 与えられるもの：各風船が落ちる場所と時刻
- ロボットには風船を３個まで載せられる
- 風船は左端の家で回収
- 風船を k 個載せると、移動時間は k+1 倍 (座標を１移動するのに、k+1時間かかる,
追記) - 風船は落ちてくる順に、その場所と時刻が与えられる
追記
- 質問
- 風船をすべて回収できる場合は、最小移動距離を答える
- 回収できない場合は、何個目で回収不能かを答える
入力例(//以降はコメント, 追記)
3 // 風船は３個落ちてくる
100 150 // 場所 100 に時刻 150 に落ちてくる
10 360 // 場所 10 に時刻 360 に落ちてくる
40 450 // 場所 40 に時刻 450 に落ちてくる
3
100 150
10 360
40 440
2
100 100
50 110
0
出力
OK 260
OK 280
NG 2
DP 的アイデア
問題の解き方は一通りではありません。でも、DP 的に考えるのが簡単かと。 以下のように状態をとらえることができますよね？
- f(k, b): k 番目の風船をキャッチして風船 b 個になるまでの最小移動距離（or 到達不能か）
プログラム解説
入力データは構造体balloon_tの配列として記述しています。
- 構造体 struct balloon (= balloon_t): 時刻
timeと 位置posを持つ (追記) - 大域変数：
balloon_t balloons[MAX_BALLOONS];
皆さんが実装するのは、以下の関数
- result_t solve(int n): n はバルーンの数。返り値 result_t は、
isOKとnumを持つ構造体です。isOKには、最後までバルーンを回収できる場合は1を、回収できない場合は0を入れましょう。numには、回収できる場合は最小移動距離を、回収できない場合は回収できなくなる最初の風船の番号をいれましょう。
課題提出
課題は、11月中の提出を推奨します。12/6 には持ち越さないようにしましょう。 正解プログラム例は、皆さんの 11/8 か 11/15 に公開予定です。
- 自作プログラム
- 自作プログラムが正解に辿りつかなかった場合は、指定日（現在未定）公開の正解プログラム例と比較して、自分のプログラムが間違っていた箇所を、正解プログラムがどのように実現していたか解説すること。
- 自作プログラムもしくは正解プログラム例の解法について簡単に解説し、その時間計算量を、バルーンの数
n（今回はnは40以下）および、位置の取りうる値の幅P(今回は 100 以下), バルーンの落ちてくる時間の幅T(今回は50000以下)を用いて表せ。