TopCoder SRM 730 Div2 Subgraphs

解けたけど手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=14817

問題

整数Kが与えられる。
以下の条件を満たす無向グラフと頂点の選択法を構築せよ。

• 頂点数2K以下の無向グラフである。
• 頂点をK個選ぶと、元のグラフのうちそのK個からなる部分グラフの辺の数が0～K(K-1)/2本の全パターン構築できる。

解法

K個の頂点を選んだ時に辺の数が0の場合とK(K-1)/2本のパターンがある。
ということは、まずK頂点は完全グラフをなし、残りK頂点はK頂点内に辺がないものという構成でなければならない。
あとは前者と後者をどうつなぐか考えよう。

前者のうちn頂点を選んだとすると、その時点で辺がn(n-1)/2本ある。
前者のうちn+1頂点を選ぶと辺がn(n+1)/2本になる。
よって、前者からn頂点選び、後者から(n-k)頂点を選ぶケースで、辺の数がn(n-1)/2～n(n+1)/2-1本のケースをカバーできればよい。
これには、前者と後者を結ぶことで0～(n-1)本のケースを再現できればよいことになる。
よって、後者の頂点は、前者に対し(n-1)、(n-2)、…、0,0,0本と辺を張るようにしよう。
(n-k)個の後者の頂点のうち1個の頂点だけは辺の数を0～(n-1)から選ぶこととし、残りは0本の辺をもつものを選べば、n(n-1)/2～n(n+1)/2-1本のケースをカバーできる。

class Subgraphs {
	public:
	vector <string> findGroups(int k) {
		vector<string> S;
		int i,j;
		FOR(i,2*k) {
			string T(2*k,'0');
			FOR(j,2*k-i) T[j]='1';
			T[i]='0';
			S.push_back(T);
		}
		
		FOR(i,k*(k-1)/2+1) S.push_back("");
		for(i=0;i<=k;i++) {
			for(j=0;j<k;j++) {
				string T(2*k,'N');
				int nk=i;
				if(i!=k) T[k+j]='Y', nk++;
				int x,y;
				FOR(x,i) T[k-1-x]='Y';
				for(x=2*k-1;x>=0;x--) {
					if(nk==k) break;
					if(T[x]=='N') T[x]='Y', nk++;
				}
				
				int num=0;
				FOR(y,2*k) FOR(x,y) if(T[x]=='Y' && T[y]=='Y' && S[x][y]=='1') num++;
				S[2*k+num]=T;
			}
		}
		return S;
	}
}

まとめ

割と頭が混乱して手間取った。