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