読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 566 Div1 Easy PenguinSledding

SRM

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

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

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

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

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

ケース3で辺1本のケースを除いているのは、辺が1本のケースは2つの点で二重カウントしてしまうのを防ぐため。
ケース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連発してそうだったね。
面白い問題でした。

広告を非表示にする