Google Code Jam 2019 Round 1B : A. Manhattan Crepe Cart

出てたらまぁ通ってたっぽい。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/000000000012295c

問題

グリッド状になった町の交差点のいくつかに人がいる。
各人に対し、初期位置と移動する方向(東西南北)が与えられる。
なお、東西方向に移動する人は、東西は指定されるが南北は任意に移動でき、南北方向に移動する人は南北は指定されるが東西は任意に移動できるとする。

最も多くの人が通る座標のうち、辞書順最小のものを求めよ。

解法

自分は座標圧縮して東西および南北方向に累積和を取って数え上げたが、座標圧縮しなくても通りそうだ。

int P,Q;
int R[503][2];
int C[503][2];
int X[501],Y[501],T[505];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	string s;
	cin>>P>>Q;
	vector<int> Xs,Ys;
	
	FOR(i,P) {
		cin>>X[i]>>Y[i]>>s;
		if(s=="W") T[i]=3,X[i]--;
		if(s=="E") T[i]=1,X[i]++;
		if(s=="N") T[i]=0,Y[i]++;
		if(s=="S") T[i]=2,Y[i]--;
		Xs.push_back(X[i]);
		Ys.push_back(Y[i]);
	}
	Xs.push_back(0);
	Xs.push_back(Q);
	Ys.push_back(0);
	Ys.push_back(Q);
	sort(ALL(Xs));
	sort(ALL(Ys));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	Ys.erase(unique(ALL(Ys)),Ys.end());
	ZERO(R);
	ZERO(C);
	
	FOR(i,P) {
		X[i]=lower_bound(ALL(Xs),X[i])-Xs.begin();
		Y[i]=lower_bound(ALL(Ys),Y[i])-Ys.begin();
		if(T[i]==3) C[X[i]][0]++;
		if(T[i]==1) C[X[i]][1]++;
		if(T[i]==0) R[Y[i]][1]++;
		if(T[i]==2) R[Y[i]][0]++;
	}
	int H=Ys.size();
	int W=Xs.size();
	
	for(y=1;y<H;y++) R[y][1]+=R[y-1][1];
	for(y=H-1;y>=0;y--) R[y][0]+=R[y+1][0];
	for(x=1;x<W;x++) C[x][1]+=C[x-1][1];
	for(x=W-1;x>=0;x--) C[x][0]+=C[x+1][0];
	
	int ma=0,ty=0,tx=0;
	FOR(x,W) FOR(y,H) {
		if(R[y][0]+R[y][1]+C[x][0]+C[x][1]>ma) {
			ma=R[y][0]+R[y][1]+C[x][0]+C[x][1];
			ty=y;
			tx=x;
		}
	}
	
	
	_P("Case #%d: %d %d\n",_loop,Xs[tx],Ys[ty]);
}

まとめ

最初東西南北に一直線に進むと誤読してタイムロスした。