資料へ

Balloon Collecting

2010年 ICPC 2010年アジア予選 東京大会からの出題です。問題Bについて考えてみましょう。

illustration

問題の説明

上から落ちて来る風船をロボットが家に集める． 風船が落ちる場所と時刻が与えられる． ロボットは左右に動ける． 運んでいる風船の数 k によって速度が変わる：具体的には座標を１移動するのに、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

問題１

入力処理は準備しています：kadai3/balloon.c mainの中で，風船をballoons配列に格納し，solve関数を呼び出し，正解との比較を行う． 残りは54行目のsolve関数を実装．

/* 風船 struct / balloon struct */
typedef struct balloon {
	int time;
	int pos;
} balloon_t;


/* 風船の配列 Balloon array */
balloon_t balloons[MAX_BALLOONS];

/*
 * balloons配列に記録されている問題を解く
 * solve the problem contained in the balloons array
 * 
 * parameter:
 * - n: 風船の数 number of balloons
 */
result_t solve(int n) {
    /* TODO */
	result_t result = { true, 0 };
	return result;
}

ヒント：

Balloon Collectingの溶け方は，Backgammonに結構似ています． すぐパソコンをいじるよりも，Backgammonのプログラムを参考にして，下記の点について考えてみて下さい．

  • Backgammonのゲームでは，ステートは 「i ステップ目で，タイル j にいる」でした．今回はステートはなんですか？
  • 最終目的は最短ルートを見つけることなので，各ステートで，何を記録するべきですか？
  • もし，n 個目の風船を無事に拾った場合，次の風船も拾えることが出来るんですか？どうやって確認しますか？ロボットが今持っている風船の数の影響は？

授業中にもう少し具体的なヒントを出すかもしれません…

デバッグ事項

実装する時に色んなバッグが起こるでしょう． 下記，気を付けないと行けないところです：

  • ロボットが風船と同じ時刻で着いた場合はオッケーです　→ 
    if (timeRobotReachBalloon <= baloonFallTime ) {
  // Ok
} else { 
    // 間に合わなかった
}
  • 距離は，最後の風船を回収した後ホームに戻る距離も含める
  • ロボットが動ける期間は，前の風船が落ちた時刻からです
  • どうしても，ある風船を回収出来ない場合は，その次に落ちる風船を確認する必要がない
  • …

提出事項

  • ソースコード Balloon.c を提出
  • レポートの中に：
    • 実装したアルゴリズムの説明（半ページ程度）
    • コンパイル法
    • 実行結果

問題２

自作プログラムもしくは正解プログラム例の解法について簡単に解説し、その時間計算量と空間計算量を表示して下さい．

  • 風船の数 n （今回は n は40以下）
  • 位置の取りうる値の幅 P (今回は 100 以下)
  • 風船の落ちてくる時間の幅 T (今回は50000以下)

提出

Beef+ で提出をお願いします

問題１ → 12月7日 12:00 全員提出（途中でも）

  • 問題１を解けた場合は，問題２も一緒に提出していい

回答例を 12月7日12:00に公開する

問題１の再提出及び問題２ → 12月13日23:59

  • 問題１：正解例と比較して，間違っていた箇所をどのように実現していたか解説すること
  • 問題２：公開した回答例で解けること

資料へ