Codeforces #178 Div2. D. Shaass and Painter Robot

地味にEより難しいかも知れない問題。正答者もEより少ない。
http://codeforces.com/contest/294/problem/D

問題

２次元グリッドのサイズ、ロボットがいる初期位置、初期の向きが与えられる。
このロボットは斜め方向に移動し、グリッド端では反射しながら、通ったマス目を黒く塗っていく。
市松模様にグリッドを塗り終わるまでにロボットが移動するマスの数を答えよ。
また、市松模様が作れないならそう答えよ。

解法

グリッドの高さ・幅は10^5あり、市松模様を作るためには10^10程度のマスを通らないといけないので、地道なシミュレーションは無理。

そこでEditorialを見てみた。
全部のマス目を通ったかシミュレートしなくても、壁際のマスだけすべて通ったかシミュレートすればよいようだ。
すべての(市松模様の黒ますに含まれる)壁際のマスを通れば、壁際以外も含めたすべてのマスを通ったことになる。
また、すべて塗り終わるタイミングも、最後の壁際のマスを塗り終わったところになる。

壁際のマスの数は高々4×10^5なので、後は壁際から壁際への移動を10^6位シミュレートして全部埋まるか試してみればよい。

int W,H;
int TX[2][100001];
int TY[2][100001];
int CT=0;

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar,dx,dy,sx,sy;
	char st[4];
	
	H=GETi();
	W=GETi();
	sy=GETi()-1;
	sx=GETi()-1;
	GETs(st);
	dx=(st[1]=='R')?1:-1;
	dy=(st[0]=='U')?-1:1;
	
	FOR(x,W) {
		if(((sx+sy)%2)==(x%2)){ TX[0][x]++; CT++;}
		if(((sx+sy)%2)==((x+H-1)%2)){ TX[1][x]++; CT++;}
	}
	FOR(y,H) {
		if(((sx+sy)%2)==(y%2)){ TY[0][y]++; CT++;}
		if(((sx+sy)%2)==((y+W-1)%2)){ TY[1][y]++; CT++;}
	}
	
	ll res=1;
	FOR(i,1000000) {
		if(sx==0   && TY[0][sy]){ TY[0][sy]=0; CT--;}
		if(sx==W-1 && TY[1][sy]){ TY[1][sy]=0; CT--;}
		if(sy==0   && TX[0][sx]){ TX[0][sx]=0; CT--;}
		if(sy==H-1 && TX[1][sx]){ TX[1][sx]=0; CT--;}
		if(CT==0) {
			cout << res << endl;
			return;
		}
		
		if(sx==0) dx=1;
		if(sx==W-1) dx=-1;
		if(sy==0) dy=1;
		if(sy==H-1) dy=-1;
		//_P("%d %d (%d %d) %d %lld\n",sx,sy,dx,dy,CT,res);
		
		int ml=1000000;
		if(dx>0) ml=min(ml,W-1-sx);
		if(dx<0) ml=min(ml,sx);
		if(dy>0) ml=min(ml,H-1-sy);
		if(dy<0) ml=min(ml,sy);
		
		res += ml;
		sx += ml*dx;
		sy += ml*dy;
	}
	_P("-1\n");
	return;
}

まとめ

壁際だけ全部通ればよい、と気づくまでが大変だ。