tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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);
	}
}