SRM541 Div1 Easy(250), Div2 Medium(500) AntsMeet
AntsMeet
xとyの範囲が小さいので、単にシミュレーションすれば良い。ただし、アリがxやyが整数ではない位置で衝突する場合を考慮する必要がある。その場合でも衝突地点の座標は0.5の整数倍なので、あらかじめ座標を2倍にしておくのが簡単。
#include <vector> #include <string> #include <set> #include <utility> using namespace std; class AntsMeet{public: int countAnts( vector <int> x, vector <int> y, string direction ) { int n = (int)x.size(); for ( int i=0; i<n; i++ ) x[i] *= 2, y[i] *= 2; vector<bool> live(n,true); for ( int s=0; s<10000; s++ ) { for ( int i=0; i<n; i++ ) { if ( direction[i]=='N' ) y[i]++; if ( direction[i]=='E' ) x[i]++; if ( direction[i]=='S' ) y[i]--; if ( direction[i]=='W' ) x[i]--; } for ( int i=0; i<n; i++ ) if ( live[i] ) { bool f = false; for ( int j=i+1; j<n; j++ ) if( live[j] && x[i]==x[j] && y[i]==y[j] ) live[j] = false, f = true; if ( f ) live[i] = false; } } int ans = 0; for ( int i=0; i<n; i++ ) if ( live[i] ) ans++; return ans; }};