SCPC2016 2차예선
문제1.
별로 너무 어렵지는 않지만 실행 제한시간이 좀 짧다.
적당한 정수배 고속화를 해서 만점을 얻었다.
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>id[5100]; int X1[5100]; int X2[5100]; int Y1[5100]; int Y2[5100]; pair<pair<int,int>,int> p[5100]; int main(){ setbuf(stdout,NULL); int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int a,b,n; scanf("%d%d%d",&a,&b,&n); for(int i=0;i<=n;i++)id[i].clear(); for(int i=0;i<n;i++){ scanf("%d%d%d%d",X1+i,Y1+i,X2+i,Y2+i); p[i]=make_pair(make_pair(X2[i]-X1[i],Y2[i]-Y1[i]),i); } std::sort(p,p+n); int ret=1; for(int i=0;i<n;i++){ int at=p[i].second; int tmp=0; for(int j=i;j>0;j--){ for(int k=0;k<id[j].size();k++){ int to=id[j][k]; if(X1[at]<=X1[to]&&X2[to]<=X2[at]&&Y1[at]<=Y1[to]&&Y2[to]<=Y2[at]){ tmp=j;break; } } if(tmp)break; } // printf("%d %d\n",at,tmp+1); ret=max(ret,tmp+1); id[tmp+1].push_back(at); } printf("Case #%d\n",t); printf("%d\n",ret); } }
문제2.
straightforward DP.
#include<stdio.h> #include<algorithm> using namespace std; int b[11000]; int c[11000]; int dp[11000]; int main(){ setbuf(stdout,NULL); int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); for(int i=0;i<a;i++)scanf("%d",c+i); for(int i=0;i<=a;i++)dp[i]=-999999999; dp[0]=0; for(int i=0;i<a;i++){ dp[i+1]=max(dp[i+1],dp[i]+b[i]); if(i==0)dp[i+1]=max(dp[i+1],dp[i]+c[i]); if(i<a-1)dp[i+2]=max(dp[i+2],dp[i]+c[i+1]); } printf("Case #%d\n",t); printf("%d\n",dp[a]); } }
문제3.
'구리'는 무슨 뜻입니까?
유명한 O(n log n) 해법으로는 70점만 얻을 수가 없다.
문제4.
해법은 어렵지 않는데, 힘들게 보인다.
문제5.
I thought there'd been some mistakes in the test data. It was fixed a few hours later.
이분검색. 45도 회전하고 greedy로 소포(=물과 빵)를 할당했다.
#include<stdio.h> #include<algorithm> using namespace std; double x[100]; double y[100]; double p[100]; double X[100]; double Y[100]; double zx[3000]; double zy[3000]; double EPS=1e-9; double ABS(double a){return max(a,-a);} int used[100]; int main(){ setbuf(stdout,NULL); 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<a;i++){ scanf("%lf%lf",x+i,y+i); } for(int i=0;i<b;i++){ scanf("%lf",p+i); } std::sort(p,p+b); for(int i=0;i<a;i++){ X[i]=x[i]+y[i]; Y[i]=x[i]-y[i]; } double LX=999999999; double RX=-999999999; double LY=999999999; double RY=-999999999; for(int i=0;i<a;i++){ LX=min(LX,X[i]); RX=max(RX,X[i]); LY=min(LY,Y[i]); RY=max(RY,Y[i]); } // printf("%d %d %d %d\n",LX,RX,LY,RY); double left=-1; double right=11000000; for(int i=0;i<50;i++){ double M=(left+right)/2; int sz=0; for(int i=0;i<a;i++){ zx[sz]=X[i]-M; zy[sz]=Y[i]-M; sz++; zx[sz]=X[i]+M; zy[sz]=Y[i]+M; sz++; for(int j=0;j<b;j++){ if(M+EPS<p[j])continue; zx[sz]=X[i]-M+p[j]; zy[sz]=Y[i]-M+p[j]; sz++; zx[sz]=X[i]+M-p[j]; zy[sz]=Y[i]+M-p[j]; sz++; } } std::sort(zx,zx+sz); std::sort(zy,zy+sz); bool ok=false; for(int i=0;i<sz;i++){ if(ok)break; if(i&&zx[i]-zx[i-1]<EPS)continue; if(zx[i]+EPS<RX-M||zx[i]>EPS+LX+M)continue; for(int j=0;j<sz;j++){ if(ok)break; if(j&&zy[j]-zy[j-1]<EPS)continue; if(zy[j]+EPS<RY-M||zy[j]>EPS+LY+M)continue; bool dame=false; int cnt=0; for(int k=0;k<b;k++)used[k]=0; for(int k=0;k<a;k++){ double rem=M-max(ABS(zx[i]-X[k]),ABS(zy[j]-Y[k])); if(rem<-EPS){dame=true;break;} // printf("%d %d %d %d: %d\n",M,zx[i],zy[j],k,rem); for(int l=b-1;l>=0;l--){ if(!used[l]&&rem+EPS>p[l]){ cnt++; used[l]=1; break; } } } if(cnt==b&&!dame){ ok=true; } } } if(ok)right=M; else left=M; } printf("Case #%d\n",t); printf("%.1f\n",right+EPS); } }