SRM528 DIV2 1000 Mosquitoes

直線状を移動する複数の蚊を効率的に殺す方法を考えるゲーム。

　時間がfixなら、端点のパターンをすべて試して最適なのを選ぶだけ。時間を選ぶのが難しいが、最適解において、ある２匹の蚊の距離は2Rになっていると仮定してよい。もし最適解において両端の蚊の距離が2R未満だったとしても、時間の経過とともに蚊は拡散していくのであるポイントで両端の蚊の距離は2Rになるからである。拡散しない場合（相対速度が一定）場合は、t=0のときに計算しているのでOK。

　自力では全く解けませんでした。蚊が時間の経過とともにある部分に密集していき、そのあとは拡散していくというようなイメージは浮かんだので、三分探索みたいなことをするのかなーと思ったら全く違った。この問題のように、”ある区間内とかある範囲内に何かを収めたい”というような問題の場合は、同じような思考が使える場合がよくあると思う。（四角形の中にあると言われたら、少なくとも2つの点は辺に接していると仮定していいとか。）最適解があって、そこから最適性を崩すことなく解を上手く動かすことで最適解にある仮定を設定することができ効率的な探索ができる、という考え方はしっかり身に付けたい。

view plainprint?

1. const double EPS = 1e-9;  
2. class Mosquitoes {  
3. public:  
4.     int getMaximum(vector<int> xInit, vector<int> v, int R) {  
5.         int N = xInit.size();  
6.         int ret = 0;  
7.         vector<double> pos(N);  
8.   
9.         // t = 0  
10.         REP(i, N) pos[i] = xInit[i];  
11.         sort(ALL(pos));  
12.         REP(p, N) FOR (q, p, N) {  
13.             if (pos[q] - pos[p] <= 2*R+EPS)  
14.                 ret = max(ret, q-p+1);  
15.         }  
16.   
17.         REP(i, N) REP(j, N) if (i != j){  
18.             if (v[i] == v[j]) continue;  
19.   
20.             // t = time when the distance between mosquito[i] and mosquito[j] = 2*R  
21.             double t = 1.0 * (xInit[i]-xInit[j]-2*R) / (v[j] - v[i]);  
22.             if (t < EPS) continue;  
23.   
24.             REP(k, N) pos[k] = xInit[k] + v[k] * t;  
25.             int cnt = 0;  
26.             REP(k, N) {  
27.                 if (pos[j] <= pos[k] + EPS && pos[k] <= pos[i] + EPS)  
28.                     ++cnt;  
29.             }  
30.             ret = max(ret, cnt);  
31.         }  
32.   
33.         return ret;  
34.     }  
35. };  

const double EPS = 1e-9;
class Mosquitoes {
public:
    int getMaximum(vector<int> xInit, vector<int> v, int R) {
        int N = xInit.size();
        int ret = 0;
        vector<double> pos(N);

        // t = 0
        REP(i, N) pos[i] = xInit[i];
        sort(ALL(pos));
        REP(p, N) FOR (q, p, N) {
            if (pos[q] - pos[p] <= 2*R+EPS)
                ret = max(ret, q-p+1);
        }

        REP(i, N) REP(j, N) if (i != j){
            if (v[i] == v[j]) continue;

            // t = time when the distance between mosquito[i] and mosquito[j] = 2*R
            double t = 1.0 * (xInit[i]-xInit[j]-2*R) / (v[j] - v[i]);
            if (t < EPS) continue;

            REP(k, N) pos[k] = xInit[k] + v[k] * t;
            int cnt = 0;
            REP(k, N) {
                if (pos[j] <= pos[k] + EPS && pos[k] <= pos[i] + EPS)
                    ++cnt;
            }
            ret = max(ret, cnt);
        }

        return ret;
    }
};