Codeforces #305 Div1 D. Mike and Fish

言われてみれば普段のDよりは簡単。
http://codeforces.com/contest/547/problem/D

問題

２次元グリッド上でN個のセルの位置が指定される。
N個の各セルを赤か青で塗ったとき、各行及び各列内の赤セルと青セルの数の差が1以下になるように塗れ。

解法

指定されるセルの列・行の範囲はともに1～Lだとする。
ここで列に対応するL個の点と、行に対応するL個の点、計2L個の頂点からなる2部グラフを考える。
y行x列のセルが指定されている場合、y行に対応する点とx列に対応する点の間に辺を張る。

問題の条件を満たすには、N個の辺を赤か青で塗ったとき、各点がつながる赤辺と青辺の数の差が1以下で有ればよい。
各頂点につながる辺の数が偶数なら閉路が構築でき、その閉路を1本ずつ赤青交互に塗ることで、この閉路に関する頂点は赤青辺の差が0となる。

そこで、先に辺の次数が奇数の点を処理しよう。
次数が奇数の点を見つけたら、そこから残り辺が奇数である間DFSで辺を適当にたどり、たどった辺を赤青交互に塗ってグラフから取り除いていく。
こうすると、各点につながるの赤青の辺の数の差は1以下になる。

奇数の点の処理を終えたら、後はすべて頂点の次数は偶数なので上記のとおり閉路を成す辺を赤青交互に塗ればよい。

int N;
int X[202000],Y[202000];
map<pair<int,int>,int> M;
string S;

set<int> XE[202000],YE[202000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		M[{X[i],Y[i]}]=i;
		XE[X[i]].insert(Y[i]);
		YE[Y[i]].insert(X[i]);
		S+=" ";
	}
	
	stack<pair<int,int> > Q;
	FOR(j,2) {
		FOR(i,202000) {
			if(j==0) {
				if(XE[i].size()%2) Q.push({i,1});
				if(YE[i].size()%2) Q.push({-i,1});
			}
			else {
				if(XE[i].size()%2==0 && XE[i].size()) Q.push({i,1});
				if(YE[i].size()%2==0 && YE[i].size()) Q.push({-i,1});
			}
		}
		
		while(Q.size()) {
			int cur=Q.top().first;
			if(Q.top().second) x=0;
			x^=1;
			Q.pop();
			
			if(cur>0) {
				if(XE[cur].size()==0) continue;
				if(j==0 && XE[cur].size()%2==0) continue;
				
				int tar=*XE[cur].begin();
				XE[cur].erase(tar);
				if(x) S[M[{cur,tar}]]='r';
				else S[M[{cur,tar}]]='b';
				YE[tar].erase(cur);
				Q.push({-tar,0});
			}
			else {
				cur=-cur;
				if(YE[cur].size()==0) continue;
				if(j==0 && YE[cur].size()%2==0) continue;
				
				int tar=*YE[cur].begin();
				YE[cur].erase(tar);
				if(x) S[M[{tar,cur}]]='r';
				else S[M[{tar,cur}]]='b';
				XE[tar].erase(cur);
				Q.push({tar,0});
			}
		}
	}
	
	cout<<S<<endl;
}

まとめ

わかってしまえば考え方は簡単。