Google Code Jam Japan 2011 #3

例の解けないB問題のlarge、集合同士の合併は無いと思っていたのですが計算してみたらどうやらあるらしい。そこで忠実に集合の合併を行うようにコードを修正してみました。とりあえず答えは正しいのですが、どういうときに集合の合併が起きるのかいまだによくわからないです。

------------------------------
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PLD "%ld"
#define PD "%d"


int p[1000001];
int rank[1000001];
char isPrime[1000001];

int root(int x) {
    if (p[x] != x)
        p[x] = root(p[x]);
    return p[x];
}
  
void funion(int a, int b) {
    int aa,bb;
    aa=a,bb=b;

    a = root(a);
    b = root(b);
    //printf("SS a=%d b=%d root(a)=%d root(b)=%d rank[a]=%d ranl[b]=%d\n",aa,bb,a,b,rank[a],rank[b]);

    if (rank[a] < rank[b]){
        p[a] = b;
    }
    else {
        p[b] = a;
        if (rank[a] == rank[b]){
            rank[a]++;
            //if(rank[a]>=2){
            //    printf("kita!\n");
            //}
        }
    }
    //printf("EE a=%d b=%d root(a)=%d root(b)=%d rank[a]=%d ranl[b]=%d\n",aa,bb,a,b,rank[a],rank[b]);
}
  
int main(){
    FILE *fi=NULL,*fo=NULL;
    char buf[1024];

    int i,j,y;
    int caseCnt,caseNum;

    //fi=fopen("test.txt","rt");
    //fi=fopen("B-small-practice.in","rt");
    fi=fopen("B-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-small.txt","wt");
    fo=fopen("result-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    fgets(buf,sizeof(buf),fi);
    sscanf(buf,PD,&caseCnt);

  
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0]=0;
    isPrime[1]=0;
    for (i=2; i<=1000000; i++)
        for (j=2*i; j<=1000000; j+=i)
            isPrime[j] = 0;


    for (caseNum=1; caseNum <= caseCnt; caseNum++) {
            longlong A,B;
            longlong x;
            int P;
            int res;

            fgets(buf,sizeof(buf),fi);
            sscanf(buf,PLLD PLLD PD ,&A,&B,&P);

            for (i=0; i < B - A + 1; i++) {
                p[i] = i;
                rank[i] = 0;
            }
            res = (int)(B - A + 1);
            for (i=P; i<=1000000; i++) {
                if (!isPrime[i]) continue;
                x = A / i * i;
                if (x < A) x += i;
                x -= A;
                for (y=(int)x+i; y < B - A + 1; y += i)
                    if (root((int)x) != root(y)) {
                        res--;
                        funion((int)x, y);
                    }
            }
            printf("Case #" PD ": " PD "\n",caseNum,res);
            fprintf(fo,"Case #" PD ": " PD "\n",caseNum,res);
            //break;
        }

end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);
    return 1;



------------------------------

Google Code Jam Japan 2011 #2

Code Jam の問題がどうしても答えが合わないので別のアルゴリズムでといてみました。
前回は集合を足していく方法で求めたので、今回は集合を引いていく方法で求めて見ました。
やはりGoogleと答えが合わない。

------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PLD "%ld"
#define PD "%d"


char sosu[1000010];
int sosu_list[100000];

char onaji[1000010];

main(){
    FILE *fi=NULL,*fo=NULL;

    char buf[256];
    longlong a,b,p;
   
    int i,j,c;
    int sct,kotae;

    //sosou wo motomeru
    sosu[0]=1;
    sosu[1]=1;
    for(i=2;i<1000003;i++){
        if(sosu[i]==0){
            for(j=i*2;j<1000010;j+=i)sosu[j]=1;
        }
    }

    for(sct=0,i=0;i<1000003;i++)if(sosu[i]==0){
        sosu_list[sct++]=(int)i;
    }

    printf("sosu=%d\n",sct);
    //fi=fopen("test.txt","rt");
    //fi=fopen("B-small-practice.in","rt");
    fi=fopen("B-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-small.txt","wt");
    fo=fopen("result-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    fgets(buf,sizeof(buf),fi);
    sscanf(buf,PD,&c);



    for(i=0;i<c;i++){

        fgets(buf,sizeof(buf),fi);
        sscanf(buf,PLLD PLLD PLLD ,&a,&b,&p);

        kotae=(int)(b-a+1);
        memset(onaji,0,sizeof(onaji));

        // kousoku soinnsuu bunkai
        printf("bunkai\n");
        for(j=0;j<sct;j++){
            longlong t;
            int flag=0,kita=0;
            if((longlong)(sosu_list[j])<p)continue;
            if((longlong)(sosu_list[j])>b)break;

            t=a+sosu_list[j]-1;
            t/=sosu_list[j];
            t*=sosu_list[j];

            //printf(PLLD"\n" ,t);
            while(t<=b){
                int pos=t-a;
                kita=1;
                if(onaji[pos]==0)kotae--;
                else flag=1;
                onaji[pos]=1;
                t+=sosu_list[j];
            }
            if(flag==0 && kita==1)kotae++;
        }

        printf("Case #%d: %d\n",i+1,kotae);
        fprintf(fo,"Case #%d: %d\n",i+1,kotae);
        //break;
    }


end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);

}


------------------------------

Google Code Jam Japan 2011

Google Gode JamJapan 2011  の練習問題を解いてみました。
http://code.google.com/codejam/japan/

A.数珠繋ぎ
B.数の集合
C.遊園地

と三つ問題があります。
僕が思うにBだけ異常に難しい。 しかもBのlargeだけgoogleの解答と僕の解答が合わない。
いろいろチェックしたんだけどなぁ。本当にGoogleあってんの？



A.数珠繋ぎ
------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



main(){
    FILE *fi=NULL,*fo=NULL;
    char buf[256];
    int t=0,n=0,k=0;
    int i,j,l;

    int syuki=0;
    int no=0;


    //fi=fopen("test.in","rt");
    fi=fopen("A-small-practice.in","rt");
    //fi=fopen("A-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    fo=fopen("small-result.txt","wt");
    //fo=fopen("larget-result.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    buf[0]=0;
    fgets(buf,256,fi);
    sscanf(buf,"%d",&t);

   
    for(i=0;i<t;i++){
        fgets(buf,256,fi);
        sscanf(buf,"%d%d",&n,&k);

        no=1<<n;
       
        printf("i=%d n=%d,k=%d\n",i,n,k);
        printf("Case #%d: %s\n",i+1,(k%no)==no-1?"ON":"OFF");
        fprintf(fo,"Case #%d: %s\n",i+1,(k%no)==no-1?"ON":"OFF");
    }

end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);
}
------------------------------


B.数の集合
------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PLD "%ld"
#define PD "%d"


char sosu[1000010];
int sosu_list[1000010];
//char sosu_flag[1000010];

int onaji_list[1000010];
int onaji_ct;

struct st_kazu{
    int sosu[16];
    int ct;
};

struct st_kazu kazu[1000010];


void clear_onaji(){
    onaji_ct=0;
}

void add_onaji(int n){
    int i;
    for(i=0;i<onaji_ct;i++){
        if(onaji_list[i]==n)return;
    }
    onaji_list[i]=n;
    onaji_ct++;
}

main(){
    FILE *fi=NULL,*fo=NULL;

    char buf[256];
    longlong a,b,p;
   
    int i,j,k,l,m,n;
    int sct,c,kaisu,kotae;

    //sosou wo motomeru
    sosu[0]=1;
    sosu[1]=1;
    for(i=2;i<1000003;i++){
        if(sosu[i]==0){
            for(j=i*2;j<1000010;j+=i)sosu[j]=1;
        }
    }

    for(sct=0,i=0;i<1000003;i++)if(sosu[i]==0){
        sosu_list[sct++]=(int)i;
    }

    printf("sosu=%d\n",sct);
    //fi=fopen("test.txt","rt");
    //fi=fopen("B-small-practice.in","rt");
    fi=fopen("B-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-small.txt","wt");
    fo=fopen("result-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    fgets(buf,sizeof(buf),fi);
    sscanf(buf,PD,&c);



    for(i=0;i<c;i++){
        fgets(buf,sizeof(buf),fi);
        sscanf(buf,PLLD PLLD PLLD ,&a,&b,&p);

        kaisu=(int)(b-a+1);
        kotae=0;
        memset(kazu,0,sizeof(kazu));

        // kousoku soinnsuu bunkai
        printf("bunkai\n");
        for(k=0;k<sct;k++){
            longlong t;
            if((longlong)(sosu_list[k])<p)continue;
            if((longlong)(sosu_list[k])>b)break;

            //printf("sosu=%d\n" ,sosu_list[k]);

            t=a+sosu_list[k]-1;
            t/=sosu_list[k];
            t*=sosu_list[k];
            //printf(PLLD"\n" ,t);
            while(t<=b){
                int pos=t-a;
                kazu[pos].sosu[kazu[pos].ct++]=sosu_list[k];
                t+=sosu_list[k];
            }

        }

        printf("check1\n");
        for(j=0;j<kaisu;j++){
            longlong t;
            t=a+j;
           
            //printf(PLLD ": ",t);
            //for(k=0;k<kazu[j].ct;k++){
            //    printf("%d ",kazu[j].sosu[k]);
            //}
            //printf("\n");

            if(kazu[j].ct==0)kotae++;
        }

        printf("check2\n");

        for(j=0;j<sct;j++){
            longlong t;

            if((longlong)(sosu_list[j])<p)continue;
            if((longlong)(sosu_list[j])>b)continue;

            t=a+sosu_list[j]-1;
            t/=sosu_list[j];
            t*=sosu_list[j];


            clear_onaji();
            while(t<=b){
                int k=t-a;
                for(l=0;l<kazu[k].ct;l++){
                    add_onaji(kazu[k].sosu[l]);
                }
                t+=sosu_list[j];
            }

            //printf("sosu %d to onazi \n",sosu_list[j]);
            //for(k=0;k<onaji_ct;k++){
            //    printf("%d ",onaji_list[k]);
            //}
            //printf("\n");

            if(onaji_ct==1)kotae++;
            if(onaji_ct>1){
                int mmiinn;

                mmiinn=onaji_list[0];
                for(k=1;k<onaji_ct;k++){
                    if(mmiinn>onaji_list[k])mmiinn=onaji_list[k];
                }
                if(mmiinn==sosu_list[j]){
                    kotae++;
                }

            }
        }
        printf("Case #%d: %d\n",i+1,kotae);
        fprintf(fo,"Case #%d: %d\n",i+1,kotae);
        //break;
    }


end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);

}


------------------------------


C.遊園地
------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PD "%d"
#define PLD "%ld"


int g[1000];
longlong nn[1000];
int nx[1000];

main(){
    FILE *fi,*fo;
    int t,n,r,k;
    int i,j,l,cc;
    longlong m,c;
    char buf[1000*100];
    char*p;

    //fi=fopen("test.in","rt");
    //fi=fopen("C-small-practice.in","rt");
    fi=fopen("C-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-c-small.txt","wt");
    fo=fopen("result-c-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;

    fgets(buf,sizeof(buf),fi);
    sscanf(buf,"%d",&t);
    for(i=0;i<t;i++){

        m=0;

        fgets(buf,sizeof(buf),fi);
        sscanf(buf,"%d%d%d",&r,&k,&n);
        fgets(buf,sizeof(buf),fi);

        p=buf;
        for(j=0;j<n;j++){
            sscanf(p,"%d",&(g[j]));
            p=strchr(p,' ');
            p++;
        }
   
        for(j=0;j<n;j++){
            c=0;
            for(cc=0;cc<n;cc++){
                if(c+g[(j+cc)%n]>k)break;
                c+=g[(j+cc)%n];
            }
            nn[j]=c;
            nx[j]=(j+cc)%n;
        }
        j=0;
        for(l=0;l<r;l++){
            m+=nn[j];
            j=nx[j];
        }
        printf("Case #" PD ": " PLLD "\n",i+1,m);
        fprintf(fo,"Case #" PD ": " PLLD "\n",i+1,m);
    }


end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);
}


------------------------------