TopCoder SRM 539 Div2 Hard CaptureFish

問題

直線上にN個のブイがあり、ブイとブイの間に一匹ずつ魚がいる。
魚にはそれぞれ'O', 'X', '*'の文字が割り振られている。
この魚を次のように網で囲う。

• 網は自己交差のない閉曲線で表される。
• 網は直線と、ブイの点のみで交わる。
• ブイで直線と網が交わったとき、同じ側へ網が戻らない。
• Oの文字が割り振られた魚は全て網の同じ側に、Xの文字が割り振られた魚はOの文字の魚とは反対側の網の全て同じ側にいなければならない。

魚を網で囲う方法は偶数か奇数か答えよ。

制約条件

魚の数≦50

方針

上下対称な魚の囲い方が奇数通りあれば、求める数は奇数。
上下対称な魚の囲い方は、連続する魚i≦x＜jを囲う囲い方のみ。

それぞれの囲い方がvalidかどうかを見て、validなものだけ数える。

ソースコード

class CaptureFish {
	public:
	int getParity(string fish) 
	{
		int n = fish.size(), ans = 0;
		rep(i,n) for(int j = i+1; j <= n; j++){
			bool out[2] = {}, in[2] = {};
			rep(k,n){
				if(i <= k && k < j){
					if(fish[k] == 'O') in[0] = 1;
					if(fish[k] == 'X') in[1] = 1;
				}
				else{
					if(fish[k] == 'O') out[0] = 1;
					if(fish[k] == 'X') out[1] = 1;
				}
			}
			if(in[0] && in[1] || out[0] && out[1]) continue;
			if(in[0] && out[0] || in[1] && out[1]) continue;
			ans ^= 1;
		}
		return ans;
	}
};