GCJ2014 Round2
なんだこのセットは…
A:
CFで既出らしい。やるだけ。
#include<stdio.h> #include<algorithm> using namespace std; int c[11000]; int main(){ int T; scanf("%d",&T); for(int t=0;t<T;t++){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d",c+i); } std::sort(c,c+a); int ret=0; int rem=a; while(rem){ ret++; for(int i=0;i<a;i++){ if(~c[i]){ rem--; for(int j=a-1;j>=0;j--){ if(i!=j&&~c[j]&&c[i]+c[j]<=b){ c[j]=-1; rem--; break; } } c[i]=-1; break; } } } printf("Case #%d: %d\n",t+1,ret); } }
B:
JOI合宿で既出。貼るだけ。
#include<stdio.h> #include<algorithm> using namespace std; int bit[131072]; int sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); int ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<131072;a|=a+1)bit[a]+=b; } int b[110000]; pair<int,int> c[110000]; int main(){ int T; scanf("%d",&T); for(int t=0;t<T;t++){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); // for(int i=0;i<131072;i++)bit[i]=0; for(int i=0;i<a;i++)c[i]=make_pair(b[i],i); std::sort(c,c+a); for(int i=0;i<a;i++)add(i,1); int at=0; long long ret=0; for(int i=0;i<a;i++){ while(at<a&&c[at].first==c[i].first){ add(c[at].second,-1); at++; } ret+=min(sum(0,c[i].second),sum(c[i].second,131071)); } printf("Case #%d: %lld\n",t+1,ret); } }
C:
JAGで既出。でも長方形二つの距離を求めるので苦戦しました・・・
#include<stdio.h> #include<queue> #include<algorithm> #include<vector> using namespace std; vector<pair<int,int> > g[5000]; int ijk[5000]; int v[5000]; int x0[5000]; int x1[5000]; int y0[5000]; int y1[5000]; int X[5000]; int Y[5000]; inline int ABS(int a){return max(a,-a);} int main(){ int T; scanf("%d",&T); for(int t=0;t<T;t++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<5000;i++){ g[i].clear(); v[i]=0; ijk[i]=999999999; } for(int i=0;i<c;i++){ scanf("%d%d%d%d",x0+i,y0+i,x1+i,y1+i); x1[i]++;y1[i]++; } for(int i=0;i<c;i++){ X[i*4]=x0[i]; Y[i*4]=y0[i]; X[i*4+1]=x0[i]; Y[i*4+1]=y1[i]; X[i*4+2]=x1[i]; Y[i*4+2]=y0[i]; X[i*4+3]=x1[i]; Y[i*4+3]=y1[i]; } for(int i=0;i<c;i++){ for(int j=i+1;j<c;j++){ int d=999999999; for(int k=0;k<4;k++){ if(X[j*4+k]>=x1[i]){ if(Y[j*4+k]>y1[i])d=min(d,max(ABS(x1[i]-X[j*4+k]),ABS(y1[i]-Y[j*4+k]))); else if(Y[j*4+k]<y0[i])d=min(d,max(ABS(x1[i]-X[j*4+k]),ABS(y0[i]-Y[j*4+k]))); else d=min(d,ABS(x1[i]-X[j*4+k])); }else if(X[j*4+k]<=x0[i]){ if(Y[j*4+k]>y1[i])d=min(d,max(ABS(x0[i]-X[j*4+k]),ABS(y1[i]-Y[j*4+k]))); else if(Y[j*4+k]<y0[i])d=min(d,max(ABS(x0[i]-X[j*4+k]),ABS(y0[i]-Y[j*4+k]))); else d=min(d,ABS(x0[i]-X[j*4+k])); }else{ if(Y[j*4+k]>=y1[i])d=min(d,ABS(y1[i]-Y[j*4+k])); else if(Y[j*4+k]<=y0[i])d=min(d,ABS(y0[i]-Y[j*4+k])); } } for(int k=0;k<4;k++){ if(X[i*4+k]>=x1[j]){ if(Y[i*4+k]>y1[j])d=min(d,max(ABS(x1[j]-X[i*4+k]),ABS(y1[j]-Y[i*4+k]))); else if(Y[i*4+k]<y0[j])d=min(d,max(ABS(x1[j]-X[i*4+k]),ABS(y0[j]-Y[i*4+k]))); else d=min(d,ABS(x1[j]-X[i*4+k])); }else if(X[i*4+k]<=x0[j]){ if(Y[i*4+k]>y1[j])d=min(d,max(ABS(x0[j]-X[i*4+k]),ABS(y1[j]-Y[i*4+k]))); else if(Y[i*4+k]<y0[j])d=min(d,max(ABS(x0[j]-X[i*4+k]),ABS(y0[j]-Y[i*4+k]))); else d=min(d,ABS(x0[j]-X[i*4+k])); }else{ if(Y[i*4+k]>=y1[j])d=min(d,ABS(y1[j]-Y[i*4+k])); else if(Y[i*4+k]<=y0[j])d=min(d,ABS(y0[j]-Y[i*4+k])); } } if(d>1000)continue; g[i].push_back(make_pair(j,d)); g[j].push_back(make_pair(i,d)); } } for(int i=0;i<c;i++){ g[c].push_back(make_pair(i,x0[i])); g[i].push_back(make_pair(c+1,a-x1[i])); } g[c].push_back(make_pair(c+1,a)); priority_queue<pair<int,int> > Q; ijk[c]=0; Q.push(make_pair(0,c)); while(Q.size()){ int at=Q.top().second; int cost=-Q.top().first; Q.pop(); if(v[at])continue; v[at]=1; for(int i=0;i<g[at].size();i++){ if(!v[g[at][i].first]&&ijk[g[at][i].first]>cost+g[at][i].second){ ijk[g[at][i].first]=cost+g[at][i].second; Q.push(make_pair(-ijk[g[at][i].first],g[at][i].first)); } } } // for(int i=0;i<n+2;i++)printf("(%d,%d): %d\n",X[i],Y[i],ijk[i]); printf("Case #%d: %d\n",t+1,ijk[c+1]); } }
D:
Cで時間無限に消えたので満点解法考えてない。
small
#include<stdio.h> #include<algorithm> using namespace std; char str[100][100]; int ret; int num; struct Trie{ int next[26]; Trie(){ for(int i=0;i<26;i++)next[i]=-1; } }; Trie pool[100000]; int use[100]; int m,n; void dfs(int a){ if(a==m){ int val=0; for(int i=0;i<n;i++){ int count=0; int sz=1; pool[0]=Trie(); for(int j=0;j<m;j++){ if(use[j]==i){ count++; int at=0; for(int k=0;str[j][k];k++){ if(~pool[at].next[str[j][k]-'A'])at=pool[at].next[str[j][k]-'A']; else{ pool[at].next[str[j][k]-'A']=sz; at=sz; pool[sz++]=Trie(); } } } } if(count==0)return; val+=sz; } if(ret<val){ ret=val; num=1; }else if(ret==val)num++; return ; } for(int i=0;i<n;i++){ use[a]=i; dfs(a+1); } } int main(){ int T; scanf("%d",&T); for(int t=0;t<T;t++){ scanf("%d%d",&m,&n); for(int i=0;i<m;i++)scanf("%s",str[i]); ret=0; num=0; dfs(0); //for(int i=1;i<=n;i++)num/=i; printf("Case #%d: %d %d\n",t+1,ret,num); } }
Asmall,Alarge,Bsmall,Blarge,Csmall,Clarge,Dsmallで70点、151位でRound3へ…