SRM541 Div1 Easy - AntsMeet

問題

n匹のアリがいて、i匹目の座標は (x[i], y[i]) である
i匹目のアリはd[i]方向に毎秒1だけ進み、2匹以上のアリがどこかでぶつかるとそれらは全て消える
いつまでも消えないアリは何匹いるか求めよ

1 <= n <= 50
|x[i], y[i]| <= 1000

解法

座標を2倍すればぶつかる場所が必ず格子点上になる
あとはシミュレーションするだけ

class AntsMeet {
public:
	int countAnts(vector<int> x, vector<int> y, string d) {
		int n = x.size(), fin[55] = {};
		rep(i,n) x[i] *= 2, y[i] *= 2;
		rep(k,4000) {
			rep(i,n) if (!fin[i]) {
				if (d[i]=='N') y[i]++;
				else if (d[i]=='E') x[i]++;
				else if (d[i]=='W') x[i]--;
				else y[i]--;
			}
			map<pair<int,int>, vector<int> > m;
			rep(i,n) if (!fin[i]) m[{x[i],y[i]}].push_back(i);
			each(i,m) if (i.second.size()>=2) each(j,i.second) fin[j] = 1;
		}
		return n - accumulate(fin, fin+55, 0);
	}
};