いやあもうホント嬉しい。
10: Boomerang
最初に投げる先の頂点を選んで、行った先からのatan2でソートしてO(N^2 log N)。
1点しか行き先がなくて1*1みたいなので落としやすいので気をつけましょう。
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; const double EPS = 1e-10; const double INF = 1e+10; const double PI = acos(-1); // ライブラリ省略 double th[3100]; Pt p[3100]; int main(){ int T;scanf("%d",&T); for(int t=1;t<=T;t++){ double X,Y; scanf("%lf%lf",&X,&Y); Pt p0=Pt(X,Y); int b,a; scanf("%d%d",&b,&a); for(int i=0;i<a;i++){ double ix,iy; scanf("%lf%lf",&ix,&iy); p[i]=Pt(ix,iy); } p0=p0*Pt(cos(1.0),sin(1.0)); for(int i=0;i<a;i++)p[i]=p[i]*Pt(cos(1.0),sin(1.0)); int ret=0; for(int i=0;i<a;i++){ if((p[i]-p0).ABS()>EPS+b)continue; Pt at=p0+(p[i]-p0)/(p[i]-p0).ABS()*(double)b; int A=0; for(int j=0;j<a;j++){ if((p[j]-p0).ABS()<EPS||(p[j]-at).ABS()<EPS)A++; else if(iSP(p0,p[j],at)==2){ A++; } } int C=0; int B=0; int sz=0; for(int j=0;j<a;j++){ if((at-p[j]).ABS()<EPS){ C++;continue; } th[sz++]=atan2(p[j].y-at.y,p[j].x-at.x); } std::sort(th,th+sz); int now=0; B=C; for(int j=0;j<sz;j++){ if(j==0||th[j]-th[j-1]<EPS)now++; else now=1; B=max(B,C+now); } ret=max(ret,A*B); // printf("%f %f %f %f %d %d\n",at.x,at.y,p[0].x,p[0].y,A,B); } printf("Case #%d: %d\n",t,ret); } }
15: Lunch Scheduling
まあどうせ座標圧縮してからdp[i][j]:時間iまでは大丈夫でそのうちWさんがj回働いたときのJさんが働く回数の最小値、みたいなDPなんだろうなあと思ったけどなかなかオーダー削るのが面白い。
i!=jでA[i]<=A[j]
#include<stdio.h> #include<algorithm> using namespace std; int dp[12100][3100]; int z[12100]; int A[3100]; int B[3100]; int C[3100]; int D[3100]; int pv[3100]; int qv[3100]; pair<int,int>p[3100]; pair<int,int>q[3100]; int main(){ int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); int sz=0; for(int i=0;i<a;i++)pv[i]=0; for(int i=0;i<b;i++)qv[i]=0; z[sz++]=0; z[sz++]=80000000; for(int i=0;i<a;i++){ scanf("%d%d",A+i,B+i); z[sz++]=A[i]; z[sz++]=B[i]; } for(int i=0;i<b;i++){ scanf("%d%d",C+i,D+i); z[sz++]=C[i]; z[sz++]=D[i]; } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i==j)continue; if(A[j]<=A[i]&&B[i]<=B[j])pv[i]=1; } } for(int i=0;i<b;i++){ for(int j=0;j<b;j++){ if(i==j)continue; if(C[j]<=C[i]&&D[i]<=D[j])qv[i]=1; } } std::sort(z,z+sz); int ps=0; int qs=0; for(int i=0;i<a;i++){ if(pv[i])continue; p[ps++]=make_pair(A[i],B[i]); } for(int i=0;i<b;i++){ if(qv[i])continue; q[qs++]=make_pair(C[i],D[i]); } std::sort(p,p+ps); std::sort(q,q+qs); for(int i=0;i<sz+10;i++){ for(int j=0;j<a+10;j++){ dp[i][j]=999999999; } } dp[0][0]=0; for(int i=0;i<sz;i++){ for(int j=0;j<=a;j++){ if(dp[i][j]>9999999)continue; // printf("%d %d: %d\n",z[i],j,dp[i][j]); int at=lower_bound(p,p+ps,make_pair(z[i]+c,0))-p-1; if(at>=0&&z[i]<p[at].second){ int to=lower_bound(z,z+sz,p[at].second)-z; dp[to][j+1]=min(dp[to][j+1],dp[i][j]); } at=lower_bound(p,p+ps,make_pair(z[i],0))-p-1; if(at>=0&&z[i]<p[at].second){ int to=lower_bound(z,z+sz,p[at].second)-z; dp[to][j+1]=min(dp[to][j+1],dp[i][j]); } at=lower_bound(q,q+qs,make_pair(z[i]+c,0))-q-1; if(at>=0&&z[i]<q[at].second){ int to=lower_bound(z,z+sz,q[at].second)-z; dp[to][j]=min(dp[to][j],dp[i][j]+1); } at=lower_bound(q,q+ps,make_pair(z[i],0))-q-1; if(at>=0&&z[i]<q[at].second){ int to=lower_bound(z,z+sz,q[at].second)-z; dp[to][j]=min(dp[to][j],dp[i][j]+1); } } } int ret=999999999; for(int i=0;i<sz;i++) for(int j=0;j<=a;j++){ if(80000000-z[i]<c)ret=min(ret,max(j,dp[i][j])); } if(ret>9999999)printf("Case #%d: Lunchtime\n",t); else printf("Case #%d: %d\n",t,ret); } }
35: Gentrification
(図は入力例5に対応)
こんなグラフ作って流したら通ったんだけどなぜなんですか。
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int D_MAX_V=1100; const int D_v_size=1100; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } int G[510][510]; int UF[510]; int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a; } int sz[510]; vector<int>g[510]; int num[510]; int main(){ int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<510;i++)g[i].clear(); for(int i=0;i<a;i++)UF[i]=-1; for(int i=0;i<a;i++)for(int j=0;j<a;j++) G[i][j]=0; for(int i=0;i<a;i++)G[i][i]=0; for(int i=0;i<b;i++){ int p,q; scanf("%d%d",&p,&q); G[p][q]=1; } for(int k=0;k<a;k++)for(int i=0;i<a;i++)for(int j=0;j<a;j++) G[i][j]|=(G[i][k]&G[k][j]); for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){ if(G[i][j]&&G[j][i])UNION(i,j); } int ind=0; for(int i=0;i<a;i++){ if(UF[i]<0){ num[i]=ind; sz[ind++]=-UF[i]; } } for(int i=0;i<a;i++){ if(UF[i]>=0)num[i]=num[FIND(i)]; } for(int i=0;i<a;i++)for(int j=0;j<a;j++){ if(UF[i]<0&&UF[j]<0&&i!=j){ if(G[i][j])g[num[i]].push_back(num[j]); } } int ss=ind*2; int st=ind*2+1; for(int i=0;i<D_MAX_V;i++){ D_G[i].clear(); D_level[i]=D_iter[i]=0; } for(int i=0;i<ind;i++){ add_edge(ss,i,sz[i]); add_edge(i+ind,st,sz[i]); } for(int i=0;i<ind;i++){ for(int j=0;j<g[i].size();j++)add_edge(i,ind+g[i][j],99999999); } printf("Case #%d: %d\n",t,a-max_flow(ss,st)); } }
40: Fox Rocks
そもそも解けないからあれなんだけど、りんごさんによると結構変なケースがあるらしく一発で通すのは結構難しいらしい。
60pts 2:58:49 (17th)
決勝進出！がんばるぞ！
