TopCoder SRM 566 Div1 Easy PenguinSledding

新年初SRM。
後述の通りEasyで予想外に時間かかってしまったが、ラスト１分半でMediumをsubmitさせ、なんとか２問解け切った。
おかげでSRM563で大ミスして暴落したレートが元の水準まで戻った。

では１問目から。
http://community.topcoder.com/stat?c=problem_statement&pm=12336

点と辺からなるグラフ構造が与えられるので、辺を減らして点の座標が(点同士が一直線にならない限り）どう動いても辺同士が交差しないような残し方の組み合わせを求める。

これは以下の和で計算できる。

1. 辺が0本もないケース : 1通り
2. 辺が1本だけ残るケース : 元の辺の数
3. 点を１つ選び、そこから２本以上の辺が出ているケース ： (1<<辺) - (辺+1) （辺+1は、１本辺が出るケースと0本のケースを除いている)
4. 三角形ができるケース

ケース3で辺１本のケースを除いているのは、辺が１本のケースは２つの点で二重カウントしてしまうのを防ぐため。
ケース4の三角形検出は、点が高々50個なのでO(V^3)の安直なコードで問題なし。
自分はケース4の三角形に気づくまでかなり苦戦したし、ほかにも同じ人が多かったと思われる。
ただ、テストケースで三角形があったおかげでsubmitした人の正答率は高いし、今回チャレンジの数もすごい少なかったね。

class PenguinSledding {
	int V,E;
	int EE[100];
	int mp[100][100];
	public:
	long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2) {
		ll res=0;
		V=numCheckpoints;
		E=checkpoint1.size();
		
		int x,y,z;
		ZERO(EE);
		ZERO(mp);
		FOR(x,E) {
			EE[checkpoint1[x]-1]++;
			EE[checkpoint2[x]-1]++;
			mp[checkpoint1[x]-1][checkpoint2[x]-1]=1;
			mp[checkpoint2[x]-1][checkpoint1[x]-1]=1;
		}
		FOR(x,V) res += (1LL<<EE[x]) - (EE[x]+1);
		res += E+1;
		
		//三角形
		FOR(x,V) for(y=x+1;y<V;y++) for(z=y+1;z<V;z++) 
			if(mp[x][y] && mp[y][z] && mp[z][x]) res++;
		
		return res;
		
	}

};

まとめ

ケース3まではすぐ思いついたものの三角形に気づくのに遅れたけど、何とか解けきれてよかった。
テストケースになかったらWA連発してそうだったね。
面白い問題でした。