1000 Mosquitoes

2011-12-29

14:07 |

数直線上で蚊がそれぞれの位置から等速直線運動をする。時刻と円の中心を適切に決めて半径R以内に入る蚊の最大数を求める。

蚊の数も初期位置の範囲も小さいし、t>=200くらいでみんな外向きに広がってっちゃうので 0～300 を微小時間に分けて円の端の位置を全通り試してみよう
最大の速さ 100 なので 0.01 秒単位でいいかな
サンプルと、速さ100のときのテストも通ったので出したら failed system test.
よーく追って見ると、0.777777777... のときに一瞬だけ 4 匹が半径 1 以内に入るケースで 3 匹と答えていた。。
物理シミュレーションで薄い壁をボールが通り抜けちゃったみたいな感じ。

任意の２匹の蚊の距離が 2R になる瞬間すべてについて位置を求めてソートしてどこまで R に入ってるか確かめると良いらしい。
変化は連続なんだけど求める答えが変わらないような有限のサンプルに落とすという例であろう。

↓最初に書いただめなやつ

class Mosquitoes { 
  public: 
  int getMaximum(vector <int> xInit, vector <int> v, int R) { 
    int ans = -1; 
    //int K=2; 
    int KT=100; 
    REP(idx, v.size()) 
    for(int side=-1;side<=1;side+=2) 
    { 
      for(int t=0;t<300*KT;t++) 
      { 
        double x = (xInit[idx]+(double)t/KT*v[idx])+side*R; 
        int lans = 0; 
        REP(i, v.size()) lans += fabs(x - (xInit[i]+(double)t/KT*v[i]))<=R; 
        ans = max(ans, lans); 
      } 
    } 
    return ans; 
  }

↓後で通したやつ

class Mosquitoes {
	public:
	int getMaximum(vector <int> xInit, vector <int> v, int R) {
		int ans = -1;
		vector<double> ts;
		int N = v.size();
		REP(i, N) REP(j, N) {
			if(i==j || v[i]==v[j]) continue;
			double t0 = (xInit[i]-xInit[j]-2.0*R)/(v[j]-v[i]);
			if(t0>=0.0) ts.push_back(t0);
			double t1 = (xInit[i]-xInit[j]+2.0*R)/(v[j]-v[i]);
			if(t1>=0.0) ts.push_back(t1);
		}
		ts.push_back(0.0);
		//cout<<ts<<endl;
		vector<double> pos(N);
		FOR(t, ts) {
			REP(i, N) pos[i] = xInit[i]+*t*v[i];
			sort(ALL(pos));
			REP(i, N) {
				for(int j=i;j<N;j++) {
					if(pos[j] - pos[i] <= 2.0*R+0.00000001) ans = max(ans, j-i+1);
				}
			}
		}
		return ans;
	}