読者です 読者をやめる 読者になる 読者になる

GCJ2013 Round 1B

A-Large,B-Large,C-Smallで通過です

A:
Greedyするだけ

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int d[100];
int e[100];
int main(){
	int a;
	scanf("%d",&a);
	int T=0;
	while(a--){
		T++;
		int b,c;scanf("%d%d",&b,&c);
		for(int i=0;i<c;i++){
			scanf("%d",d+i);
		}
		std::sort(d,d+c);
		if(b==1){
			printf("Case #%d: %d\n",T,c);
			continue;
		}
		int now=b;
		for(int i=0;i<c;i++)e[i]=99999999;
		int v=0;
		for(int i=0;i<c;i++){
			if(now>d[i]){
				e[i]=v;
				now+=d[i];
			}else{
				//int r=now-1;
				for(int j=1;;j++){
					now+=now-1;v++;
					if(now>d[i]){
						e[i]=v;
						//now+=r;
						now+=d[i];
						break;
					}
				}
			}//printf("%d ",e[i]);
		}
		int ret=c;
		for(int i=0;i<c;i++){
			ret=min(ret,e[i]+(c-i-1));
		}
		printf("Case #%d: %d\n",T,ret);
	}
}

B:
コンビネーションするだけ 誤差が怖いので三角形

#include<stdio.h>
#include<algorithm>
using namespace std;
int ABS(int a){return max(a,-a);}
double C[4000][4000];
int main(){
	int a;
	scanf("%d",&a);
	int T=0;
	C[0][0]=1;
	C[1][0]=C[1][1]=1.0/2;
	for(int i=2;i<4000;i++){
		C[i][0]=C[i-1][0]/2;
		C[i][i]=C[i-1][i-1]/2;
		for(int j=1;j<i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])/2;
		}
	}
	while(a--){
		T++;
		int b,c,d;
		scanf("%d%d%d",&b,&c,&d);
		int V=0;
		int t=0;
		for(int i=1;;i+=4){
			V+=2;
			t+=i;
			if(t>b){
				V-=2;
				t-=i;
				t=b-t;
				break;
			}
		}
		//printf("%d\n",t);
		if(ABS(c)+d<V){
			printf("Case #%d: 1.0\n",T);
			continue;
		}
		if(ABS(c)+d>V||c==0||d>=t){
			printf("Case #%d: 0.0\n",T);
			continue;
		}
		if(d<t-V){
			printf("Case #%d: 1.00\n",T);
			continue;
		}
		double ret=0;
		//double now=1;
	//	if(t>V){
	//		int A=t-V;
	//		t-=A*2;
	//		d-=A;
	//	}
		for(int i=d+1;i<=t;i++){
			ret+=C[t][i];
		}
		printf("Case #%d: %.8f\n",T,ret);
	}
}

C:
変な定数倍改善?trie使わないと間に合わないのかこれ

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long t[521196];
char str[4001];
int dp[4001][5];
int main(){
	freopen("garbled_email_dictionary.txt","r",stdin);
	for(int i=0;i<521196;i++){
		scanf("%s",str);
		for(int j=0;str[j];j++){
			t[i]<<=5;
			t[i]+=str[j]-'a'+1;
		}
	}
	std::sort(t,t+521196);
	freopen("in.txt","r",stdin);
	int a;
	scanf("%d",&a);
	for(int T=1;T<=a;T++){
		scanf("%s",str);
		int n=strlen(str);
		for(int i=0;i<4001;i++)
			for(int j=0;j<5;j++)
				dp[i][j]=99999999;
		dp[0][0]=0;
		for(int i=0;i<n;i++){
		//	printf("\n");
			for(int j=0;j<5;j++){
		//		printf("%d ",dp[i][j]);
				if(dp[i][j]==99999999)continue;
				for(int k=j;k<10;k++){
					for(int l=k+5;l<10;l++){
						for(char p='a';p<='z';p++){
							for(char q='a';q<='z';q++){
								long long val=0;
								int count=2;
								for(int r=0;r<10&&i+r<n;r++){
									char V=str[i+r];
									
									if(r==k){V=p;}
									if(r==l){V=q;}
									val<<=5;
									val+=V-'a'+1;
									if(binary_search(t,t+521196,val)){
								//		printf("%lld\n",val);
										dp[i+r+1][min(4,l-r+4)]=min(dp[i+r+1][min(4,l-r+4)],dp[i][j]+count);
									}
								}
							}
						}
					}
				}
				for(int k=j;k<10;k++){
					for(char p='a';p<='z';p++){
						long long val=0;
						int count=1;
						for(int r=0;r<10&&i+r<n;r++){
							char V=str[i+r];
							
							if(r==k){V=p;}
							val<<=5;
							val+=V-'a'+1;
							if(binary_search(t,t+521196,val)){
						//		printf("%lld\n",val);
								dp[i+r+1][min(4,max(0,k-r+4))]=min(dp[i+r+1][min(4,max(0,k-r+4))],dp[i][j]+count);
							}
						}
					}
				}
				long long val=0;
				//int count=0;
				for(int r=0;r<10&&i+r<n;r++){
					char V=str[i+r];
					val<<=5;
					val+=V-'a'+1;
					if(binary_search(t,t+521196,val)){
				//		printf("%lld\n",val);
						dp[i+r+1][max(0,j-r)]=min(dp[i+r+1][max(0,j-r)],dp[i][j]);
					}
				}
			}
		}
		int ret=999999999;
		for(int i=0;i<5;i++)ret=min(ret,dp[n][i]);
		if(ret==999999999)ret=1;
		printf("Case #%d: %d\n",T,ret);
	}
}

76pts 155th
GCJは実装量が多いしなぜかWA量産するので苦手…