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);
}
}