TopCoder SRM 539 Div2 Hard CaptureFish

実装自体は簡単で、気づくまでが面倒な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11848

問題

ややこしいので問題の図を参照することを推奨。

N+1個のブイが1列に並んでおり、それぞれの間に1匹ずつN匹の魚が泳いでいる。
各魚は、グループOかグループXに属するか、もしくはいずれにも属さない。

ここで以下の条件を満たすように網を配置する。

• 網は輪であり、自己交差はできない。
• ブイのある直線上は、ブイの位置でしか交差できない。
• グループOとグループXの魚は、網の外側と内側にわかれないといけない。

条件を満たす網の配置方法の組み合わせの偶奇を答えよ。

解法

重要な観点として、ブイと交差するのは2か所の場合だけを考えればよい。
4か所交差する場合は、問題文の図を見てわかるとおり上下対称な網の張り方ができるので必然的に偶数通りの張り方ができる。

ブイと交差するのが2か所なら、その2か所を総当たりで試して魚をグループごとに分けられるか判定すればよい。

class CaptureFish {
	public:
	int getParity(string fish) {
		int L=fish.size();
		int ret=0,x,y,i;
		
		FOR(x,L) for(y=x+1;y<=L;y++) {
			int ino=0,inx=0,outo=0,outx=0;
			FOR(i,L) {
				if(fish[i]=='O') {
					if(i>=x && i<y) ino=1;
					else outo=1;
				}
				if(fish[i]=='X') {
					if(i>=x && i<y) inx=1;
					else outx=1;
				}
			}
			if(ino&&inx) continue;
			if(outo&&outx) continue;
			if(ino&&outo) continue;
			if(inx&&outx) continue;
			ret++;
		}
		return ret%2;
	}
};

まとめ

ブイとの交差が2か所と気づけば後は簡単だね。