Codeforces #593 Div2 D. Alice and the Doll

なんで落としたんだろ。
http://codeforces.com/contest/1236/problem/D

問題

グリッドが与えられる。
一部のマスはすでに埋まっている。
初期状態でコマが(1,1)にいて上を向いているとする。
コマを隣接マスに動かすことを繰り返し、埋まっていないマスをちょうど1回ずつ通ることができるだろうか。
なお、移動の向きを変えるときは常に右90度のみ方向転換可能とする。

解法

右回りにしか動けないので、基本的には埋まったマスまたは通過済みのマスの直前まで行って曲がるということを繰り返す。
あとは愚直にシミュレーションして、通過したマス数をカウントしよう。

int H,W,K;
set<int> Rs[101010];
set<int> Cs[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(i,K) {
		cin>>y>>x;
		y--,x--;
		Rs[y].insert(x);
		Cs[x].insert(y);
	}
	
	int L=0,R=W-1,U=0,D=H-1;
	ll walk=1;
	int turn=0;
	while(L<R || U<D) {
		if(turn==0) {
			auto it=Rs[U].lower_bound(L);
			int NR=R;
			if(it!=Rs[U].end()) NR=min(NR,*it-1);
			if(L==NR && (L||U)) break;
			R=NR;
			walk += R-L;
			if(L||U) L++;
		}
		else if(turn==1) {
			auto it=Cs[R].lower_bound(U);
			int ND=D;
			if(it!=Cs[R].end()) ND=min(ND,*it-1);
			if(U==ND) break;
			D=ND;
			walk += D-U;
			U++;
		}
		else if(turn==2) {
			auto it=Rs[D].lower_bound(R);
			int NL=L;
			if(it!=Rs[D].begin()) {
				it--;
				NL=max(NL,*it+1);
			}
			if(R==NL) break;
			L=NL;
			walk += R-L;
			R--;
		}
		else if(turn==3) {
			auto it=Cs[L].lower_bound(D);
			int NU=U;
			if(it!=Cs[L].begin()) {
				it--;
				NU=max(NU,*it+1);
			}
			if(D==NU) break;
			U=NU;
			walk += D-U;
			D--;
		}
		turn=(turn+1)%4;
	}
	
	if(walk+K==1LL*H*W) {
		cout<<"Yes"<<endl;
	}
	else {
		cout<<"No"<<endl;
	}
}

まとめ

この回は遅刻参加だったので結果はいまいち。