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