AtCoder ARC #037 : A - 全優、B - バウムテスト

昨晩からSRM→VK Cup→GCJ→ARCと出てますが、GCJとARCが好調だったので気持ちよく寝られそうです。
http://arc037.contest.atcoder.jp/tasks/arc037_a
http://arc037.contest.atcoder.jp/tasks/arc037_b

A - 全優

現在N科目の試験でそれぞれM[i]点が取れる見込みである。
ある科目を1分勉強すると、その科目の試験が1点多く取れる。
全科目優(80点以上)を取るのに必要な最小勉強時間を求めよ。

max(80-M[i],0)の総和を答えればよい。

int N;
int M[30];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>M[i];
	int ret=0;
	FOR(i,N) ret += max(80-M[i],0);
	cout<<ret<<endl;
}

B - バウムテスト

N頂点M辺のグラフが与えられる。
木を成す連結成分の数を求めよ。

個々の連結成分について辺の数をカウントしても良いが、自分はUnion-Findで行った。
辺を順に処理し、既に連結成分になっている点が出た場合、その連結成分群は以後木ではなくなる。

以下のコードはUFで演算子のオーバーロードをしているので、そのままだと分かりにくいです。
角括弧がfind、丸括弧がunion。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1100> uf;

int NG[1010];
int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(uf[x]==uf[y]) NG[uf[x]]=1;
		else uf(x,y);
	}
	
	FOR(i,N) if(NG[i]) NG[uf[i]]=1;
	int ret=0;
	FOR(i,N) if(uf[i]==i && NG[i]==0) ret++;
	cout<<ret<<endl;
	
}

まとめ

A,BとFirst Answer取れたので良かったです。
AはNのサイズを見て一瞬BitDPかと思ったけど、25は5日×5時間の時間割を想定したものかな。