Codeforces #205 Div2. E. Antichain

これは何とか解けた。
http://codeforces.com/contest/353/problem/E

問題

数字がリング状に並んでいるとする。
個々の数字がわからないが、隣接する数字同士の大小関係が与えられる。
この時、互いに大小比較が不可能な要素の数の最大値を答えよ。

解法

A[i-1]A[i+1]>A[i+2]A[i+2]A[i+4]…のようなケースが残る。
この場合、大きい方の要素と小さい方の要素から構成される２部グラフにおける最大独立集合を求める問題となるが、２部グラフの辺の構成が非常に単純なので、まじめにフローを解かなくても(要素数+1)/2個の点を選べば最大独立集合を構成できることがわかる。

string S;

void solve() {
	int f,i,j,k,l, x,y,r,t;
	
	cin>>S;
	l=S.size();
	//rotate
	FOR(x,l-1) if(S[x]=='1' && S[x+1]=='0') break;
	if(x!=l-1) S=S.substr(x+1)+S.substr(0,x+1);
	
	vector<int> P;
	FOR(i,l) if(S[(l+i-1)%l] != S[i]) P.push_back(i);
	vector<int> P2=P;
	r=0;
	k=P.size();
	x=-1;
	FOR(i,k) {
		if((P2[i]+1)%l != P2[(i+1)%k]%l) {
			r++;
			P[i]=P[(i+1)%k]=-1;
			if(x<0) x=i;
		}
	}
	if(x<0) {
		r+=k/2;
	}
	else {
		FOR(y,P.size()) {
			if(P[(x+y)%k]==-1) continue;
			t=0;
			while(y+t<k && P[(x+y+t)%k]!=-1) t++;
			r+=(t+1)/2;
			y+=t-1;
		}
	}
	
	cout << r << endl;
}

まとめ

まじめに二部グラフのマッチングを解かなくてよかった。