yukicoder : No.274 The Wall

３問とも急ぎすぎて細かいミスを重ねてしまい、回答が遅れてしまった。
http://yukicoder.me/problems/658

問題

大きさ1x1の正方形ブロックを横にM個連結した大きさ1xMのブロックがある。
各1x1ブロックは基本白色だが、左からL[i]～R[i]番目の1x1ブロックはピンク色である。
これらの1xMブロックは180度回転することが可能である。

このような1xMブロックがN個与えられるので、縦に綺麗に積んでいきたい。
各1xMブロックは180度回転しても良い場合、各列ピンクである1x1ブロックが1行以下であるように並べられるか答えよ。

解法

向きの確定していない1xMブロックのうち、ピンク色の1x1ブロックが一番左側に来るような1xMブロックを貪欲に選んで行けばよい。
その際、すでに向きが確定してしまった1xMブロックと同じ列にピンク色が共に来てしまう場合、未確定なブロックは180度回転させる。
180度回転させても、すでに向きが確定してしまった1xMブロックと同じ列にピンク色が共に来てしまう場合、条件は満たせない。

以下のコードはO(N^2)だけど、恐らくO(N*logN)でも通ると思う。

int N,M;
int L[2020],R[2020];
int vis[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>L[i]>>R[i];
	
	int left=0;
	FOR(i,N) {
		int y=-1;
		FOR(x,N) if(vis[x]==0) {
			
			if(M-1-R[x]<L[x]) {
				L[x]=M-1-L[x];
				R[x]=M-1-R[x];
				swap(L[x],R[x]);
			}
			
			if(left>L[x]) {
				L[x]=M-1-L[x];
				R[x]=M-1-R[x];
				swap(L[x],R[x]);
			}
			if(left>L[x]) return _P("NO\n");
			if(y==-1 || L[x]<L[y]) y=x;
		}
		if(y==-1) return _P("NO\n");
		left=R[y]+1;
		vis[y]=1;
	}
	_P("YES\n");
	
}

まとめ

二部グラフとかにならないかなとも思ったけど、想定解は2-SATなのね。