Codeforces ECR #070 : C. You Are Given a WASD-string...

ちょっと気を抜くと4か月近く離れる…。
https://codeforces.com/contest/1202/problem/C

問題

ロボットがグリッド上で動く。
その際のコマンドが与えられる。
コマンドの指示に従い、ロボットは上下左右に1マスの移動を順に行う。

ここで、コマンドを1つだけ任意の場所に追加することができるとする。
ロボットが通るマスを覆う矩形の面積を最小化せよ。

解法

コマンドの各位置において、

• 最初から今までに移動する上下左右の最大移動量
• 今から最後までに移動する上下左右の最大移動量

を求める。
間に4方向それぞれの移動コマンドを挟んだ場合、両者を合わせて現在位置から上下左右にどこまでの範囲動くかを計算すればよい。

int T;
int N;
string S;
ll L[202020],R[202020],U[202020],D[202020],X[202020],Y[202020];
ll PL[202020],PR[202020],PU[202020],PD[202020],PX[202020],PY[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		FOR(i,N) {
			X[i+1]=X[i];
			Y[i+1]=Y[i];
			if(S[i]=='D') X[i+1]++;
			if(S[i]=='A') X[i+1]--;
			if(S[i]=='W') Y[i+1]++;
			if(S[i]=='S') Y[i+1]--;
			
			L[i+1]=min(L[i],X[i+1]);
			R[i+1]=max(R[i],X[i+1]);
			D[i+1]=min(D[i],Y[i+1]);
			U[i+1]=max(U[i],Y[i+1]);
		}
		PL[N]=PR[N]=X[N];
		PU[N]=PD[N]=Y[N];
		for(i=N-1;i>=0;i--) {
			PL[i]=min(PL[i+1],X[i]);
			PR[i]=max(PR[i+1],X[i]);
			PD[i]=min(PD[i+1],Y[i]);
			PU[i]=max(PU[i+1],Y[i]);
		}
		ll ret=1LL<<60;
		for(i=0;i<=N;i++) {
			ret=min(ret,(max(R[i]-X[i],PR[i]-X[i]+0)-min(L[i]-X[i],PL[i]-X[i]+0)+1)*(max(U[i]-Y[i],PU[i]-Y[i]+0)-min(D[i]-Y[i],PD[i]-Y[i]+0)+1));
			ret=min(ret,(max(R[i]-X[i],PR[i]-X[i]+1)-min(L[i]-X[i],PL[i]-X[i]+1)+1)*(max(U[i]-Y[i],PU[i]-Y[i]+0)-min(D[i]-Y[i],PD[i]-Y[i]+0)+1));
			ret=min(ret,(max(R[i]-X[i],PR[i]-X[i]-1)-min(L[i]-X[i],PL[i]-X[i]-1)+1)*(max(U[i]-Y[i],PU[i]-Y[i]+0)-min(D[i]-Y[i],PD[i]-Y[i]+0)+1));
			ret=min(ret,(max(R[i]-X[i],PR[i]-X[i]+0)-min(L[i]-X[i],PL[i]-X[i]+0)+1)*(max(U[i]-Y[i],PU[i]-Y[i]+1)-min(D[i]-Y[i],PD[i]-Y[i]+1)+1));
			ret=min(ret,(max(R[i]-X[i],PR[i]-X[i]+0)-min(L[i]-X[i],PL[i]-X[i]+0)+1)*(max(U[i]-Y[i],PU[i]-Y[i]-1)-min(D[i]-Y[i],PD[i]-Y[i]-1)+1));
		}
		cout<<ret<<endl;
	}
	
	
}

まとめ

そこまで難しくないけどなぜかDより正答者が少ない。