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のインストールは無理です。
これはパソコンを買い替えるときの課題にして、当面はコードにデバッグ出力を埋め込んで対処します。