kmjp's blog

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

AtCoder ARC #032 : A - ホリドッグ、B - 道路工事

ARC032に参加。
久々にDが解けて好順位。
http://arc032.contest.atcoder.jp/tasks/arc032_1
http://arc032.contest.atcoder.jp/tasks/arc032_2

A - ホリドッグ


Nが与えられる。
1~Nの総和が素数かどうか答えよ。

愚直に総和を素因数分解しても良い。
1~Nの総和がN*(N+1)/2であることから、Nが2以上なら必ず合成数になる。
本番このことも気づいたが、すでに素因数分解解法を書き始めていたので使わず。

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll N;
	cin>>N;
	N=N*(N+1)/2;
	
	if(N==1) return _P("BOWWOW\n");
	for(ll A=2;A*A<=N;A++) {
		if(N%A==0) return _P("BOWWOW\n");
	}
	_P("WANWAN\n");
	
}

B - 道路工事

N頂点M無向辺からなるグラフが与えられる。
このグラフを全頂点連結にするには、何本辺を加えればよいか。

Union-Findで連結成分を数えて、連結成分数-1を答えればよい。

class UF {
	public:
	static const int ufmax=100052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	UF uf;
	int N,M;
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		uf.unite(x-1,y-1);
	}
	set<int> S;
	FOR(i,N) S.insert(uf[i]);
	cout<<S.size()-1<<endl;
	
}

まとめ

AでN==1を考慮し忘れて1WA…。