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量産するので苦手…