0

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

問題:
自然数を要素とする長さnの配列aがある。i=1..mにわたり、i回目に値b[i]を配列aから取り除く。m回目の操作までの間に、取り除くべき数値が配列aからすでに無くなっているか判定せよ。(なくなっていればNo, なくなっていなければYesを出力)

例1の入力例

結果: 正解が出る。

3 2
1 1 3
3 1

例2の入力例

結果: Paiza.ioで試したところ正解が出るもののAtcoderに提出するとTLEになる。

1 1
1000000000
1

例3の入力例

結果: Paiza.ioでもtimeoutになる。その他、不正解になる場合もあります。

5 2
1 2 3 4 5
5 5

TLEになる場合はwhileループが無限ループになっているものと思われますが、値が見つかった場合と連結リストの最後まで来た場合はループを抜けるように処理しており、なぜ無限ループになるのか分かりません。

現状のコード:

typedef struct node{
    struct node *prev;
    struct node *next;
    int v;
} node;
void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#define N1 11
#include<stdio.h>
#include<stdlib.h>
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    fgets(s1,N1,stdin);
    int n=readint(s1);
    int i=0;
    while(*(s1+i)>=48 && *(s1+i)<=57)i++;
    i++;
    int m=readint(s1+i);
    char* s2=(char*)malloc(sizeof(char)*(11*n+1));
    if(s2==NULL){
        printf("memory allocation to s2 failed\n");
        exit(1);
    }
    fgets(s2,(11*n+1),stdin);
    int* a=(int*)malloc(sizeof(int)*n);
    if(a==NULL){
        printf("memory allocation to a failed\n");
        exit(1);
    }
    input_iarray(s2,a,n,(11*n+1));
    free(s2);
    char* s3=(char*)malloc(sizeof(char)*(11*m+1));
    if(s3==NULL){
        printf("memory allocation to s3 failed\n");
        exit(1);
    }
    fgets(s3,(11*m+1),stdin);
    int* b=(int*)malloc(sizeof(int)*m);
    if(b==NULL){
        printf("memory allocation to b failed\n");
        exit(1);
    }
    input_iarray(s3,b,m,(11*m+1));
    free(s3);
    node* nds=(node*)malloc(sizeof(node)*n);
    if(nds==NULL){
        printf("memory allocation to nds failed\n");
        exit(1);
    }
    node *first=nds;
    node *end=(nds+n-1);
    for(int j=0;j<n;j++){
        if(j==0 && j==n-1){
            (nds+j)->v=*a;
        }else if(j==0){
            (nds+j)->prev=NULL;
            (nds+j)->next=(nds+1);
            (nds+j)->v=*a;
        } else if(j==n-1){
            (nds+j)->prev=(nds+n-2);
            (nds+j)->next=NULL;
            (nds+j)->v=*(a+n-1);
        } else {
            (nds+j)->prev=(nds+j-1);
            (nds+j)->next=(nds+j+1);
            (nds+j)->v=*(a+n-1);
        }
    }
/*
    printf("n=%d m=%d\n",n,m);
    print_ivector(a,n);
    print_ivector(b,m);
    struct node* k=first;
    do {
        printf("%d ",k->v);
    }while((k->next)!=NULL);
    printf("\n");
*/
    for(int j=0;j<m;j++){
        int found=0;
        while(1) {
            node *nd=first;
            if ((nd->v)==*(b+j)){
                found=1;
                if(nd->prev==NULL && nd->next==NULL){
                    nd=NULL;
                }
                else if(nd->prev==NULL){
                    first=(nd->next);
                    (nd->next)->prev=NULL;
                }else if(nd->next==NULL){
                    end=(nd->prev);
                    (nd->prev)->next=NULL;
                }else{
                    (nd->prev)->next=(nd->next);
                    (nd->next)->prev=(nd->prev);
                }
                break;
            }
            if(nd==end){
                break;
            }else{
                nd=(nd->next);
            }
        }
        if(found==0){
            printf("No\n");
            exit(0);
        }
    }
    printf("Yes\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になったコードを掲載いたします。
typedef struct node{
    struct node *prev;
    struct node *next;
    int v;
} node;
void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#define N1 11
#include<stdio.h>
#include<stdlib.h>
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    fgets(s1,N1,stdin);
    int n=readint(s1);
    int i=0;
    while(*(s1+i)>=48 && *(s1+i)<=57)i++;
    i++;
    int m=readint(s1+i);
    char* s2=(char*)malloc(sizeof(char)*(11*n+1));
    if(s2==NULL){
        printf("memory allocation to s2 failed\n");
        exit(1);
    }
    fgets(s2,(11*n+1),stdin);
    int* a=(int*)malloc(sizeof(int)*n);
    if(a==NULL){
        printf("memory allocation to a failed\n");
        exit(1);
    }
    input_iarray(s2,a,n,(11*n+1));
    free(s2);
    char* s3=(char*)malloc(sizeof(char)*(11*m+1));
    if(s3==NULL){
        printf("memory allocation to s3 failed\n");
        exit(1);
    }
    fgets(s3,(11*m+1),stdin);
    int* b=(int*)malloc(sizeof(int)*m);
    if(b==NULL){
        printf("memory allocation to b failed\n");
        exit(1);
    }
    input_iarray(s3,b,m,(11*m+1));
    free(s3);
    node* nds=(node*)malloc(sizeof(node)*n);
    if(nds==NULL){
        printf("memory allocation to nds failed\n");
        exit(1);
    }
    node *first=nds;
    node *end=(nds+n-1);
    for(int j=0;j<n;j++){
        if(j==0 && j==n-1){
            nds->prev=NULL;
            nds->next=NULL;
            (nds+j)->v=*a;
        }else if(j==0){
            (nds+j)->prev=NULL;
            (nds+j)->next=(nds+1);
            (nds+j)->v=*a;
        } else if(j==n-1){
            (nds+j)->prev=(nds+n-2);
            (nds+j)->next=NULL;
            (nds+j)->v=*(a+n-1);
        } else {
            (nds+j)->prev=(nds+j-1);
            (nds+j)->next=(nds+j+1);
            (nds+j)->v=*(a+j);
        }
    }
/*
    printf("n=%d m=%d\n",n,m);
    print_ivector(a,n);
    print_ivector(b,m);
    struct node* k=first;
    do {
        printf("%d ",k->v);
    }while((k->next)!=NULL);
    printf("\n");
*/
    for(int j=0;j<m;j++){
        int found=0;
        node *nd=first;
        while(1) {
            if ((nd->v)==*(b+j)){
                found=1;
                if(nd->prev==NULL && nd->next==NULL){
                    if(j==m-1){
                        printf("Yes\n");
                        exit(0);
                    }else{
                        printf("No\n");
                        exit(0);
                    }
                }
                else if(nd->prev==NULL){
                    first=(nd->next);
                    (nd->next)->prev=NULL;
                }else if(nd->next==NULL){
                    end=(nd->prev);
                    (nd->prev)->next=NULL;
                }else{
                    (nd->prev)->next=(nd->next);
                    (nd->next)->prev=(nd->prev);
                }
                break;
            }
            if(nd==end){
                break;
            }else{
                nd=(nd->next);
            }
        }
        if(found==0){
            printf("No\n");
            exit(0);
        }
    }
    printf("Yes\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));
}

Cの実行環境をローカルにインストールするよう助言頂いた件ですが、確かにそうした方がいいと思うのですが、既にハードディスクが満杯に近い私の低スペックなマシンでは、デバッガを備えたようなIDEのインストールは無理です。
これはパソコンを買い替えるときの課題にして、当面はコードにデバッグ出力を埋め込んで対処します。

1 件の回答 1

2

無限ループの原因のみお伝えします。それ以外のバグは自力で対処してください。

    for(int j=0;j<m;j++){
        int found=0;
        while(1) {
            node *nd=first;
            /* ... */
        }
        /* ... */
    }

whileの先頭でnd=firstしているので、whileの先頭に戻るたびに毎回ndが先頭の位置に戻ってしまいます。そのため、探している要素が先頭に無くて、要素数が2つ以上だと、ループが無限に回ることになります。

ndを先頭の位置に戻すのは、whileの前に一回だけで良いはずです。

    for(int j=0;j<m;j++){
        int found=0;
        node *nd=first;
        while(1) {
            /* ... */
        }
        /* ... */
    }

あと、ローカルでC言語のデバッグができる環境を整えることをお勧めします。
Paiza.io や AtCoder では、実行の流れを脳内で追うしかないので、想定外の動作の原因を見つけるのが非常に困難です。
デバッガを使えば、プログラムを好きなところで止めて、変数の内容を見つつ1行単位で処理を進めることができるので、原因の発見が容易になります。

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

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