0

AtCoder Beginners Contest (ABC) 314-Bを解くための問題をCで書きました。

問題

n組のデータが与えられる。各組は一行目が1から37までいずれかの値を取る整数cで、二行目がc個の整数(0から36までのいずれかの値を取る)からなる配列である。最後に整数xが与えられるので、n組のデータのうち、二行目の配列にxを含み、かつ要素数が最も少ないものの番号を(該当するものが複数あれば全て空白区切りで)出力せよ。

その解答として書いたのが以下のコードです。
まず、① n*38のサイズのメモリ ars を取って、与えられたn組の各データを、行の先頭にcを格納し、続く部分に二行目の配列を格納して、残りの部分があればそこを-1で埋めた配列の形で保持し、次に、② xを含み行の最も小さい要素数minを求め、最後に、③ xを含み要素数が min である行番号の配列を作っています。(ansも最初に全部を-1で埋めていますが、出力は-1でない実要素が入った部分のみとしています。)

これに、入力例1のデータを与えると、下記のように正しい出力が得られます。
(問題本来の解答は最後の二行のみで、残りはデバッグ出力です。)

入力例 1:

4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19

出力結果 1:

(begin debug output)
(debug output): loop i=0
3 7 19 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
(debug output): loop i=1
4 4 19 24 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
(debug output): loop i=2
2 26 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
(debug output): loop i=3
3 19 31 24 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
(end debug output)
(debug output): x=19
(debug output): min=3
2
1 4

一方、以下の入力(テストケース名 000.txt)を与えると、この場合たまたま解答は正解と一致しているのですが、本来36であるはずのxが0になっています。

入力例 2:

1
37
21 36 33 9 28 1 0 34 3 25 13 31 20 2 22 4 11 15 7 18 6 32 5 14 26 35 12 10 24 17 23 29 19 30 8 27 16
36

出力結果 2:

(begin debug output)
(debug output): loop i=0
37 21 36 33 9 28 1 0 34 3 25 13 31 20 2 22 4 11 15 7 18 6 32 5 14 26 35 12 10 24 17 23 29 19 30 8 27 16 
(end debug output)
(debug output): x=0
(debug output): min=37
1
1

また、上のテストケースを少し書き換えて実行すると、2組目のデータが正しく読み込まれていないうえ、xの読み込みのfgetsが失敗しています。

1組目のデータの読み込みの最後のところで何か変なことが起っているのではないかと思いまずが、それが何なのかわかません。

入力例 2':

2
37
21 36 33 9 28 1 0 34 3 25 13 31 20 2 22 4 11 15 7 18 6 32 5 14 26 35 12 10 24 17 23 29 19 30 8 27 16
1
36
36

出力結果 2':

(begin debug output)
(debug output): loop i=0
37 21 36 33 9 28 1 0 34 3 25 13 31 20 2 22 4 11 15 7 18 6 32 5 14 26 35 12 10 24 17 23 29 19 30 8 27 16 
(debug output): loop i=1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
(end debug output)
fgets(s5) failed

ソースコード:

void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 5
#define N2 37
#define N3 4
#define N4 102
int main(void){
    char *s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    char *ts1=fgets(s1,N1,stdin);
    if(ts1==NULL){
        printf("fgets(s1) failed\n");
        exit(1);
    }
    int n=readint(s1);
    free(s1);
//    printf("n=%d\n",n);
    int *ars=(int*)malloc(sizeof(int)*n*(N2+1));
    if(ars==NULL){
        printf("memory allocation to ars failed\n");
        exit(1);
    }
    for(int i=0;i<n;i++){
        char *s3=(char*)malloc(sizeof(char)*N3);
        if(s3==NULL){
            printf("memory allocation to s3(%d) failed\n",i);
            exit(1);
        }
        char *ts3=fgets(s3,N3,stdin);
        if(ts3==NULL){
            printf("fgets(s3(%d)) failed\n",i);
            exit(1);
        }
        int c=readint(s3);
        free(s3);
        char *s4=(char*)malloc(sizeof(char)*N4);
        if(s3==NULL){
            printf("memory allocation to s4(%d) failed\n",i);
            exit(1);
        }
        char *ts4=fgets(s4,N4,stdin);
        if(ts4==NULL){
            printf("fgets(s4(%d)) failed\n",i);
            exit(1);
        }
        int *a=(int*)malloc(sizeof(int)*n);
        if(a==NULL){
            printf("memory allocation to a(%d) failed\n",i);
            exit(1);
        }
        input_iarray(s4,a,c,N4);
//        printf("%d\n",c);
//        print_ivector(a,c);
        free(s4);
        *(ars+i*(N2+1))=c;
        for(int j=1;j<=c;j++){
            *(ars+i*(N2+1)+j)=*(a+j-1);
        }
        for(int j=c+1;j<(N2+1);j++){
            *(ars+i*(N2+1)+j)=-1;
        }
        free(a);

    }
    printf("(begin debug output)\n");
    for(int i=0;i<n;i++){
        printf("(debug output): loop i=%d\n",i);
        for(int j=0;j<(N2+1);j++){
            printf("%d ",*(ars+i*(N2+1)+j));
        }
        printf("\n");
    }
    printf("(end debug output)\n");
    char *s5=(char*)malloc(sizeof(char)*N3);
    if(s5==NULL){
        printf("memory allocation to s5 failed\n");
        exit(1);
    }
    char *ts5=fgets(s5,N3,stdin);
    if(ts5==NULL){
        printf("fgets(s5) failed\n");
        exit(1);
    }
    int x=readint(s5);
    free(s5);
    printf("(debug output): ");
    printf("x=%d\n",x);
    int min=N2,ans_idx=0;
    int* ans=(int*)malloc(sizeof(int)*n);
    int* flgs=(int*)malloc(sizeof(int)*n);
    if(ans==NULL){
        printf("memory allocation to ans failed\n");
        exit(1);
    }
    if(flgs==NULL){
        printf("memory allocation to flgs failed\n");
        exit(1);
    }
    for(int i=0;i<n;i++){
        *(ans+i)=-1;
        *(flgs+i)=0;
    }
    for(int i=0;i<n;i++){
        int flag=0;
        for(int j=1;j<*(ars+i*(N2+1));j++){
            if(*(ars+i*(N2+1)+j)==x){
                flag=1;
//                printf("%d was found in line (%d)\n",*(ars+i*(N2+1)+j),i);
                break;
            }
        }
        if(flag==1 && *(ars+i*(N2+1))<min){
            min=*(ars+i*(N2+1));
//            printf("min is changed to %d\n",min);
        }
        if(flag==1){
            *(flgs+i)=1;
        }
    }
    printf("(debug output): ");
    printf("min=%d\n",min);
    for(int i=0;i<n;i++){
        if(*(flgs+i)==1 && *(ars+i*(N2+1))==min){
            *(ans+ans_idx)=i+1; ans_idx++;
//            printf("i=%d\n");
        }
    }
    printf("%d\n",ans_idx);
    ans_idx=0;
    while(ans_idx<n && *(ans+ans_idx)!=-1){
        printf("%d",*(ans+ans_idx));
        if(ans_idx<n-1 && *(ans+ans_idx+1)!=-1)putchar(32);
        ans_idx++;
    }
    printf("\n");    
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
void input_iarray(char* s,int* a,int n,int imax){
    int aidx=0,i=0; 
    while(*(s+i)!=0 && i<imax){
        if (*(s+i)<48 || *(s+i)>57){i++;}
        else{
            int bidx=i;
            while(*(s+i)>=48 && *(s+i)<=57){
                i++;
            }
            int t=0;
            for(int j=bidx;j<i;j++){
                t*=10;
                t+=*(s+j)-48;
            }
        *(a+aidx++)=t;
        }
    }
    if (aidx!=n)printf("n!=aidx aidx=%d\n",aidx);
}
void print_ivector(int* a,int n){
    for(int i=0;i<n-1;i++){
        printf("%d ",*(a+i));
    }
    printf("%d\n",*(a+n-1));
}

指摘いただいた点を直したほか、あと一ヵ所間違いがあったのでそこも直してACになったコードを以下に掲載いたします。

void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 5
#define N2 37
#define N3 4
#define N4 102
int main(void){
    char *s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    char *ts1=fgets(s1,N1,stdin);
    if(ts1==NULL){
        printf("fgets(s1) failed\n");
        exit(1);
    }
    int n=readint(s1);
    free(s1);
//    printf("n=%d\n",n);
    int *ars=(int*)malloc(sizeof(int)*n*(N2+1));
    if(ars==NULL){
        printf("memory allocation to ars failed\n");
        exit(1);
    }
    for(int i=0;i<n;i++){
        char *s3=(char*)malloc(sizeof(char)*N3);
        if(s3==NULL){
            printf("memory allocation to s3(%d) failed\n",i);
            exit(1);
        }
        char *ts3=fgets(s3,N3,stdin);
        if(ts3==NULL){
            printf("fgets(s3(%d)) failed\n",i);
            exit(1);
        }
        int c=readint(s3);
        free(s3);
        char *s4=(char*)malloc(sizeof(char)*N4);
        if(s3==NULL){
            printf("memory allocation to s4(%d) failed\n",i);
            exit(1);
        }
        char *ts4=fgets(s4,N4,stdin);
        if(ts4==NULL){
            printf("fgets(s4(%d)) failed\n",i);
            exit(1);
        }
        int *a=(int*)malloc(sizeof(int)*c);
        if(a==NULL){
            printf("memory allocation to a(%d) failed\n",i);
            exit(1);
        }
        input_iarray(s4,a,c,N4);
//        printf("%d\n",c);
//        print_ivector(a,c);
        free(s4);
        *(ars+i*(N2+1))=c;
        for(int j=1;j<=c;j++){
            *(ars+i*(N2+1)+j)=*(a+j-1);
        }
        for(int j=c+1;j<(N2+1);j++){
            *(ars+i*(N2+1)+j)=-1;
        }
        free(a);

    }
/*    printf("(begin debug output)\n");
    for(int i=0;i<n;i++){
        printf("(debug output): loop i=%d\n",i);
        for(int j=0;j<(N2+1);j++){
            printf("%d ",*(ars+i*(N2+1)+j));
        }
        printf("\n");
    }
    printf("(end debug output)\n");*/
    char *s5=(char*)malloc(sizeof(char)*N3);
    if(s5==NULL){
        printf("memory allocation to s5 failed\n");
        exit(1);
    }
    char *ts5=fgets(s5,N3,stdin);
    if(ts5==NULL){
        printf("fgets(s5) failed\n");
        exit(1);
    }
    int x=readint(s5);
    free(s5);
    //printf("(debug output): ");
    //printf("x=%d\n",x);
    int min=N2,ans_idx=0;
    int* ans=(int*)malloc(sizeof(int)*n);
    int* flgs=(int*)malloc(sizeof(int)*n);
    if(ans==NULL){
        printf("memory allocation to ans failed\n");
        exit(1);
    }
    if(flgs==NULL){
        printf("memory allocation to flgs failed\n");
        exit(1);
    }
    for(int i=0;i<n;i++){
        *(ans+i)=-1;
        *(flgs+i)=0;
    }
    for(int i=0;i<n;i++){
        int flag=0;
        for(int j=1;j<=*(ars+i*(N2+1));j++){
            if(*(ars+i*(N2+1)+j)==x){
                flag=1;
//                printf("%d was found in line (%d), from left (%d)\n",*(ars+i*(N2+1)+j),i+1,j);
                break;
            }
        }
        if(flag==1 && *(ars+i*(N2+1))<min){
            min=*(ars+i*(N2+1));
//            printf("min is changed to %d\n",min);
        }
        if(flag==1){
            *(flgs+i)=1;
        }
    }
//    printf("(debug output): ");
//    printf("min=%d\n",min);
    for(int i=0;i<n;i++){
        if(*(flgs+i)==1 && *(ars+i*(N2+1))==min){
            *(ans+ans_idx)=i+1; ans_idx++;
//            printf("i=%d\n");
        }
    }
    printf("%d\n",ans_idx);
    ans_idx=0;
    while(ans_idx<n && *(ans+ans_idx)!=-1){
        printf("%d",*(ans+ans_idx));
        if(ans_idx<n-1 && *(ans+ans_idx+1)!=-1)putchar(32);
        ans_idx++;
    }
    printf("\n");    
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
void input_iarray(char* s,int* a,int n,int imax){
    int aidx=0,i=0; 
    while(*(s+i)!=0 && i<imax){
        if (*(s+i)<48 || *(s+i)>57){i++;}
        else{
            int bidx=i;
            while(*(s+i)>=48 && *(s+i)<=57){
                i++;
            }
            int t=0;
            for(int j=bidx;j<i;j++){
                t*=10;
                t+=*(s+j)-48;
            }
        *(a+aidx++)=t;
        }
    }
    if (aidx!=n)printf("n!=aidx aidx=%d\n",aidx);
}
void print_ivector(int* a,int n){
    for(int i=0;i<n-1;i++){
        printf("%d ",*(a+i));
    }
    printf("%d\n",*(a+n-1));
}
1
  • 1
    「説明の文章」と「コードや出力結果」は分離して書いてもらった方が見やすいです。編集後の本文を参考にしてもらえればと思います。
    – cubick
    Commented 2月15日 1:27

1 件の回答 1

2
        int *a=(int*)malloc(sizeof(int)*n);
        if(a==NULL){
            printf("memory allocation to a(%d) failed\n",i);
            exit(1);
        }
        input_iarray(s4,a,c,N4);

a向けにintn個確保していますが、input_iarrayintc個書き込んでいます。
問題のある入力例だと、nが1で、cが37なので、メモリが溢れます。

メモリ関連のバグを一切出さない自信が無いなら、ローカルデバッグ環境無しでC言語を使うのは無謀です。
C言語は、間違ったことをやっても平気で処理を続けて、関係ないところでエラーが発生するので、ローカルデバッグ環境無しで学ぶのは本当に無理があります。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。