オタク浪人　石策竜喜のブログ　情報棟（南棟）: 配列の判定・操作(2)

先頭から削除、末尾に挿入

ABC278-A

問題概要

要素数nの配列に対し、先頭の要素一つを削除し、末尾に0を一つ追加することを繰り返す。k回の操作後にできた配列を出力せよ。

解答

この問題の制約ならばk回のshift, pushを繰り返しても間に合うのだが、それではあまりにも芸がない気がするので、「先頭のk要素を削除し、末尾に0をk個追加する」ことを考える。

まず書いたのが、次のコード


    n,k=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
a.shift(k)
b=[0]*k
a+=b
puts a.join(" ")

提出してみたら、半分くらいがWA

少し考えてみると、このコードでは、kがnよりも大きい場合に正しい結果が得られないことに気づく。

それで、書き直したのが以下のコード


    n,k=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
unless k>n
    a.shift(k)
    b=[0]*k
    a+=b
else
    a=Array.new(n,0)
end
puts a.join(" ")

これを提出してACになった。

もう一つのやり方としては、先にaの末尾に0がk個ある配列を連結してしまい、あとは配列a自体は変更することなく、そのk+1番目の要素からn要素を出力するというやりかたもある。

そうやってみたのが、以下のコード。


    n,k=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
b=[0]*k
a+=b
a=a[k,n]
puts a.join(" ")

これもACになった。

Cで書いたのが以下。


    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 N 9
#define N2 402
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    if(s==NULL){
        printf("memory allocation to s failed\n");
        exit(1);
    }
    fgets(s,N,stdin);
    int n=readint(s);
    int i=0;
    while(*(s+i)!=32)i++;
    i++;
    int k=readint(s+i);
    free(s);
    char* s2=(char*)malloc(sizeof(char)*N2);
    if(s2==NULL){
        printf("memory allocation to s2 failed\n");
        exit(1);
    }
    fgets(s2,N2,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,N2);
//    print_ivector(a,n);
    int * b=(int*)malloc(sizeof(int)*n);
    if(b==NULL){
        printf("memory allocation to b failed\n");
        exit(1);
    }
    if(k>n)k=n;
    for(int j=0;j<(n-k);j++){
        *(b+j)=*(a+k+j);
    }
    for(int j=0;j<k;j++){
        *(b+(n-k)+j)=0;
    }
    print_ivector(b,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));
}

先頭に元の配列のk番目から(n-k)個の要素をコピーし、残りを0で埋めた配列を出力している。

逆順に出力

ABC284-A

問題概要

n個の文字列が順に与えられるので、これを後から与えられたものから順に出力せよ

解答


    n=gets.to_i
as=[]
n.times do |i|
    s=gets.chomp
    as.push(s)
end
(n-1).downto(0).each do |i| 
    puts as[i]
end

Cでまず書いたのが以下。


    int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 4
#define N2 111
#define N3 12
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    if(s==NULL){
        printf("memory allocation to s failed\n");
        exit(1);
    }
    fgets(s,N,stdin);
    int n=readint(s);
    free(s);
    char* s2=(char*)malloc(sizeof(char)*N2);
    if(s2==NULL){
        printf("memory allocation to s2 failed\n");
        exit(1);
    }
    fgets(s2,N2,stdin);
    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);
        }
        fgets(s3,N3,stdin);
        int j=0;
        while(*(s3+j)!=0){
            *(s2+11*i+j)=*(s3+j);j++;
        }
        *(s2+11*i+j)=0;
    }
    for(int i=n-1;i>=0;i--){
        printf("%s",(s2+11*i));
    }
    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;
}

このコードは、実行すると、例えば

4
2023
Year
New
Happy

という入力例では、出力結果が、

    Happy
    New
    Year

となり、最後の(元の並びでは最初の)文字列が出力されない。

原因がわからず、StackOverflowで質問。

actorbugさんから回答を頂いて分かったのは、fgets(s2,N2,stdin); という一行が余計だということだ。言われてみれば拍子抜けするような当たり前の話で、このs2というメモリ領域は後で一行ずつ取り込む文字列を順に格納するためのものだから、ここでfgetsしてはいけないのだった。前に書いたコードからメモリ確保部分と一緒にコピー&ペーストで引っ張ってきたという問題もあるのだが、つい、文字列用のメモリを確保したら次はfgetsと思い込んでいてその存在を怪しまなかった。

あと、指摘されたのがfgetsのヌルチェックの必要性。前にmallocの戻り値チェックの必要性を指摘されてから、mallocの後にはヌルチェックを入れるようにしていたが、mallocだけでなく、fgetsでも戻り値チェックが必要なのか。

さて、その問題は解決したが、今度は、一部のテストケースで、改行が出力されずWAになるという現象が生じる。というより、ある意味このコードではこうなることが最初の想定で、だから初めは printf("%s\n",(s2+N3*i)); と改行を入れていたのである。だが、そうすると余分な空行が出力されてしまうので、改行文字を加えずに出力するコードに直していたのである。だから、上のコードのように出力の際に改行文字を加えれはこのテストケースについては正しい出力がえられるが、そうすると今度は改行文字なしで改行されていたテストケースで空行が入ってしまうことは明白である。

この現象の意味についてしばらく考えたが、テストケースの入力例のうち、文字列に最初から改行文字が入っているものとそうでないものがあるのではないかと推測し、もし最後の文字(ヌル文字0の前)が改行文字でない場合には文字列に改行文字を加えるようコードを書きなおした。それに伴い、一つの文字列分のメモリも、(文字数の上限10)+(改行文字分2)+(ヌル文字分1)の13個に改める。それでACになったのが以下。


    int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 4
#define N3 13
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    if(s==NULL){
        printf("memory allocation to s failed\n");
        exit(1);
    }
    char *ts=fgets(s,N,stdin);
    if(ts==NULL){
        printf("fgets(s) failed\n");
        exit(1);
    }
    int n=readint(s);
    free(s);
    char* s2=(char*)malloc(sizeof(char)*(N3*n));
    if(s2==NULL){
        printf("memory allocation to s2 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(ts3(i)) failed\n");
            exit(1);
        }
        int j=0;
        while(*(s3+j)!=0){
            *(s2+N3*i+j)=*(s3+j);j++;
        }
        if(*(s3+N3*i+j-1)!='\n'){
            *(s2+N3*i+j)='\n'; j++;    
        }
        *(s2+N3*i+j)=0;
        free(s3);
    }
    for(int i=n-1;i>=0;i--){
        printf("%s",(s2+N3*i));
    }
    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;
}

配列の一部の入れ替え

ABC286-A

問題概要

ある配列のp番目からq番目まで(第一部分)とr番目からs番目まで(第二部分)を入れ替えよ。

解答


    n,p,q,r,s=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
b=[]
idx=0
(p..q).each do |i|
    b[idx]=a[i-1]
    idx+=1
end
idx=r-1
(p..q).each do |i|
    a[i-1]=a[idx]
    idx+=1
end
idx=0
(r..s).each do |i|
    a[i-1]=b[idx]
    idx+=1
end
puts a.join(" ")

swap関数を作る時の要領で、片方の部分の一時保管用の配列を作ってやればよい。

上が本番での提出コード。Cで書いたのが以下。


    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 N 21
#define N2 401
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    char* ts=fgets(s1,N,stdin);
    if(ts==NULL){
        printf("fgets(s1) failed\n");
        exit(1);
    }
    int n=readint(s1);
    int i=0;
    while(*(s1+i)!=32)i++;
    i++;
    int p=readint(s1+i);
    while(*(s1+i)!=32)i++;
    i++;
    int q=readint(s1+i);
    while(*(s1+i)!=32)i++;
    i++;
    int r=readint(s1+i);
    while(*(s1+i)!=32)i++;
    i++;
    int s=readint(s1+i);
    free(s1);
//    printf("n=%d p=%d q=%d r=%d s=%d\n",n,p,q,r,s);
    char* s2=(char*)malloc(sizeof(char)*N2);
    if(s2==NULL){
        printf("memory allocation to s2 failed\n");
        exit(1);
    }
    char* ts2=fgets(s2,N2,stdin);
    if(ts2==NULL){
        printf("fgets(s2) failed\n");
        exit(1);
    }
    int * a=(int*)malloc(sizeof(int)*n);
    if(a==NULL){
        printf("memory allocation to a failed\n");
        exit(1);
    }
    input_iarray(s2,a,n,N2);
//    print_ivector(a,n);
    for(int j=0;j<p-1;j++){
        printf("%d ",*(a+j));
    }
    for(int j=r-1;j<s;j++){
        printf("%d ",*(a+j));
    }
    for(int j=q;j<r-1;j++){
        printf("%d ",*(a+j));
    }
    for(int j=p-1;j<q;j++){
        printf("%d",*(a+j));
        if(j!=n-1)putchar(32);
    }
    for(int j=s;j<n;j++){
        printf("%d",*(a+j));
        if(j!=n-1)putchar(32);
    }
    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));
}

こちらでは、特に出力用の配列を作ることはせず、元の配列の要素を、① 1番目からp-1番目、② r番目からs番目、③ q+1番目からr-1番目、⑤s+1番目からn番目、の順に出力している。

オタク浪人　石策竜喜のブログ　情報棟（南棟）

2022年10月30日日曜日

配列の判定・操作(2)

先頭から削除、末尾に挿入

ABC278-A

問題概要

逆順に出力

ABC284-A

問題概要

解答

配列の一部の入れ替え

ABC286-A

問題概要

解答

0 件のコメント:

コメントを投稿

ブログアーカイブ

オタク浪人 石策竜喜のブログ 情報棟（南棟）

2022年10月30日日曜日

配列の判定・操作(2)

先頭から削除、末尾に挿入

ABC278-A

問題概要

逆順に出力

ABC284-A

問題概要

解答

配列の一部の入れ替え

ABC286-A

問題概要

解答

0 件のコメント:

コメントを投稿

ブログ アーカイブ

オタク浪人　石策竜喜のブログ　情報棟（南棟）

ブログアーカイブ