間を埋める
ABC301-B
問題概要
与えられた整数列の、間隔が1でないところを整数で埋めて全ての間隔を1にせよ。
解答
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
b=[]
b.push(a[0])
(1...n).each do |i|
t=a[i]-a[i-1]
if t.abs==1
b.push(a[i])
elsif a[i]>a[i-1]
temp=((a[i-1]+1)..a[i]).to_a
b+=temp
elsif a[i]<a[i-1]
temp=(a[i]..a[i-1]-1).to_a.reverse
b+=temp
end
end
puts b.join(" ")
上が本番で提出したコード。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 N1 5
#define N2 401
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);
char *s2=(char*)malloc(sizeof(char)*N2);
if(s2==NULL){
printf("memory allocation to s3 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);
free(s2);
// print_ivector(a,n);
printf("%d",*a);
for(int i=1;i<n;i++){
putchar(32);
if(*(a+i-1)-*(a+i)==1 || *(a+i)-*(a+i-1)==1){
printf("%d",*(a+i));
}
else if(*(a+i)<*(a+i-1)){
int m=*(a+i-1)-*(a+i)-1;
for(int j=0;j<m;j++){
if(j!=0)putchar(32);
printf("%d",*(a+i-1)-j-1);
}
putchar(32);
printf("%d",*(a+i));
}else if(*(a+i)>*(a+i-1)){
int m=*(a+i)-*(a+i-1)-1;
for(int j=0;j<m;j++){
if(j!=0)putchar(32);
printf("%d",*(a+i-1)+j+1);
}
putchar(32);
printf("%d",*(a+i));
}
}
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));
}
ABC304-A
問題概要
環状配列において名前と数値がセットで与えられる。数値が最小の部分を起点として出力せよ。
解答
n=gets.to_i
year=Array.new(2*n,0)
name=Array.new(2*n,"")
idx=0
min=1e9
n.times do |i|
t1,t2=gets.chomp.split(" ")
y=t2.to_i
name[i]=name[i+n]=t1
year[i]=year[i+n]=y
if y<min
min=y
idx=i
end
end
n.times do |i|
puts name[idx+i]
end
上が本番で提出したコード。Cで書いたのが以下。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 5
#define N2 11
#define N3 23
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);
char *s2=(char*)malloc(sizeof(char)*N2*n);
if(s2==NULL){
printf("memory allocation to s2 failed\n");
exit(1);
}
int *a=(int*)malloc(sizeof(int)*n);
if(a==NULL){
printf("memory allocation to a 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 j=0;
while(*(s3+j)>=97 && *(s3+j)<=122){
*(s2+N2*i+j)=*(s3+j); j++;
}
*(s2+N2*i+j)=0;
j++;
*(a+i)=readint(s3+j);
free(s3);
}
/* for(int i=0;i<n;i++){
printf("%s ",s2+N2*i);
printf("%d\n",*(a+i));
}*/
int min_idx=0;
int min=1e9;
for(int i=0;i<n;i++){
if(*(a+i)<min){
min=*(a+i);
min_idx=i;
}
}
for(int i=0;i<n;i++){
int idx=(min_idx+i)%n;
printf("%s\n",(s2+idx*N2));
}
free(s2);
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;
}
ABC308-A
問題概要
長さ8の整数列が与えられる。これが条件「広義単調増加であり、全ての要素は100以上675以下であり、25の倍数である」を満たすか判定せよ。
解答
n=8
a=gets.chomp.split(" ").map(&:to_i)
n.times do |i|
if a[i]<100 || a[i]>675 || a[i]%25!=0
puts "No"
exit
elsif i>=1 && a[i]<a[i-1]
puts "No"
exit
end
end
puts "Yes"
上が本番で提出したコード。Cで書いたのが以下。
void input_iarray(char* s,int* a,int n,int imax);
#include<stdio.h>
#include<stdlib.h>
#define N1 41
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 *a=(int*)malloc(sizeof(int)*8);
if(a==NULL){
printf("memory allocation to a failed\n");
exit(1);
}
input_iarray(s1,a,8,N1);
free(s1);
int flag=1;
for(int i=0;i<7;i++){
if(*(a+i)>*(a+i+1))flag=0;
if(*(a+i)<100 || *(a+i)>675)flag=0;
if(*(a+i)%25!=0)flag=0;
if(flag==0){
printf("No\n");
exit(0);
}
}
printf("Yes\n");
return 0;
}
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\n");
}
ABC313-A
問題概要
配列の最初の要素(a[0])が他の全ての要素よりも大きくなるようにするには、a[0]に何を加えればよいか。。
解答
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
mx=0
(1...n).each do |i|
if a[i]>mx
mx=a[i]
end
end
if a[0]>mx
puts 0
else
puts mx-a[0]+1
end
上が本番で提出したコード。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 N1 5
#define N2 401
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);
char *s2=(char*)malloc(sizeof(char)*N2);
if(s2==NULL){
printf("memory allocation to s3 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);
free(s2);
// print_ivector(a,n);
int max=0;
for(int i=1;i<n;i++){
if(*(a+i)>max){
max=*(a+i);
}
}
int ans=0;
if((max-*a)>=0){
ans=max-*a+1;
}
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 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));
}
ABC314-B
問題概要
n個の整数列が与えられる。xを含み、かつ要素数が最も少ない配列の番号を昇順で出力せよ。
解答
n=gets.to_i
c=[]
a=[]
ans=[]
n.times do |i|
c[i]=gets.to_i
a[i]=gets.chomp.split(" ").map(&:to_i)
end
x=gets.to_i
n.times do |i|
flag=false
if a[i].include?(x)
flag=true
n.times do |j|
if a[j].include?(x) && c[j]<c[i]
flag=false
break
end
end
if flag==true
ans.push(i+1)
end
end
end
puts ans.size
puts ans.join(" ")
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 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));
}
まず、① n*38のサイズのメモリ ars を取って、与えられたn組の各データを、行の先頭にcを格納し、続く部分に二行目の配列を格納して、残りの部分があればそこを-1で埋めた配列の形で保持し、次に、② xを含み行の最も小さい要素数minを求め、最後に、③ xを含み要素数が min である行番号の配列を作っている。(ansも最初に全部を-1で埋めているが、出力は-1でない実要素が入った部分のみとしている。)
このコードは、入力例の二つの例ではACになるのだが、他の大部分ではWAになる。
例えば、テストケース000.txt
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
では、
(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という出力となり、この場合たまたま解答は正解と一致しているのだが、本来36であるはずのxが0になる。
更に、上のテストケースでn=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としてみると、
(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となって、2組目のデータが正しく読み込まれていないうえ、xの読み込みのfgetsが失敗している。
1組目のデータの読み込みの最後のところに問題があるのではないかと推測したが、それがなんであるのか分からず、StackOverflowで質問した。
結果は、なんと、配列aのメモリを確保した際に、イント型c個のメモリを取らなければいけないところ、cではなくnと書いていたのが原因だった。
指摘されてみれば拍子抜けするような単純なミスだったのだが、それに自分で気付かなかったのは事実。そう言えば、前にも変数名の書き間違いでコードがうまく動かず、原因がなかなか分からずに悩んだことがあった。
回答を頂いたactorbugさんからは、ローカルのデバッグ環境無しでCを使うのは無謀だと言われたが、確かにこういったミスに気付くための仕組みはないといけないかもしれないと思い始める。
さて、そこを直しても、上の修正テストケースで正しい結果が得られない。この場合
1
2
とならなければいけないのに
1 1となってしまう。
目的のxが何行目の左から何番目に見つかったかも分かるようにデバッグ出力に手を加えてみながら(114行目)考えて、ここは j<*(ars+i*(N2+1)) ではなく、j<=*(ars+i*(N2+1)) としなければならないことに気付く。そうしないと、例えば要素数が1の場合、j=1から始めて j<1までの繰り返しになるので、ループが1回も回らないまま終わってしまう。どうも、(N2+1)に引きずられて、既に行の要素数の上限に1を足しているからその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));
}
ABC318-A
問題概要
数列 a[i]=m+p*i (i=1,2,…) の要素のうち、n以下であるものはいくつあるか。
解答
n,m,p=gets.chomp.split(" ").map(&:to_i)
if m<=n
puts (n-m)/p+1
else
puts 0
end
a[i]がnを超えるまでループを回すのも芸がないので上のようなコードにした。場合分けをしたのは、例えばn=2,m=5,p=1のとき、(n-m)/p+1は-3となるように負の値になってしまうことがあるため。
上が本番で提出したコード。Cで書いたのが以下。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 22
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);
int i=0;
while(*(s1+i)!=32)i++;
i++;
int m=readint(s1+i);
while(*(s1+i)!=32)i++;
i++;
int p=readint(s1+i);
free(s1);
// printf("n=%d m=%d p=%d\n",n,m,p);
int ans=-1;
if(n>=m){
ans=(n-m)/p+1;
}else{
ans=0;
}
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;
}
ABC321-A
問題概要
与えられた数字の各桁の数が左から見て狭義単調減少になっているか判定せよ。
解答
n=gets.to_i
s=n.to_s.split("").map(&:to_i)
(1...s.size).each do |i|
if s[i]>=s[i-1]
puts "No"
exit
end
end
puts "Yes"
上が本番で提出したコード。Cでやったのが以下。
#include
#include
#define N 7
int readint(char *s);
int main(void){
char* s=(char*)malloc(sizeof(char)*N);
if(s==NULL){
printf("memory allocation to s failed\n");
exit(1);
}
char* ts1=fgets(s,N,stdin);
if(ts1==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int i=1;
while(*(s+i)>=48 && *(s+i)<=57){
if(*(s+i)>=*(s+i-1)){
printf("No\n");
exit(0);
}
i++;
}
printf("Yes\n");
free(s);
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;
}
ABC321-B
問題概要
n-1 個の整数からなる配列が与えられる。これにもう一つの整数を加えてできる配列を a とする。配列 a の最大値と最小値を一つずつ(最大値、最小値が複数ある場合には、それぞれについて一つのみが取り除かれる)取り除いた後の各要素の和をx以上とするための最後に加えるべき整数の最小値を出力せよ。
解答
n,x=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
a.sort!
sum1=sum2=0
(1..(n-3)).each do |i|
sum1+=a[i]
end
sum2=sum1+a[n-2]
if sum1>=x
puts 0
elsif sum1<x && sum2>=x
if x-sum1<=100
ans=x-sum1
if ans==a[n-2]
puts 0
else
puts ans
end
end
else
puts -1
end
上が本番で提出したコードなのだが、ACが38個、WAが8個となった。
新たにCで書きながら、改めて考えてみる。
32 50 70というような入力例を考え、最小値をmin, 真ん中の値をmid, 最大値をmaxとする。また、この段階での配列の総和は sum=152 である。この状態で、最大値と最小値を除いた総和は、mid=50 である。
ここで、最後に加えられた値(yとする)がmin以下だったとすると、新たにyがminとなり、総和は mid=50 に min=32 を足し戻した 82 になる。だからこの場合、sum-max が x 以上であればよいことになる。逆に言えば、sum-max が x 以上であれば、新たに加える値がmin以下の値であれば何でもよいことになる。よってこの場合には、配列の要素の取りうる最小値である0を答えればよい。
次に、yがmin以上でmax以下である場合を考える。この場合、従来のmaxとminが和から取り除かれることは変わらず、新たな配列の和は (sum-min-max)+y となる。よって、これが x 以上であればよい。逆に言えば、条件を満たす y の最小値は、x-(sum-min-max) である。max以下のこのようなyが存在すればよい。
最後に、yがmax以上である場合。この場合には、和から取り除かれるのは y であり、従前の和 mid=50 に max=70 が足し戻され、和は120 になる。つまり、新たな和は sum-min となる。この場合、最後に加えられる値は max 以上であれば何でもいいので、その中の最小値であるmaxを答えることになるが、最後の値がmaxに等しい場合は上の第二のケースに含めて考えることができ、独立して場合を立てる必要はない。
それをコード化してACになったのが、以下。
#include<stdio.h>
#include<stdlib.h>
#define N 10
#define N2 397
void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
int main(void){
char* s=(char*)malloc(sizeof(char)*N);
if(s==NULL){
printf("memory allocation to s failed\n");
exit(1);
}
char* ts1=fgets(s,N,stdin);
if(ts1==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int i=1;
int n=readint(s);
while(*(s+i)>=48 && *(s+i)<=57){
i++;
}
i++;
int x=readint(s+i);
free(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-1,N2);
int min=100,max=0,sum=0,ans=0;
for(i=0;i<n-1;i++){
if(*(a+i)<min){
min=*(a+i);
}
if(*(a+i)>=max){
max=*(a+i);
}
sum+=*(a+i);
}
// printf("n=%d x=%d\n",n,x);
// print_ivector(a,n-1);
// printf("min=%d max=%d sum=%d\n",min,max,sum);
if(sum-max>= x){
ans=0;
}else if (x-(sum-min-max) <= max){
ans=x-(sum-min-max);
}else {
ans=-1;
}
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 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));
}
ABC324-A
問題概要
与えられた配列の全ての項が等しいか判定せよ。
解答
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
(1...n).each do |i|
if a[i]!=a[0]
puts "No"
exit
end
end
上が本番で提出したコード。Cでやったのが以下。
#include<stdio.h>
#include<stdlib.h>
#define N 5
#define N2 401
void print_ivector(int* a,int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
int main(void){
char* s=(char*)malloc(sizeof(char)*N);
if(s==NULL){
printf("memory allocation to s failed\n");
exit(1);
}
char* ts1=fgets(s,N,stdin);
if(ts1==NULL){
printf("fgets(s) failed\n");
exit(1);
}
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);
}
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);
for(int i=1;i<n;i++){
if(*(a+i)!=*a){
printf("No\n");
exit(0);
}
}
//printf("n=%d\n",n);
//print_ivector(a,n);
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));
}
0 件のコメント:
コメントを投稿