最大値のインデックスをすべて取得
ABC252-B
問題概要
数列aの最大値が、数列bに含まれる数をインデックスとしているか。
解答
n,k=gets.chomp.split(" ").to_a.map(&:to_i)
a=gets.chomp.split(" ").to_a.map(&:to_i)
b=gets.chomp.split(" ").to_a.map(&:to_i)
h=Hash.new
a.each do |item|
if h.has_key?(item)
h[item]+=1
else
h[item]=1
end
end
amax=h.keys.max
amax_idx=[]
a.each_with_index do |item,i|
amax_idx.push(i) if item==amax
end
b.each do |item|
amax_idx.each do |idx|
if item==idx+1
puts "Yes"
exit
end
end
end
puts "No"
「正の字カウント」で、aの各値の出現回数を求める。(今回は出現回数自体は必要ないのだが、既存のコードの流用のため。)そして、もう一度ループを回して、aの最大値のインデックスを配列amax_idxを作る。あとは、amax_idxとbに共通する要素があるか見ていけばよい。
Cで書いたのが以下。
#include<stdio.h>
#include<stdlib.h>
#define MAX 2e9+2
void print_ivector(int* a,int n);
int main(void){
int n,m;
int min_idx,max_idx,min=MAX,max=0;
int max_count=0,min_count=0;
scanf("%d %d\n",&n,&m);
// printf("n=%d, m=%d\n",n,m);
int* a=(int*)malloc(sizeof(int)*n);
int* b=(int*)malloc(sizeof(int)*m);
int* c=(int*)malloc(sizeof(int)*n);
int* d=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++)scanf("%d",a+i);getchar();
for(int i=0;i<m;i++)scanf("%d",b+i);getchar();
/*
printf("a={");
print_ivector(a,n);
printf("}\n");
printf("b={");
print_ivector(b,m);
printf("}\n");
*/
for(int i=0;i<n;i++){
*(c+i)=-1;
*(d+i)=-1;
}
for(int i=0;i<n;i++){
if (*(a+i)>max){
max=*(a+i);
max_idx=i;
for(int i=0;i<=max_count;i++){
*(c+i)=-1;
}
*c=i;
max_count=1;
}else if (*(a+i)==max){
*(c+max_count)=i;
max_count++;
}
if(*(a+i)<min){
min=*(a+i);
min_idx=i;
for(int i=0;i<=min_count;i++){
*(d+i)=-1;
}
*d=i;
min_count=1;
}else if (*(a+i)==min){
*(d+min_count)=i;
min_count++;
}
}
// printf("max : %d, %d個\n",max,max_count+1);
// printf("min : %d, %d個\n",min,min_count+1);
for(int i=0;i<m;i++){
for(int j=0;j<max_count;j++){
if(*(b+i)==*(c+j)+1){
printf("Yes\n");
exit(0);
}
}
}
printf("No\n");
return 0;
}
void print_ivector(int* a,int n){
/*
for(int i=0;i<n;i++){
printf("%d\n",*(a+i));
}
*/
for(int i=0;i<n-1;i++){
printf("%d ",*(a+i));
}
printf("%d\n",*(a+n-1));
}
最大値と最小値のインデックスを保持する配列を作るところはRubyでやった場合と同じだが、このように最初に長さが分からない配列を作るのがCではやりにくい。最大値または最小値の個数は最大でaの要素数に等しいので、今回は、aの同じ長さの配列を作り、それに現在まで見つかったインデックスを入れていき、最大値が更新された時にはそれを初期値の-1に戻すというやりかたでやった。
最大値・最小値のインデックス
ABC275-A
問題概要
解答
最大値・最小値を求めるのは基本中の基本だが、その際にインデックスも更新していけばよい。
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
idx=0
max=0
n.times do |i|
if a[i]>max
max=a[i]
idx=i
end
end
puts idx+1
これは本番中の提出コード。
Cで書いたのが以下。問題では最大値のインデックスだけ求めればよいが、今後使うことも考えて最小値のインデックスも一緒に求めるコードを書いた。
#include<stdio.h>
#include<stdlib.h>
#define MAX 2e9+2
int main(void){
int n,min_idx,max_idx,min=MAX,max=0;
scanf("%d\n",&n);
int* a=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++){
scanf("%d",a+i);
if (*(a+i)>max){
max=*(a+i);
max_idx=i;
}else if(*(a+i)<min){
min=*(a+i);
min_idx=i;
}
}
printf("%d\n",max_idx+1);
// printf("%d\n",min_idx+1);
return 0;
}
より汎用性を求めるなら、インデックスと最大値・最小値を配列で返す関数を作っておいてもいい。
最大値または最小値が複数あって、そのインデックスをすべて答える必要がある場合
ans=[]
n.times do |i|
if cc[i]>max
ans.clear
max=cc[i]
ans.push(i)
elsif cc[i]==max
ans.push(i)
end
end
ans.size.times do |i|
puts ans[i]+1
end
最大値が更新されたときに、インデックスが格納された配列をクリアしてそのインデックスを入れる、もし最大値と同じ値がでてきたら、そのインデックスを答えの配列に追加する、としていけばよい。
後ろから数えたインデックス
ABC276-A
問題概要
英小文字からなる文字列sが与えられる。sに文字aが現れるならば最後に現れるのが何文字目かを出力し、現れないならば−1を出力
文字列を分割して配列にし、末尾から順に見ていけばいい。
解答
a=gets.chomp.split("").to_a
s=a.size
s.downto(0).each do |i|
if a[i]=="a"
puts i+1
exit
end
end
puts -1
これが本番で提出したコード
Cでやったのが以下。
#include<stdio.h>
#include<stdlib.h>
int main(void){
int n,m,ans=0;
scanf("%d %d\n",&n,&m);
int* a=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++){
scanf("%d",a+i);
if(*(a+i)==m){
ans=i+1;
break;
}
}
printf("%d\n",ans);
return 0;
}
要素の出現位置(前から数えたインデックス)を調べる
これは、最も基本的な問題。
ABC277-A
問題概要
n個の数字からなる配列が与えられる、mが何番目に出現するか求めよ。
n,k=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
idx=0
n.times do |i|
if a[i]==k
idx=i
break
end
end
puts idx+1
これが本番で提出したコード。
Cでやったのが以下。
#include<stdio.h>
#include<stdlib.h>
int main(void){
int n,m,ans=0;
scanf("%d %d\n",&n,&m);
int* a=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++){
scanf("%d",a+i);
if(*(a+i)==m){
ans=i+1;
break;
}
}
printf("%d\n",ans);
return 0;
}
ABC297-A
問題概要
配列の隣接する要素の差が初めて一定値以下になる箇所を出力せよ。
解答
n,d=gets.chomp.split(" ").map(&:to_i)
t=gets.chomp.split(" ").map(&:to_i)
(1...n).each do |i|
if t[i]-t[i-1]<=d
puts t[i]
exit
end
end
puts -1
上が本番で提出したコード。以下はCで書いたもの。
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 1000000100
int main(void){
char* s=(char*)malloc(sizeof(char)*N);
fgets(s,N,stdin);
int n=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int d=readint(s+i);
free(s);
//printf("%d %d\n",n,d);
char* s2=(char*)malloc(sizeof(char)*N);
fgets(s2,N,stdin);
int* a=(int*)malloc(sizeof(int)*n);
input_iarray(s,a,n,N);
for(int i=1;i<n;i++){
if((*(a+i)-*(a+i-1))<=d){
printf("%d\n",*(a+i));
exit(0);
}
}
printf("%d\n",-1);
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
// printf("%d\n",*(s+i));
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\n");
}
Rubyだと61秒かかっていたものがCでは1秒と、猛烈に速い。
ところで、このコードをCで試すとSegmentation fault (core dumped)というエラーになり、原因が分からずStackoverflowで質問した。その際に、n,dの入力部分は省略したコードを載せたのだが、これは質問のしかたとしてはよくなかったようで、批判を頂いた。結局、原因はn,dの入力用に確保したメモリsでそのまま配列の入った文字列を読み込んだところにあったようで、そこを別にメモリを確保しなおしたら正常に動いた。
ABC299-B
問題概要
整数n,tと二つの整数列が与えられる。配列cにtが一個以上含まれていれば、c[i]==tとなるr[i]のうちで最大のもののインデックス(1-indexed)を、tが配列cに含まれていなければ、c[i]==c[1]となるr[i]のうちで最大のもののインデックス(1-indexed)を出力せよ。
解答
n,t=gets.chomp.split(" ").map(&:to_i)
c=gets.chomp.split(" ").map(&:to_i)
r=gets.chomp.split(" ").map(&:to_i)
cnt=0
idxs1=[]
idxs2=[]
max1=0
max2=0
m1_idx=0
m2_idx=0
n.times do |i|
if c[i]==t
cnt+=1
idxs1.push(i)
if r[i]>max1
max1=r[i]
m1_idx=i
end
elsif c[i]==c[0]
idxs2.push(i)
if r[i]>max2
max2=r[i]
m2_idx=i
end
end
end
if cnt>0
puts m1_idx+1
else
puts m2_idx+1
end
上が本番で提出したコード。以下はCで書いたもの。
typedef struct {
int c;
int r;
} player;
void print_player(player *pl, int n);
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 20
#define N 100000002
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
fgets(s1,N1,stdin);
int i=0;
int n=readint(s1);
while(*(s1+i)!=32)i++;
i++;
int t=readint(s1+i);
free(s1);
char* s2=(char*)malloc(sizeof(char)*N);
fgets(s2,N,stdin);
char* s3=(char*)malloc(sizeof(char)*N);
fgets(s3,N,stdin);
int * c=(int*)malloc(sizeof(int)*n);
int * r=(int*)malloc(sizeof(int)*n);
input_iarray(s2,c,n,N);
input_iarray(s3,r,n,N);
// print_ivector(c,n);
// print_ivector(r,n);
player* pls=(player*)(malloc(sizeof(player)*n));
for(int i=0;i<n;i++){
(pls+i)->c=*(c+i);
(pls+i)->r=*(r+i);
}
// print_player(pls,n);
int max1=-1,max2=pls->r;
int max1_idx=-1,max2_idx=0;
int pl1c=pls->c;
for(int i=0;i<n;i++){
if ((pls+i)->c == t && (pls+i)->r > max1){
max1=(pls+i)->r;
max1_idx=i;
}
if ((pls+i)->c == pl1c && (pls+i)->r > max2){
max2=(pls+i)->r;
max2_idx=i;
}
}
if (max1==-1)printf("%d\n",max2_idx+1);
else printf("%d\n",max1_idx+1);
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
// printf("%d\n",*(s+i));
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\n");
}
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));
}
void print_player(player *pl, int n){
for(int i=0;i<n;i++)printf("[%d %d], ",(pl+i)->c,(pl+i)->r);
printf("\n");
}
ABC300-A
問題概要
与えられた整数列のなかに、和がa+bであるものがあるか判定せよ。
解答
n,a,b=gets.chomp.split(" ").map(&:to_i)
c=gets.chomp.split(" ").map(&:to_i)
idx=0
n.times do |i|
if c[i]==(a+b)
idx=i
break
end
end
puts idx+1
上が本番で提出したコード。以下はCで書いたもの。
void input_iarray(char* s,int* a,int n,int imax);
int str_toi(char* s);
#include<stdio.h>
#include<stdlib.h>
#define N1 13
#define N 1000000002
int main(void){
int n,a,b;
int i=0;
char *s=(char*)malloc(sizeof(char)*N1);
fgets(s,N1,stdin);
// printf("%s\n",s);
n=str_toi(s);
while(*(s+i)!=32)i++;
i++;
a=str_toi(s+i);
while(*(s+i)!=32)i++;
i++;
b=str_toi(s+i);
// printf("%d %d %d\n",n,a,b);
char *s2=(char*)malloc(sizeof(char)*N);
fgets(s2,N,stdin);
int* c=(int*)malloc(sizeof(int)*n);
input_iarray(s2,c,n,N);
/* for(int j=0;j<n;j++){
printf("%d ",*(c+j));
}
printf("\n");*/
for(int j=0;j<n;j++){
if(*(c+j)==(a+b)){
printf("%d\n",j+1);
exit(0);
}
}
printf("No\n");
return 0;
}
int str_toi(char* s){
int t=0,i=0,minus_flag=0;
while((*(s+i)<48 || *(s+i)>57) && *(s+i)!='-' && *(s+i)!='+')i++;
if (*(s+i)=='-'){
minus_flag=1; i++;
}else if (*(s+i)=='+'){
i++;
}
while(*(s+i)>=48 && *(s+i)<=57){
t*=10;
t+=*(s+i)-48;i++;
}
if (minus_flag)t*=(-1);
//printf("%s: %d\n",s,t);
return t;
}
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);
}
連続する整数列の中の抜けている数字を見つける
ABC317-B
問題概要
連続する整数列の中の一つの要素が抜けた数列が与えられる。その抜けている要素を出力せよ。
解答
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
min=a.min
max=a.max
(min..max).each do |it|
if !a.include?(it)
puts it
end
end
答えは一意に定まるという制約があるので、与えられた配列の両端に抜けている数字が来ることはない。なので、与えられた配列の最大値と最小値の間に抜けている数がないか探せばよい。
上が本番で提出したコード。以下はCで書いたもの。なお、Cでのコードを書いたときに、毎回ループを回すのは無駄なので、最初に配列をソートしてしまった方がいいと気付いたが、ソートのコードをすぐには書けなかったので、やり方はとりあえずrubyでやったときと同じにした。
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#define N1 20
#define N 100000002
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
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);
int max=0,min=INT_MAX;
for(int i=0;i<n;i++){
if (max<*(a+i))max=*(a+i);
if (min>*(a+i))min=*(a+i);
}
for(int i=min+1;i<max;i++){
int flag=0;
for(int j=0;j<n;j++){
if (*(a+j)==i)flag=1;
}
if (flag==0){
printf("%d\n",i);
exit(0);
}
}
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
// printf("%d\n",*(s+i));
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);
}
二番目に大きい値
ABC329-B
問題概要
整数を要素とする配列の中で、最大値ではない数のうち最大のものを出力せよ。なお、配列の全てが同じ数であることはない。
解答
制約により配列の要素の全てが同じ数である可能性はないので、uniqメソッドで配列の重複要素を削除すれば要素数は必ず2個以上になる。それを(昇順で)ソートして、後ろから2番目のものを出力すればよい。
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
a.uniq!
a.sort!
puts a[a.size-2]
上が本番で提出したコード。以下はCで書いたもの。
typedef struct {
int v;
struct tn *l;
struct tn *r;
} tn;
int push_element(tn* f, int* ar);
tn* create_tn(int v);
void insert_tn(int v, tn *node);
int seccond_largest(tn* baum, int prev);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N1 20
#define N 100000002
tn *root=NULL;
int cnt=0, ar_idx=0;
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
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);
for(int i=0;i<n;i++){
insert_tn(*(a+i),root);
}
int * b=(int*)malloc(sizeof(int)*cnt);
push_element(root,b);
printf("%d\n",*(b+cnt-2));
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
// printf("%d\n",*(s+i));
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);
}
tn* create_tn(int v){
tn* neu;
neu=(tn*)malloc(sizeof(tn));
if(neu==NULL){
printf("Memory allocation failure.");
exit(0);
}
neu->l=NULL;
neu->r=NULL;
neu->v=v;cnt++;
return neu;
}
void insert_tn(int v, tn *node){
if(node==NULL){
root=create_tn(v);
return;
} else if (v == node->v){
return;
} else if (v < node->v){
if (node->l !=NULL){
insert_tn(v,node->l);
} else {
node->l = create_tn(v);
}
} else if (node->v < v){
if (node->r !=NULL){
insert_tn(v,node->r);
} else {
node->r = create_tn(v);
}
}
return;
}
int push_element(tn* f, int* ar){
if(f->l!=NULL){
push_element(f->l,ar);
}
*(ar+(ar_idx++))=f->v;
if(f->r!=NULL){
push_element(f->r,ar);
}
}
二分木の実装自体は書籍に載っていたコードを見て書いたので問題なかったが、二番目に大きい値を出力する部分でかなり手間取る。初めは、木から直接に二番目に大きい値が入っているノードを求めるコードを書こうとしたが、うまくいかないので、結局、一旦木の内容を配列に出力し、その最後から二番目の要素を出力することにした。いずれにせよ、こちらの方が汎用性のあるコードではある。
0 件のコメント:
コメントを投稿