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…。