GCJ2011 Round1B 問題B

その他 過去問

問題

何人かのホットドック屋さんが通りで商売している。しかし、互いにDメートルは離れて商売したいと考えている。このとき、それぞれがDメートル離れるためには最低何秒かかるか。ホットドック屋さんは1秒で1メートル動けるとする。
ホットドック屋さんの位置情報は、通りを数直線上と見なし、その場所とそこにいる人数で与えられる。

考え方

2分探索。t秒でそれぞれがDメートル離れるように動くことができるかどうかで回す。
t秒の上限は、10^6人いてDは10^6なので、全員原点にいるときを考え、10^12以上とればいい。
判定は、t秒でtメートル動けるので、一番右にいる人からできるだけ右にいくように配置していって、それぞれの距離がD以上になるかで判定した。

反省

  • 2分探索の収束

100回のループで10^(-30)ぐらいまで行くので、通常100＋α程度回せばいい。

  • 上限値の見積もり

できるだけ大きめに取る。ただし、doubleの仮数などで精度が大丈夫かは確認する。

  • 小数計算

今回の自分のはまったところ。
ホットドック屋さんのとの距離がD以上離れられるかどうかの判定で、

if(fabs(ホットドック屋さんの位置-次のホットドック屋さんの位置)<(double)D) return false;

と書いた。けど、どうもこれがいけなかったみたいで、

#define EPS 1.0e-10
#define LT(x,y) ((x)+EPS<(y))
if(LT(fabs(ホットドック屋さんの位置-次のホットドック屋さんの位置), (double)D)) return false;

としたら通った。というかちゃんと収束した。
なんでそうなるかはわかってないけど、「小数の比較」をするときはどんな場合であれEPSを使うようにする。