SRM 541 div1 easy: AntsMeet

問題

TopCoder Statistics - Problem Statement

蟻が N 匹 xy 平面上にいる。それぞれの蟻の座標は (xi, yi) で, 向いている向きは direction[i](dx=1, dy=1, dx=-1, dy=-1 のいずれか) である。蟻は同時に同速度で動き始める。同時に複数匹に蟻が出会った場合, それらの蟻は消滅する。
最終的に残っている蟻の数を求めよ。

解法

単純にシミュレーションします。t = 10000 程度まで蟻を動かしていき, 同時に同じ座標にいたら消す, というのを繰り返すだけです。
一つ注意なのは, 例えば dx=-1 と dx=1 の蟻が出会う場合, 0.5 秒単位で蟻が出会う可能性があることです。これは x 座標を 2 倍にして速度はそのままにすることで解決します。

const int MAXN = 55;
const int INF = 1e9;
bool done[MAXN];
bool ndone[MAXN];

class AntsMeet {
public:
    int countAnts(vector <int> x, vector <int> y, string direction) {
        int N = x.size();
        vector<int> dir(N);
        for (int i = 0; i < N; i++) {
            if (direction[i] == 'N') dir[i] = 1;
            if (direction[i] == 'E') dir[i] = 0;
            if (direction[i] == 'S') dir[i] = 3;
            if (direction[i] == 'W') dir[i] = 2;
        }
        for (int i = 0; i < N; i++) {
            x[i] *= 2;
            y[i] *= 2;
        }
        memset(done, false, sizeof(done));
        for (int t = 0; t < 10000; t++) {
            for (int i = 0; i < N; i++) {
                x[i] += dx[dir[i]];
                y[i] += dy[dir[i]];
            }
            memset(ndone, false, sizeof(ndone));
            for (int i = 0; i < N; i++) ndone[i] = done[i];
            for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
                if (done[i] || done[j]) continue;
                if (i==j) continue;
                if (x[i] == x[j] && y[i] == y[j]) {
                    ndone[i] = ndone[j] = true;
                }
            }
            for (int i = 0; i < N; i++) done[i] = ndone[i];
        }
        int ans = 0;
        for (int i = 0; i < N; i++) ans += !done[i];
        return ans;
    }
};