天下一プログラマーコンテスト2016 予選A
14位だけどqualifiedの中では10位以内っぽいのでギリギリセーフだった.
A:fizzbuzz
B:できるだけ上に回したほうがいいのでminにあわせる 簡単で綺麗なDPですき.
C:文字列同士を見てはじめに異なる文字しか関係ないのでそこで文字の情報にしてaよりbがはやい みたいな条件を全部持つ あとは取れるやつから貪欲に取るのでOK.(topological順序を求めるアルゴリズムにおいて,次数が0⇔取って良い なのでgreedyでいける)
D:無限に広ければ適当なdfsで根に近い方の辺の長さをクソでかくすれば出来る. あとは座標圧縮すればOK. 基本的に座標圧縮って補助的に使われるアルゴリズムだと認識していたので,こういう使い方ができるのはじめて知って面白いなあって思った.良問だと思う(さすがchokudai(作問者)).
あと普通にdfsで行か列を挿入していく方法があって,こっちは普通だけど思いつかなかったなあ(挿入順がpreorderなので,いつも(postorder)と気持ちが違って難しい)
E:まずN頂点のグラフに辺をはったと思うと,そこでの連結成分ごとに考えれば良い. 無限グラフ上で適当な頂点からdfsをする.同じ行(つまりmodNで等しい)点についたら,その周期でその連結成分(N頂点の方の)は連結になる.これを全サイクルでやればいいが,サイクル基底的な話からこれは適当なdfsで見た全ての周期のgcdを取れば良い.
コンテスト中は明示的にはサイクル基底みたいなの考えてなくて(同じことはしてたけど),無限グラフ上での連結成分(ただし,同じ行の頂点は一つしか現れない)を一個取ってくると,与えられた辺たちで横に何個ずれた連結成分を取ってるかわかるから,それのgcdをとればOK と思った.
N頂点グラフに落とせないのはダメ.
D:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} int N; vector<int> G[26]; int xs[26],ys[26]; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dfs(int v,int p,int x,int y,int dep,int di){ xs[v]=x,ys[v]=y; int d=1<<(28-dep); int ndi=0; for(int u:G[v]) if(u!=p){ if((ndi+2)%4==di) ndi++; dfs(u,v,x+dx[ndi]*d,y+dy[ndi]*d,dep+1,ndi); ndi++; } } int main(){ cin>>N; rep(i,N-1){ char a,b; cin>>a>>b; G[a-'A'].pb(b-'A'); G[b-'A'].pb(a-'A'); } dfs(0,-1,0,0,0,-1); vector<int> X,Y; rep(i,N) X.pb(xs[i]),Y.pb(ys[i]); sort(all(X));sort(all(Y)); X.erase(unique(X.begin(),X.end()),X.end());Y.erase(unique(Y.begin(),Y.end()),Y.end()); rep(i,N) xs[i]=lower_bound(all(X),xs[i])-X.begin(),ys[i]=lower_bound(all(Y),ys[i])-Y.begin(); rep(i,N) xs[i]*=2,ys[i]*=2; int H=X.size()*2-1,W=Y.size()*2-1; vector<string> ans(H,string(W,'.')); rep(i,N) ans[xs[i]][ys[i]]='A'+i; rep(v,N) for(int u:G[v]) if(v<u){ if(xs[v]==xs[u]){ int ya=ys[v],yb=ys[u]; if(ya>yb) swap(ya,yb); for(int y=ya+1;y<yb;y++) ans[xs[v]][y]='-'; }else if(ys[v]==ys[u]){ int xa=xs[v],xb=xs[u]; if(xa>xb) swap(xa,xb); for(int x=xa+1;x<xb;x++) ans[x][ys[v]]='|'; }else{ assert(0); } } cout<<H<<" "<<W<<endl; rep(i,H) cout<<ans[i]<<endl; }
E:発想がunionfindからだったのでunionfindを使っている
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} struct unionfind{ int par[100000]; int d[100000]; void init(int n) { rep(i,n) par[i]=i,d[i]=0; } int find(int x){ if(x==par[x]) return x; int r=find(par[x]); d[x]+=d[par[x]]; return par[x]=r; } void unite(int x,int y,int z){ //w[x]-w[y]=z int rx=find(x),ry=find(y); if(rx==ry) return; d[ry]=d[x]-d[y]-z; par[ry]=rx; } int diff(int x,int y){ //w[x]-w[y]=? find(x),find(y); //いる!! return d[x]-d[y]; } bool same(int x,int y) { return find(x)==find(y); } }UF; int gcd(int x,int y){ if(y==0) return abs(x); return gcd(y,x%y); } int N,M,a[100000],b[100000],c[100000]; int main(){ cin>>N>>M; rep(i,M) cin>>a[i]>>b[i]; UF.init(N); rep(i,M){ if(UF.same(a[i],b[i])){ // int d=-UF.diff(a[i],b[i])+1; // show(d); // if(ans==-1) ans=d; // else ans=gcd(ans,d); }else{ UF.unite(a[i],b[i],1); // show(a[i]); // show(b[i]); } } rep(i,N) c[i]=-1; rep(i,M){ if(UF.same(a[i],b[i])){ int d=-UF.diff(a[i],b[i])+1; if(d==0) continue; int id=UF.find(a[i]); if(c[id]==-1) c[id]=abs(d); else c[id]=gcd(c[id],d); } } long long ans=0; rep(i,N) if(UF.find(i)==i){ if(c[i]==-1){ puts("-1"); return 0; } ans+=c[i]; } cout<<ans<<endl; }