Search on the blog

2011年5月22日日曜日

Google Code Jam 2011 Round1B

ぼろ負けでした。

集中力がなかったです。
変数名の重複とか、違う変数を参照していたりとか初歩的なミスが多すぎました。

Problem Bの二分探索が面白かったので簡単に解説。
基本的なアイディアはtに対して二分探索をかけます。与えられたtに対してすべての商人がdの間隔を保って拡散できるなら、tを小さく、できないならtを大きくします。

問題は、与えられたtに対して、商人が十分に拡散できるかどうか。。
これは一番左にいる商人から処理をしていけばいいです。一番左の人は他の人からより離れるためできる限り左に行きます。左から二番目の人も同様にできる限り(一番左の人との間隔がd以下にならない範囲で)左にいきます。これを続ければいいです。
途中で、どうがんばっても自分の左の人からd以上離れることができないとなった時点で、そのtでは十分に拡散できないと判断します。
ということで、binary search + greedyで解ける問題でした。

以下練習で通したソース。
largeの問題は、商人の人数および、間隔dが10^6なので、二分探索の上限は10^6 * 10^6程度です。ちょっと余裕をもって10^13としています。

int main() {
int t;
cin >> t;

REP(ii, t) {
int c, d;
cin >> c >> d;

int v, vs = 0;
vector<int>ps;
int p;
REP(i, c) {
cin >> p >> v;
vs += v;
REP(j, v)
ps.push_back(p);
}
SORT(ps);
double hi = 1.0E+13; // 10^6 * 10^6 < 10^13
double lo = 0;
double ret;

REP(i, 100) {
ret = (hi + lo) / 2;

bool ck = true;
double next = -1e100; // -inf
REP(j, vs) {
if (ps[j] + ret < next) {
ck = false;
break;
}
next = MAX(next + d, ps[j]- ret + d);
}
if (ck)
hi = ret;
else
lo = ret;
}
printf("Case #%d: %lf\n", ii+1,ret);
}

return 0;
}


0 件のコメント:

コメントを投稿