TopCoderOpen 2020 Round3A : Easy RectangularObstacle

しょうもないミスで大幅レート減。
https://community.topcoder.com/stat?c=problem_statement&pm=15447&rd=18111

問題

無限に広がる2次元グリッドを考える。
今コマが(0,0)に置かれており、最大s回隣接マスに移動できるとする。
グリッド中、Y座標が正の領域で、かつx=0を挟むような矩形領域(x1,y1)-(x2,y2)が移動不可であるとき、到達不可なマスは何通りか。

解法

• Y座標が0以下の領域は(s+1)^2通り。
• Y座標が1以上y2以下の領域はy座標を総当たりしよう。
• Y座標がy2より大きい領域については、(x1-1,y2+1)か(x2+1,y2+1)を通るのが最短。よって、それぞれから移動可能な領域を求めたのち、両者いずれからでも到達可能な領域を引くとよい。

ここではY座標を走査したが、X座標を走査してもよい。

class RectangularObstacle {
	public:
	long long countReachable(int x1, int x2, int y1, int y2, int s) {
		ll ret=0;
		
		// 0 - -s
		ret += 1LL*(s+1)*(s+1);
		ll y;
		for(y=1;y<=y2;y++) {
			if(y<y1) {
				if(y<=s) {
					ret+=1+(s-y)*2;
				}
			}
			else {
				int x=s-y;
				if(x>x2) ret+=x-x2;
				if(-x<x1) ret+=x-(-x1);
			}
		}
		
		ll L=s-(y2+1)-(-x1+1);
		ll R=s-(y2+1)-(x2+1);
		ll D=x2-x1+1;
		if(L>R) swap(L,R);
		cout<<L<<" "<<R<<" "<<D<<endl;
		if(L<0 && R>=0) {
			ret+=1LL*(R+1)*(R+1);
		}
		else if(L>=0) {
			ret+=1LL*(R+1)*(R+1);
			ret+=1LL*(L+1)*(L+1);
			ll C=R+L-D;
			if(C>0) {
				if(C%2==1) {
					C=(C+1)/2;
					ret-=1LL*C*C;
				}
				else {
					C/=2;
					ret-=1LL*C*(C+1);
				}
			}
		}
		
		
		return ret;
		
		
	}
}

まとめ

久々にSRMっぽいミスをしたな…。