SRM 541 250pt : AntsMeet

問題概要

蟻がN(<50)匹いる。最初に(x,y)(|x|,|y|<1000)の範囲にいて、それぞれ決まった方向(4方向のいずれか)に同じ速度で移動する。衝突が起きたらその場で消える。十分時間が立った後に蟻が何匹残っているか求める問題。

解法

すれ違いを避けるため、最初に座標を全部2倍(どうでもいいことだけど、この座標を2倍するテクニックって結構頻出で、自分は勝手に座標拡大といっている)して毎秒1単位の速度で動かしてシミュレーションする。衝突が起こるとき、かならず衝突場所は|x|,|y| < 2000なので全ての蟻がその中からいなくなるまで動かせばよい。あるいは黙って4000ターンほど動かせばよい。
もちろん、0.5ずつ動かすことにすれば座標2倍する必要はないし2べきの割り算なので誤差もでない。だけど、それでも浮動小数点数は回避できるなら回避した方がよいと思う。

acceptされたコード

#include <algorithm>
#include <vector>
#include <string>
using namespace std;

const int MAX_N = 50;

bool rem[MAX_N];

struct AntsMeet {

	int countAnts(vector <int> x, vector <int> y, string direction) {
		const int N = x.size();
		for(int i=0; i<N; ++i){
			x[i] *= 2;
			y[i] *= 2;
		}

		for(;;){
			for(int i=0; i<N; ++i)if(!rem[i]){
				if(direction[i] == 'E'){
					++x[i];
				}
				else if(direction[i] == 'W'){
					--x[i];
				}
				else if(direction[i] == 'N'){
					++y[i];
				}
				else{
					--y[i];
				}
			}

			for(int i=0; i<N; ++i)if(!rem[i]){
				for(int j=i+1; j<N; ++j)if(!rem[j]){
					if(x[i] == x[j] && y[i] == y[j]){
						rem[i] = rem[j] = true;
					}
				}
			}

			bool in = false;

			for(int i=0; i<N; ++i)if(!rem[i]){
				in |= (abs(x[i]) <= 2100 && abs(y[i]) <= 2100);
			}

			if(!in){
				break;
			}
		}

		int ans = 0;
		for(int i=0; i<N; ++i){
			if(!rem[i]){
				++ans;
			}
		}
		return ans;
	}

};