解いた問題のソースコードと解説など。


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;
  }
};

いまいちよくわかってない。

しょげないでよBaby 眠れば治る