環状配列上で隣接する数か
ABC240-A
問題概要
1から10までの数がこの順で並ぶ環状配列において、aとbが隣接しているか判定せよ。(a<b)
解答
a,b=gets.chomp.split(" ").map(&:to_i)
if a==1 and b==10 then
puts "Yes"
elsif
(b+10-a)%10==1
puts "Yes"
else
puts "No"
end
上が本番で提出したコード。しかし、なぜ単純にb-aとするのではなく、(b+10-a)%10==1としたのか、今となってはわからない。下がCで書いたコードだが、こちらは単にb-aとして問題なく動いている。
#include<stdio.h>
int main(void){
int a,b;
scanf("%d %d\n",&a,&b);
if ((a==1 && b==10) || b-a==1){
printf("Yes\n");
}else{
printf("No\n");
}
return 0;
}
連鎖移動
ABC241-A
問題概要
0..9の数字を要素とする配列aがある。はじめのインデックスは0。「現在のインデックスに対応する値を新しいインデックスとする。」ことを3回繰り返す。最終時点での値を求めよ。
解答
a=gets.chomp.split(" ").map(&:to_i)
idx=0
3.times do
idx=a[idx]
end
puts idx
上が本番で提出したコード。
Cでやったのが以下。
#include<stdio.h>
#include<stdlib.h>
#define N 10
#define T 3
int main(void){
int* a=(int*)malloc(sizeof(int)*N);
for(int i=0;i<N;i++){
scanf("%d",a+i);
}
int idx=0;
for(int i=0;i<T;i++){
idx=*(a+idx);
}
printf("%d\n",idx);
return 0;
}
ABC241-B
問題概要
自然数を要素とする長さnの配列aがある。i=1..mにわたり、i回目に値b[i]を配列aから取り除く。m回目の操作までの間に、取り除くべき数値が配列aからすでに無くなっているか判定せよ。(なくなっていればNo, なくなっていなければYesを出力)
解答
def bsearch(a,x)
n=a.size
l=0
r=n
while r-l>0.9 do
m=(r+l)/2
# puts "l=#{l} r=#{r}"
if a[m]<x then
l=m+1
else
if a[m]==x && (m==0 || a[m-1]<x) then
return m
else
r=m
end
end
end
return -1
end
n,m=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
b=gets.chomp.split(" ").map(&:to_i)
a.sort!
m.times do |i|
t=bsearch(a,b[i])
if t==-1
puts "No"
exit
else
a.delete_at(t)
end
end
puts "Yes"
m回にわたり、配列aにb[i]が含まれているかどうかを二分探索で調べ、含まれていればその値をaから取り除くことを繰り返している。
上が本番での提出コード。Cで書いたのが以下だが、まずTLE等になった次のコードを掲げる。
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になるものの、他はTLEになったりWAになったりする。TLEと言っても、この問題の制約ではaもbも要素数は最大で1000個だから、計算量の問題ではない。どうも、whileループが無限ループになっているようだ。そこで、Stackoverflowで質問した。
actorbugさんから回答を頂いたが、やはり、whileループが無限ループになっていて、node *nd=first;という一文をwhileループの中においてしまっていたため、毎回先頭に戻ることになってしまっていたのだった。
これに加えて、他にも見つけた誤りを修正したのが次のコード。これは、一つだけREになった。
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+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){
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));
}
その、REになるテストケースを見ると、
1 1 1 1という内容だ。
Paiza.ioにこのデータを入れてみると、Yesという正解になるのだが、AtCoderのコードテストで試してみると、終了コード139と、やはりエラーになるようだ。n=1,m=1というのは入力例2と同じ。違うのは、入力例2ではaとbのそれぞれの唯一の要素は異なる値だが、こちらではそれが同じ値だということ。
nd->prev==NULL && nd->next==NULL の場合に
という微修正を加えてみたが、結果は同じ。一度諦めてから翌日もう一度コードを見直してみて、最初に配列から連結リストにデータを入れなおした際、データ数が1個の場合にその前後をNULLにする処理をしていなかったことに気づく。しかし、これでよく nd->next==NULL を停止条件にしている入力確認のためのコードでエラーにならなかったなと思う。この確認はPaizaでしていて、コード全体もPaizaでは成功しているから、Paizaでは自動的に何も入れてないところはNULLになっているということか。
if(j==m-1){
printf("Yes\n");
exit(0);
}else{
printf("No\n");
exit(0);
}
最終的に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));
}
配列に含まれない最小の非負整数
ABC245-B
問題概要
非負整数を要素とする長さnの配列aが与えられる。aに含まれない最小の非負整数を求めよ。
解答
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
a.sort!
b=(0..n).to_a
c=b-a
puts c.min
上が本番で提出したコード。見直してみると、aをソートしている意味がないし、bは0からaの全範囲の一つ上までを含む配列を作ればよいので、制約によりa[i]の最大値が2000であることを考え、b=(0..2000+1).to_aとするか、或いはb=(0..a.max+1).to_a としてもよかった。
やり直したのが以下のコード。配列の引き算を使っていない分、こちらのほうがいいかと思う。
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
ref=Array.new(2002,false)
n.times do |i|
ref[a[i]]=true
end
(0..2001).each do |i|
if ref[i]==false
puts i
exit
end
end
Cで書いたのが以下。
void qsort_1(int* a, int l, int r);
void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#define N 10002
#define N1 6
#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);
char* s3=(char*)malloc(sizeof(char)*N);
fgets(s3,N,stdin);
int * a=(int*)malloc(sizeof(int)*n);
input_iarray(s3,a,n,N);
// print_ivector(a,n);
qsort_1(a,0,n-1);
// print_ivector(a,n);
int ans=0;
int i=0;
do {
if(a[i]==ans){
ans++;
if(i==(n-1))break;
else{
i++;
while(i<n-1 && a[i]<ans)i++;
}
}
else break;
}while(i<n);
printf("%d\n",ans);
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 qsort_1(int* a, int l, int r){
int left, right, d, temp;
if (l>=r)return;
d=*(a+l);
for(left=l,right=r;left<right;){
while(left<=right && a[left]<=d)left++;
while(left<=right && a[right]>d)right--;
if(left<right){
temp=a[left];
a[left]=a[right];
a[right]=temp;
}
}
temp=a[l];
a[l]=a[right];
a[right]=temp;
qsort_1(a,l,right-1);
qsort_1(a,right+1,r);
}
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));
}
まず配列をソートし(今回は実際に必要なソート。クイックソートを(ほぼ本の引き写しだけだけど)初めて実装した)、答えの候補を最小の0から始め、1ずつインクリメントしながら、それが配列の中に含まれなくなる所を探している。配列の最小値と答えの候補が一致した時には答えの候補の値をインクリメントするとともに配列のインデックスもインクリメントするが、配列には同じ値が複数並んでいる可能性があるので、もしインクリメント後のインデックスに対応する値が答えの候補よりも小さければ、配列の値が答えの候補の値以上になるまでインデックスをインクリメントしている。
分類無し
ABC247-B
問題概要
それぞれ2個の文字列からなるn組の文字列の組が与えられる。各組の第一要素と第二要素のいずれか一方のみを選ぶとき選ばれた全てが、他の各組の第1または第2要素と一致しないようにすることができるか。
解答
n=gets.to_i
a=[]
n.times do |i|
a[i]=gets.chomp.split(" ")
end
flag=true
n.times do |i|
b=a.dup
b.delete_at(i)
b.flatten!
if b.include?(a[i][0]) && b.include?(a[i][1])
flag=false
end
end
if flag==true
puts "Yes"
else
puts "No"
end
上が本番で提出したコードなのだが、自分で半年余りの後に読み返してみて、何をやっているのかしばらく分からなかった。
これは、各組について、その第一要素と第二要素のいずれかが、他の組の中で出現する文字列と一致していなければ、その組は他の組と被らない文字列を持つことができることを使っている。そこで、各組ごとに、全文字列からその組の文字列二つを除いた要素数2n-2の配列を作り、その組の第一文字列か第二文字列のどちらかが、その要素数2n-2の配列に含まれていなければその組は大丈夫として(具体的には、第一文字列も第二文字列も要素数2n-2の配列に含まれていればフラグをfalseにして)、全ての組が大丈夫であれば(flagがfalseになっていなければ)、「作ることができる」と判定しているのである。(自分が書いたコードなのに、人が書いたコードの解説をしている気分だ。)
Cで書いたのが以下。
typedef struct nom {
char first[11];
char last[11];
}nom;
int scmp1(char* s, char* t, int n);
int readint(char *s);
#define N1 5
#define N2 23
#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);
nom* nms=(nom*)malloc(sizeof(nom)*n);
if(nms==NULL){
printf("memory allocation to nms failed\n");
exit(1);
}
for(int j=0;j<n;j++){
char* s2=(char*)malloc(sizeof(char)*N2);
if(s2==NULL){
printf("memory allocation to s2(%d) failed\n",j);
exit(1);
}
fgets(s2,N2,stdin);
int k=0,l=0;
while(*(s2+k)!=32){
(nms+j)->first[k]=*(s2+k);
k++;
}
(nms+j)->first[k]=0;
k++;
while(*(s2+k)>=97 && *(s2+k)<=122){
(nms+j)->last[l]=*(s2+k);
k++;l++;
}
(nms+j)->last[l]=0;
}
/*
for(int j=0;j<n;j++){
printf("---nms(%d)---\n",j);
printf("%s\n",(nms+j)->first);
printf("%s\n",(nms+j)->last);
}
*/
int flag_first=1,flag_last=1;
for(int j=0;j<n;j++){
for(int h=0;h<n;h++){
if(h==j)continue;
if(scmp1((nms+j)->first,(nms+h)->first,10)==0){
flag_first=0;
}
if(scmp1((nms+j)->first,(nms+h)->last,10)==0){
flag_first=0;
}
if((scmp1((nms+j)->last,(nms+h)->first,10)==0)){
flag_last=0;
}
if((scmp1((nms+j)->last,(nms+h)->last,10)==0)){
flag_last=0;
}
}
if(flag_first==0 && flag_last==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;
}
int scmp1(char* s, char* t, int n){
int i=0;
while(1){
if (*(s+i)==0 && *(t+i)==0) return 0;
else if (*(t+i)!=*(s+i)) return (*(t+i)-*(s+i));
else i++;
if(i>=n){
// printf("s=%s, t=%s, i=%d\n",s,t,i);
// printf("Comparing failed.\n");
}
}
}
ただ、上のコードはACにはなったものの、想定外の動作が残る部分があった。scmp1関数の中の if(i>=n) 条件文の中身をコメントアウトなしで実行すると、例えば次の例(テストケース名は02_except_one_00)
100
avmlajlxrf zttmjemxex
vauvmzqhzs uzgvclqnem
lcljwpbfsg xnbsoouwsn
zifcqxivtq gjcupzgkyz
cinpwuotzy yxojlpipjn
tdnemryudq skxibydrct
tdjdtgtipl eurwjwxvyv
abzttwzxhb amycbijxta
vwzjmmlaew yxojlpipjn
xteucdfimo syiwqxsyvy
vowbgfxsqv sjcegwybmg
urdgjzthal cckapzefmh
jlqemwztfg yzlusdaezt
ejwwcutzsa atxkasugou
fvvvsecqvg csloaexqar
xdudibkgmt dmzuyjjkfu
jnmfxnucto anlkpmegdk
hlwnwahibo wdwgecsbqe
xoeqypczez txgzzkdeco
vrwhijewvl wytsxzogzb
flocshjexi vrounuangs
giiikhuvlw eapudjjlxz
asvwjrhpck oyyrexwiri
cqsqohapin ddpdojipiq
hgtmfsuedp tkjqmgetkl
emrjmdsahn urmlzavbyc
odultqflzd obnwbmbrbv
jhfxadevqt cinpwuotzy
dyvarcvxms tduoqcljzw
pcumzuyzgs xbfsoxvtlx
slzgvyptkq begswrioai
sikliwzvqd ivkzfnjnqs
fxfomljyeo rohrqgsbrr
mwtptktucb gabwlmmezw
swydbovjqx ybfbjxmlkw
qhpbuccyhu dsaxxwfler
guqxzzgrlr ftimlzorzv
bqklofbwzb pyemgoqbqp
xnzsfrgfqd fctpafbged
safprjkxav iducfibsms
bgaczxkjjo qdubpubmqy
gjfgwuapdu mxngjzuyzs
gfmrbrczyv wkybysnbzh
cpqnmbijhc tisbxwevsl
yyepttinlp qxdlcyaryl
rtfvtlsaed gxnmgfdlaz
cztjbttosy xvgevjycvc
niqyddonks pcntudhjex
eprhqytehu gxoechnwzq
uewhzvtawt hdkzmpoxdd
qrtpqcgzid jmdnedpvde
cbobbqkhvo fecwfsshrs
lxlwxjdune nbfsjuwwfl
nfolbzlgjz ayiiidkxpv
secemmlcyo binjogcrin
evzuvmvvxi wsxrlspmwe
edufzrlfzz uhzqiupfoc
cjehxnsfew lfxcujwugl
vfvxpvhkzp zwhyamzuqc
bmhndupair jmijqprnqv
rrxvdkpxxe comgvwojrd
shhltqafiy axpqnlimij
qwjlqpuqyr rwrkgculnr
isiadtwyew gmgrjchxeq
asydjlrgnu rsqxsdaeke
byeogugzvd oimjblsaqp
etfzxishqr zicggawrny
vrkvpixskp pootisasgb
jyquzkympl kpgrarjurw
irokbsgmzn axnmijtbuo
jcicrhohws glmxshpofv
mlcltqliqd edgalwqyrz
qabdaqkuvk gpwzxamavm
rjuybctves qoltuirrbt
ceehfrnnlt wzqpfbegeb
bygsepvzvs wivbkxcwwr
bztgqkaszz kbddlinrdl
bgcwkfhjfd anvaxdphvm
hmkrfrrykj tposlkgyfu
cvpzdchrcf jrkecgpdod
ziyqvltwjr jjywyobhow
mspuosmxsw plkwluwjpg
lnxxowqjmu eggxviqrxd
dgwlamwtdf svrlcuukan
edrefbtrce khqwssekyx
uhcvrasuxf vtvrbfeswq
jupyipafzd ufewjurxbj
bltjuxbtkv zmfhstxyzx
zgcxjwddcs xafyqtugis
glbrpmckrt xqxemkieyn
epbfldpccl idkkwdfvrc
rlcsstqdlx rvdzydkjnp
rhknmgmqdq xyumddhczm
ignokmfecc tizaaxfkgh
zlinrzhweq zzdpcqbjvc
emehoqjlcq gmvctsblgw
yargqiezlu oyifpuekox
ntveljeitx coyexswfvj
nbejnmvkdn amgirkcihn
lxlaawoatn qjofmdhvwt
で、
s=yxojlpipjn, t=yxojlpipjn, i=10
Comparing failed.
s=cinpwuotzy, t=cinpwuotzy, i=10
Comparing failed.
という出力がされてしまうのである。
文字列の文字数が10文字、末尾のヌル文字も含めて11文字あるとき、i=0からはじめたカウンターが11回廻ってi==n(=10)になったときには if (*(s+i)==0 && *(t+i)==0) return 0; の文が実行され、その後に来ている if(i>=n) という条件分岐の所に行くことはないはずなのに、なぜだ、と悩んだ。
scmp1関数の実装がおかしいのかと考えて、
char str1[4]="abc";
char str2[4]="abc";
scmp1(str1,str2,4);
というコードを試しに入れてみたが、こちらでは上の現象は起きない。
原因が分からず、結局 Stackoverflow で質問した。
回答を頂いて分かったことは、例えば上のテストケース02_except_one_00のような文字数10文字で同じ文字列があるときには、i=9(10回目のループ)で最後の文字の比較が行われ、それが同じ文字なので else i++; が実行されてi=10となり、その直後のif(i>=n)以下が実行されてしまうということである。つまり、この場合、scmp1関数の第三引数として渡すべきは10ではなく11だったということになる。文字数が最大10文字だから、11文字目のヌル文字の比較が行われるのはi=0から始めてi=10のとき、だから i==10 となるかで上限チェックをすればいいと思い込んでいたのが間違いだったのである。
それに、よく見れば、abcとabcを比較した時にはscmp1関数の第三引数に文字数+1の4を渡している。だから、それと同じならば、文字数が10の時にはscmp1関数の第三引数は11でなければならないはずだったのだ。分かってみれば当たり前のことなのだが、自分では気づかないものだと実感する。
以下が、そこを修正したコード。先に掲げたコードは、ACにはなったが厳密にはバグのあるコードということになる。
typedef struct nom {
char first[11];
char last[11];
}nom;
int scmp1(char* s, char* t, int n);
int readint(char *s);
#define N1 5
#define N2 23
#define N3 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);
nom* nms=(nom*)malloc(sizeof(nom)*n);
if(nms==NULL){
printf("memory allocation to nms failed\n");
exit(1);
}
for(int j=0;j<n;j++){
char* s2=(char*)malloc(sizeof(char)*N2);
if(s2==NULL){
printf("memory allocation to s2(%d) failed\n",j);
exit(1);
}
fgets(s2,N2,stdin);
int k=0,l=0;
while(*(s2+k)!=32){
(nms+j)->first[k]=*(s2+k);
k++;
}
(nms+j)->first[k]=0;
k++;
while(*(s2+k)>=97 && *(s2+k)<=122){
(nms+j)->last[l]=*(s2+k);
k++;l++;
}
(nms+j)->last[l]=0;
}
/*
for(int j=0;j<n;j++){
printf("---nms(%d)---\n",j);
printf("%s\n",(nms+j)->first);
printf("%s\n",(nms+j)->last);
}
*/
int flag_first=1,flag_last=1;
for(int j=0;j<n;j++){
for(int h=0;h<n;h++){
if(h==j)continue;
if(scmp1((nms+j)->first,(nms+h)->first,N3)==0){
flag_first=0;
}
if(scmp1((nms+j)->first,(nms+h)->last,N3)==0){
flag_first=0;
}
if((scmp1((nms+j)->last,(nms+h)->first,N3)==0)){
flag_last=0;
}
if((scmp1((nms+j)->last,(nms+h)->last,N3)==0)){
flag_last=0;
}
}
if(flag_first==0 && flag_last==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;
}
int scmp1(char* s, char* t, int n){
int i=0;
while(1){
if (*(s+i)==0 && *(t+i)==0) return 0;
else if (*(t+i)!=*(s+i)) return (*(t+i)-*(s+i));
else i++;
if(i>=n){
printf("s=%s, t=%s, i=%d\n",s,t,i);
printf("Comparing failed.\n");
}
}
}
配列の生成
ABC247-C
問題概要
列 S を次のように定義します。
- s[1]は 1 つの 1 からなる長さ 1 の列である。
- S[n](n は 2 以上の整数) は S[n−1],n,S[n−1]をこの順につなげた列である。
解答
問題の定義の通りに処理する。具体的には、nが１ならば1を出力。nが2以上ならば、初期値としてa=[1]を作り、あとは2からnに至るまで、a[n]=a[n-1](連結)[n](連結)a[n-1]という漸化式で新しい配列を作り、それを出力していく。見直してみると、nが1の時の処理を分ける必要はなかったが、まあいい。
n=gets.to_i
a=[]
if n==1
puts 1
exit
else
a=[1]
(2..n).each do |i|
a=a+[i]+a
end
end
puts a.join(" ")
上が本番で提出したコード。C問題としては珍しく簡単だった。
さて、これをCでやるとなると、まず、全部で何項の数列になるかを計算しなければならない。a[n]の項数をc[n]とすると、c[1]=1, c[n+1]=1+2*c[n] だから、c[n+1]+1=2*(c[n]+1), c[1]+1=2 となり、c[n]+1=2*2^(n-1)=2^n で、c[n]=2^n-1 となる。n=1,2,3,4 の場合について、入力例からこれが正しいことが確認できる。
それで書いたのが以下。
void print_ivector(int* a,int n);
int readint(char *s);
#define N1 4
#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 num,oldnum;
int *new;
for(int i=1;i<=n;i++){
num=((1<<i)-1);
if(i==1){
int* temp=(int*)malloc(sizeof(int)*num);
if(temp==NULL){
printf("memory allocation to temp(i=1) failed\n");
exit(1);
}
new=temp;
*new=1;
oldnum=1;
}else{
// printf("num=%d\n",num);
// printf("oldnum=%d\n",oldnum);
int* temp=(int*)realloc(new,sizeof(int)*num);
if(temp==NULL){
printf("memory allocation to temp(i=%d) failed\n",i);
free(new);
exit(1);
}
new=temp;
for(int j=0;j<oldnum;j++){
// printf("j=%d\n",j);
*(new+num/2+1+j)=*(new+j);
}
*(new+num/2)=i;
oldnum=num;
}
}
print_ivector(new,num);
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 print_ivector(int* a,int n){
for(int i=0;i<n-1;i++){
printf("%d ",*(a+i));
}
printf("%d\n",*(a+n-1));
}
