天下一プログラマーコンテスト2015 本戦（オープン） : A - A 問題、B - B 問題

こどふぇす本戦とかこどふぇす上海とか、本戦じゃないオープンで無駄に調子がいい。(強い人がオンサイトでだいぶいないというのもあるけど)
ちょうど自分が実力で解ける範囲を解けきれました。
ちなみにタイトルで（オープン）と断ったのは本戦と問題が違う可能性があるため。
http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_a
http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_b

問題

• 問題B : 無向グラフが与えられる。うち互いに隣接しないK点を求めよ。
• 問題A : 問題Bの入力例と出力例を1つ示せ。

解法

A問題は1頂点でK=1の例を作ればよい。例えば以下。

1 0 1
0

Bは頂点数20以下なので、K個選ぶ選び方を総当たりするだけ。

int V,E,K;
int mat[21][21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>V>>E>>K;
	FOR(i,E) {
		cin>>x>>y;
		mat[x][y]=mat[y][x]=1;
	}
	
	for(int mask=0;mask<1<<V;mask++) if(__builtin_popcount(mask)==K) {
		int ng=0;
		FOR(y,V) FOR(x,y) if(mat[x][y] && (mask&(1<<x))&&(mask&(1<<y))) ng++;
		if(ng) continue;
		FOR(x,V) if(mask&(1<<x)) _P("%d\n",x);
		return;
		
	}
}

まとめ

皆先にAを時に行ったおかげで、BのFAが取れました。
…Aは解の出力を忘れて1WA。しょうもないな。