SRM Div2 528 Hard Mosquitoes
問題
http://apps.topcoder.com/stat?c=problem_statement&pm=11654&rd=14553
蚊が数直線上でxInit[i]の初期位置におり、毎秒v[i]の速度で移動する。あなたは前後R以下にいる蚊を殺傷できる爆弾を持っており、任意の時刻に任意の位置で爆発させることができる。殺傷できる蚊の数を最大化せよ。
やりかた
ある2匹の蚊について、もっとも無駄がなく殺傷できるというのは2匹の蚊が爆弾の直径の両端にいる時である。このときに同時に殺傷できる他の蚊の数も数えてやればいい。
class Mosquitoes { public: int getMaximum(vector <int> xInit, vector <int> v, int R) { int result = 1; int N = v.size(); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(v[i] == v[j]) continue; double t1 = (double)(2 * R - (xInit[j] - xInit[i])) / (v[j] - v[i]); if(t1 < 0) continue; double left = xInit[i] + v[i] * t1; double right = xInit[j] + v[j] * t1; int cnt = 0; for(int k = 0; k < N; k++){ double pos = xInit[k] + v[k] * t1; if(left <= pos && pos <= right) cnt++; } result = max(cnt, result); } } return result; } };
いまいちよくわかってない。
Get up! 明日のSUPER ST@R!