3

AtCoderの ABC308-B を解くためのコードをCで書いたのですが、なぜかsample1だけWA (wrong answer) になります。

問題は以下の通りです。

高橋くんは回転寿司で N 皿の料理を食べました。 i 皿目の色は文字列 C[i] で表されます。また、料理の価格は皿の色と対応し、i=1,…,M のそれぞれについて、色が文字列 D[i] の皿の料理は一皿 P[i] 円です。また、D[1],…,D[M] のいずれとも異なる色の皿の料理は一皿 P[0] 円です。高橋くんが食べた料理の価格の合計を求めてください。

sample1の入力データは、

3 2
red green blue
blue red
800 1600 2800

で、正解は 5200 です。

Paiza.ioでsample1のデータを入れて実行すると正しい答えが出ているのですが、なぜAtCoderではWAになるのか、原因が分かりません。

コードは以下の通りです。

なお構造体は、もともと二分木を作るつもりで書き始めたのですが、途中でこの問題の制約なら二重ループを回しても大丈夫だと判断し、一部のメンバや関数は使っていません。

typedef struct {
    int id;
    char key[21];
    int v;
    struct tn *l;
    struct tn *r;
} tn;
void print_tn(tn* tns, int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
void print_ivector(int* a,int n);
int tree_to_pa(tn* f, int* a1, int* a2);
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N1 9
#define N2 2102
#define N 100000002
tn* create_tn(int key);
void insert_tn(int key, tn *node);
tn *root=NULL;
int cnt=0,ar_idx=0;
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("Memory allocation to s1 failed.");
        exit(1);
    }
    fgets(s1,N1,stdin);
    int i=0;
    int n=readint(s1);
    while(*(s1+i)!=32)i++;
    i++;
    int m=readint(s1+i);
//    printf("n=%d m=%d\n",n,m);
    free(s1);
    char* s2=(char*)malloc(sizeof(char)*(21*n+1));
    if(s2==NULL){
        printf("Memory allocation to s2 failed.");
        exit(1);
    }
    fgets(s2,(21*n+1),stdin);
//    printf("s2=%s\n",s2);
    char* s3=(char*)malloc(sizeof(char)*(21*m+1));
    if(s3==NULL){
        printf("Memory allocation to s3 failed.");
        exit(1);
    }
    fgets(s3,(21*m+1),stdin);
//    printf("s3=%s\n",s3);
    char* s4=(char*)malloc(sizeof(char)*(6*m+1));
    if(s4==NULL){
        printf("Memory allocation to s4 failed.");
        exit(1);
    }
    fgets(s4,6*(m+1)+1,stdin);
//    printf("s4=%s\n",s4);
    int* p=(int*)malloc(sizeof(int)*(m+1));
    if (p==NULL){
        printf("memory allocation to p failed.\n");
        exit(1);
    }
    input_iarray(s4,p,m+1,6*m+1);
//    print_ivector(p,m+1);
    free(s4);
    tn* arr=(tn*)malloc(sizeof(tn)*m);
    if (arr==NULL){
        printf("memory allocation to arr failed.\n");
        exit(1);
    }
    int s3_idx=0;
    i=0;
    for(;i<m;i++){
        char* temp=(char*)malloc(sizeof(char)*22);
        if (temp==NULL){
            printf("memory allocation to temp(%d) failed.\n",i);
            exit(1);
        }
        int k=0;
//        printf("s3+s3_idx=%s\n",s3+s3_idx);
        while(*(s3+s3_idx)!=32 && *(s3+s3_idx)!=0 && *(s3+s3_idx)!='\n'){
            *(temp+k)=*(s3+s3_idx); k++; s3_idx++;
        }
//        printf("temp(%d)=%s\n",i,temp);
        ((arr+cnt)->id)=cnt;
        strcpy((arr+cnt)->key,temp);
        ((arr+cnt)->v)=*(p+cnt+1);
        s3_idx++;
        cnt++; 
    }
//    print_tn(arr,m);
    int total=0;
    int s2_idx=0;
    for(i=0;i<n;i++){
        char* temp2=(char*)malloc(sizeof(char)*22);
        if (temp2==NULL){
            printf("memory allocation to temp2(%d) failed.\n",i);
            exit(1);
        }
        int k=0;
//        printf("s2+s2_idx=%s\n",s2+s2_idx);
        while(*(s2+s2_idx)!=32 && *(s2+s2_idx)!=0 && *(s2+s2_idx)!='\n'){
            *(temp2+k)=*(s2+s2_idx); k++; s2_idx++;
        }
        s2_idx++;
//        printf("temp2(%d)=%s\n",i,temp2);
        int flag=0,price=0;
        for(int j=0;j<m;j++){
            if(strcmp(temp2,(arr+j)->key)==0){
                flag=1;
                price=(arr+j)->v;
                break;
            }
        }
        if(flag==1){
//            printf("%s: price=%d\n",temp2,price);
            total+=price;
        }else{
//            printf("%s: price=%d\n",temp2,*p);
            total+=*p;
        }
    }
    printf("%d\n",total);
    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\n");
}
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));
}
void print_tn(tn* tns, int n){
    for(int i=0;i<n;i++){
        printf("----\n");
        printf("id=%d\n",(tns+i)->id);
        printf("key=%s\n",(tns+i)->key);
        printf("price=%d\n",(tns+i)->v);
    }
}
0

1 件の回答 1

7

文字列temptemp2の末尾に'\0'を書き込んでいないことが原因です。

C言語は、文字列の末尾に'\0'が存在する前提で動作します。
'\0'を書き込まなかった場合、メモリ上で文字列の後ろにあるゴミデータまで文字列の一部と認識してしまうため、同じはずの文字列をstrcmpで比較しても、同じと判定されない場合があります。
Paiza.ioでうまくいったのは、たまたま文字列の後ろにあったゴミデータが'\0'だったので、正常に動作しているように見えているだけだと思われます。

それ以外にも、メモリ関連のバグがいくつか存在します。

  • s4向けに確保しているメモリが足りない。malloc(sizeof(char)*(6*m+1))にて6*m+1だけ確保しているが、実際にはfgets(s4,6*(m+1)+1,stdin);にて6*(m+1)+1だけ使用している。
  • s2,s3,p,arr,temp,temp2freeしていない。特にtemp,temp2については、ループで何重にもメモリ確保しているため影響が大きい。

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

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