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