kojingharangの日記

SRM 541 Div1 250 AntsMeet

10:38 |

• アリが東南西北の一定方向に同じ一定速度で動く。同じ場所で出会ったら消滅する。最後に残るのは何匹か。

• すり抜けないように座標を２倍してシミュレーションする。
• （4000*50*50=10,000,000ということでもしかすると微妙？と思ったけどOKだった）

class AntsMeet {
	public:
	int countAnts(vector <int> x, vector <int> y, string dir) {
		int N=x.size();
		VI live(N, 1);
		REP(i, N) {
			x[i]*=2;
			y[i]*=2;
		}
		REP(t, 4000) {
			VI nlive(live);
			REP(i, N) {
				if(!live[i]) continue;
				if(dir[i]=='N') y[i]++;
				if(dir[i]=='S') y[i]--;
				if(dir[i]=='E') x[i]++;
				if(dir[i]=='W') x[i]--;
			}
			REP(i, N) REP(j, N) if(i!=j && x[i]==x[j] && y[i]==y[j] && live[i] && live[j]) nlive[i]=nlive[j]=0;
			live=nlive;
		}
		return accumulate(ALL(live), 0);
	}
};

ツイートする