AtCoder ARC #030 : A - 閉路グラフ、B - ツリーグラフ

ARC030に参加。
Cの実装に手間取り微妙な順位に。
http://arc030.contest.atcoder.jp/tasks/arc030_1
http://arc030.contest.atcoder.jp/tasks/arc030_2

A - 閉路グラフ

N個の頂点がある。i個目の頂点と(i+1)%N個目の頂点を結ぶ辺がN本ある。
ここからいくつか頂点（およびその頂点を端点とする辺）を削除し、K個の連結成分を残せるか答えよ。

１個飛びで頂点を消していくと、最大N/2個の連結成分を残すことができる。
よってKがN/2以下かどうかを判定すればよい。

void solve() {
	int i,j,k,l,r,x,y; string s;
	int N,K;
	
	cin>>N>>K;
	if(K<=N/2) _P("YES\n");
	else _P("NO\n");
}

B - ツリーグラフ

N頂点からなる木を成すグラフがある。
各頂点には0または1の値が振られている。
頂点xから初めて、全ての値が1の頂点を1回以上通って元の頂点xに戻る、最小の頂点の移動回数を答えよ。

DFSでサブツリー分の探索に伴う移動回数を累積していけば良い。

int N,X;
int H[110];
vector<int> E[101];

int dfs(int cur,int pre) {
	int r=0,i,x;
	int need=0;
	if(H[cur]) need=2;
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		x=dfs(tar,cur);
		if(x>0) need=2, r += x;
	}
	return r+need;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>H[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	x=dfs(X-1,-1);
	if(x>0) x-=2;
	cout << x << endl;
}

まとめ

ここらへんはまだまだ。