tozangezan's diary

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

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へ…