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