数を数える
今回は、具体的なABCの問題から入るのではなく、一般的な場合から。
与えられたデータの中に、区別できるものがそれぞれ何個ずつあるかを数える。。
まずは、要素の種類が分かっている場合
例えば、o,xだけとか、"Yes", "No"だけとか、一桁の数字だけとか。
もっと多くて、都道府県とか、アメリカ合衆国の州とかいう場合も考えられる。
こういう時には、あらかじめハッシュテーブルを用意しておいて、ハッシュのキーと同じものが出てきたら、そのキーのの値を一つずつ増やしていけばよい。
設例1
データ oxooxoxxxxoo が標準入力から与えられるとする。この中に、o と x はそれぞれ何個ずつあるか。
解答
h={o:0,x:1}
a=gets.chomp.split("").to_a
a.each do |it|
h[it.to_sym]+=1
end
puts "o:#{h[:o]}"
puts "x:#{h[:x]}"
実行結果は、
o:3
x:3
次に、出現する要素があらかじめわかっていない場合どうするかを見ていく。
あらかじめわかっていない要素の数を数える問題
[a,a,a,b,b,c]のような、特異な要素がそれぞれ複数個ありうる配列が与えられて、その特異な要素ごとにその数を数える、というタイプの問題である。実用度はかなり高い。手作業でやる時には、「順番に見ていって、新しい要素が出てきたらその名前を書いて、その下に正の字の最初の一画を書き、二回以上出現した要素については、既に書いた名前の下の正の字の画数を増やしていく」、ということをするのだが、それをコンピューターでやろうとするとどうするか。
データ
μῆνιν ἄειδε θεὰ Πηληϊάδεω Ἀχιλῆος οὐλομένην, ἣ μυρί᾽ Ἀχαιοῖς ἄλγε᾽ ἔθηκε, πολλὰς δ᾽ ἰφθίμους ψυχὰς Ἄϊδι προΐαψεν ἡρώων, αὐτοὺς δὲ ἑλώρια τεῦχε κύνεσσιν 5οἰωνοῖσί τε πᾶσι, Διὸς δ᾽ ἐτελείετο βουλή, ἐξ οὗ δὴ τὰ πρῶτα διαστήτην ἐρίσαντε Ἀτρεΐδης τε ἄναξ ἀνδρῶν καὶ δῖος Ἀχιλλεύς. τίς τ᾽ ἄρ σφωε θεῶν ἔριδι ξυνέηκε μάχεσθαι;の中に出てくる文字を文字ごとに集計せよ。(アクセント記号、気息記号が異なれば別の文字として扱う。)
解答
一つの案は、配列を使うやり方で、
s=<<'EOS'
μῆνιν ἄειδε θεὰ Πηληϊάδεω Ἀχιλῆος
οὐλομένην, ἣ μυρί᾽ Ἀχαιοῖς ἄλγε᾽ ἔθηκε,
πολλὰς δ᾽ ἰφθίμους ψυχὰς Ἄϊδι προΐαψεν
ἡρώων, αὐτοὺς δὲ ἑλώρια τεῦχε κύνεσσιν
5οἰωνοῖσί τε πᾶσι, Διὸς δ᾽ ἐτελείετο βουλή,
ἐξ οὗ δὴ τὰ πρῶτα διαστήτην ἐρίσαντε
Ἀτρεΐδης τε ἄναξ ἀνδρῶν καὶ δῖος Ἀχιλλεύς.
τίς τ᾽ ἄρ σφωε θεῶν ἔριδι ξυνέηκε μάχεσθαι;
EOS
list=[]
number=[]
(0...s.size).each do |i|
if s[i]=="\n" || s[i]==" "
next
elsif list.include?(s[i])
number[list.index(s[i])]+=1
else
list.push(s[i])
number.push(1)
end
end
list.size.times do |i|
puts "#{list[i]} : #{number[i]}"
end
実行結果は、
μ : 5 ῆ : 2 ν : 16 ι : 14 ἄ : 4 ε : 22 δ : 12 θ : 5 ὰ : 4 Π : 1 η : 7 λ : 11 ϊ : 2 ά : 2 ω : 4 Ἀ : 4 χ : 6 ο : 14 ς : 11 ὐ : 2 έ : 2 , : 5 ἣ : 1 υ : 5 ρ : 10 ί : 6 ᾽ : 5 α : 10 ῖ : 3 γ : 1 ἔ : 2 κ : 4 π : 4 ἰ : 2 φ : 2 ψ : 2 Ἄ : 1 ΐ : 2 ἡ : 1 ώ : 2 τ : 14 ὺ : 1 ὲ : 1 ἑ : 1 ῦ : 1 ύ : 2 σ : 8 5 : 1 ᾶ : 1 Δ : 1 ὸ : 1 ἐ : 3 β : 1 ή : 2 ξ : 3 ὗ : 1 ὴ : 1 ῶ : 3 ἀ : 1 ὶ : 1 . : 1 ; : 1のようになった。
もう一つのやり方として、rubyにはハッシュという便利なクラスが用意されているので、それを使うもの。実際に問題を解く際にはたいていこちらでやっているので、これについてはそちらの実例を参照。
数を数える
ABC240-B
問題概要
長さ N の正整数列 aには何種類の整数が現れるか。
解答
n=gets.to_i
a=gets.split.map(&:to_i)
b=[]
c=[]
n.times do |i|
if b.include?(a[i])
c[b.index(a[i])]+=1
else
b.push(a[i])
c[b.index(a[i])]=1
end
end
puts b.size
上が本番で提出したコード。Cで最初にやったのが以下。(REになった。)
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 2e9
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
fgets(s1,N1,stdin);
int n=readint(s1);
free(s1);
char* s2=(char*)malloc(sizeof(char)*N);
fgets(s2,N,stdin);
int * a=(int*)malloc(sizeof(int)*n);
input_iarray(s2,a,n,N);
free(s2);
int max=0;
for(int i=0;i<n;i++){
if (*(a+i)>max)max=*(a+i);
}
int * nums=(int*)malloc(sizeof(int)*(max+1));
for(int i=0;i<=max;i++)*(nums+i)=0;
for(int i=0;i<n;i++){
int num=*(a+i);
*(nums+num)+=1;
}
int ans=0;
for(int i=1;i<=n;i++){
if (*(nums+i))ans++;
}
printf("%d\n",ans);
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);
}
サンプル3件ではACになるが、他のテストケースでは全てREになった。
Paiza.ioにテストケースのデータを入れてやってみると、こちらでもエラーになる。一旦コード全体をコメントアウトし、少しずつコメントアウトを外しながらエラーが起る場所を探してみると、問題の箇所は25行目(*(nums+num)+=1;)のようだ。
だが、メモリは十分に確保しているはずなのに、どうしてエラーになるのか分からず、StackOverflowで質問。
原因は、メモリ制限がPaiza.ioで512MB, AtCoderでも1024MBなのに対し、制約上のa[i]の最大値10^9個のint型メモリを確保しようとすると4000MBになってしまうのが原因のようだ。それで、mallocがNULLを返すが、そこにそのままデータを入れようとしてランタイムエラーになったらしい。(attakeiさん、actorbugさん、コメント・回答有難うございました。)
それで、結局二分木を使って出現した数のリストを作ることに。と言っても、少し前に作ったABC329-Bのコードがほぼそのまま使えたので、新しく書いたところはほとんどない。それが以下。
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",cnt);
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);
}
}
ABC263-A
問題概要
フルハウスかどうか判定(正の字カウント)
ABC263-A
問題概要
５つの数がが与えられる。それらが、それぞれ３個と２個の二種類の数字からなるかどうか判定せよ。
解答
本番では別のやり方でやったのだが、これは正の字カウントでやった方が素直だし早い。
a=gets.chomp.split(" ").map(&:to_i)
h=Hash.new
a.each do |item|
if h.has_key?(item)
h[item]+=1
else
h[item]=1
end
end
ss=h.size
if ss!=2
puts "No"
exit
end
hv=h.values
if hv[0]==2 && hv[1]==3 || hv[0]==3 && hv[1]==2
puts "Yes"
else
puts "No"
end
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);
}
fgets(s1,N1,stdin);
int* a=(int*)malloc(sizeof(int)*5);
if (a==NULL){
printf("memory allocation to a failed.\n");
exit(1);
}
int i=0,j=0;
for(;i<4;i++){
*(a+i)=readint(s1+j);
while(*(s1+j)!=32)j++;
j++;
}
*(a+i)=readint(s1+j);
int* r=(int*)malloc(sizeof(int)*14);
if (a==NULL){
printf("memory allocation to r failed.\n");
exit(1);
}
for(i=0;i<=13;i++)*(r+i)=0;
for(i=0;i<5;i++){
int t=*(a+i);
*(r+t)+=1;
}
int cnt=0;
for(i=1;i<=13;i++){
if(*(r+i))cnt++;
}
// printf("%d\n",cnt);
if (cnt!=2){
printf("No\n");
exit(0);
}else{
int n1=0,n2=0;
for(i=1;i<=13;i++){
if(*(r+i)){
if (n1==0)n1=*(r+i);
else n2=*(r+i);
}
}
// printf("n1=%d, n2=%d\n",n1,n2);
if ((n1==3 && n2==2) || n2==3 && n1==2){
printf("Yes\n");
exit(0);
}else{
printf("No\n");
exit(0);
}
}
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;
}
昨日やったABC268-Aのコードがかなり流用できたので、今回はmallocのNULLチェックも入れてみた。
ABC268-A
問題概要
5個の数字が与えられる。この中に数字が何種類あるか答えよ。
解答
a=gets.chomp.split(" ").map(&:to_i)
h=Hash.new
a.each do |item|
if h.has_key?(item)
h[item]+=1
else
h[item]=1
end
end
puts h.size
空ハッシュを作っておき、配列の要素をはじめから順番に見ていって、もしハッシュのキーにその要素が既にあれば、その値を一増やし、もしなければ新しいキーを追加し、その値を１にしている。問題の答えは、最終的なハッシュのサイズになる。
もっとも、この問題の場合、各キーの個数は必要なく、ユニークな要素が何種類あるか分かればそれでいいから、
a=gets.chomp.split(" ").map(&:to_i)
au=a.uniq!
puts au.size
としてもよい。
Cで書いたのが以下。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 22
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
fgets(s1,N1,stdin);
int* a=(int*)malloc(sizeof(int)*5);
int i=0,j=0;
for(;i<4;i++){
*(a+i)=readint(s1+j);
while(*(s1+j)!=32)j++;
j++;
}
*(a+i)=readint(s1+j);
int* r=(int*)malloc(sizeof(int)*101);
for(i=0;i<=100;i++)*(r+i)=0;
for(i=0;i<5;i++){
int t=*(a+i);
*(r+t)+=1;
}
int ans=0;
for(i=0;i<=100;i++){
if(*(r+i))ans++;
}
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;
}
数を数える
ABC287-A
問題概要
ForまたはAgainstからなる文字列がn個与えられる。Forが過半数より多いか否か判定せよ。
解答
n=gets.to_i
count=0
n.times do |i|
s=gets.chomp
if s=="For"
count+=1
end
end
if count>n/2
puts "Yes"
else
puts "No"
end
上が本番で提出したコード。Cで書いたのが以下。
int scmp(char *s, char *t);
int is_nonletter(char *c);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 20
#define N2 1000
#define N 100000002
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
fgets(s1,N1,stdin);
int n=readint(s1);
free(s1);
char* s=(char*)malloc(sizeof(char)*N2);
for(int i=0;i<n;i++){
fgets(s+10*i,10,stdin);
}
/* for(int i=0;i<n;i++){
printf("%s\n",s+10*i);
}*/
const char* ar[2]={"For","Against"};
// printf("%s\n",ar[0]);
int yes=0,no=0;
for(int i=0;i<n;i++){
if(scmp(s+10*i,ar[0])==0)yes++;
else if(scmp(s+10*i,ar[1])==0)no++;
}
if (yes>no){
printf("Yes");
}else{
printf("No");
}
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;
}
int scmp(char *s, char *t){
int i=0;
//printf("s=%s,t=%s\n",s,t);
int flag=4;
while(1){
if (is_nonletter(s+i) && is_nonletter(t+i))flag=0;
else if (is_nonletter(s+i) && !is_nonletter(t+i))flag=-2;
else if (!is_nonletter(s+i) && is_nonletter(t+i))flag=2;
else if(*(s+i)>*(t+i))flag=1;
else if(*(s+i)<*(t+i))flag=-1;
else if(*(s+i)==*(t+i))i++;
else flag=-2;
if (flag!=4)return flag;
}
return flag;
}
int is_nonletter(char *c){
if (*c<=32 || *c==127)return 1;
else return 0;
}
条件に一致するものの数を数える
ABC287-B
問題概要
数字文字列の配列s(文字数6),t(文字数3)がある。配列sに含まれる文字列のうち、その４～６文字目が配列tに含まれる文字列と一致するものがいくつあるか求めよ。
解答
n,m=gets.chomp.split(" ").map(&:to_i)
s=[]
t=[]
count=0
(0...n).each do |i|
s[i]=gets.chomp
end
(0...m).each do |i|
t[i]=gets.chomp
end
(0...n).each do |i|
(0...m).each do |j|
if s[i].slice(3,3)==t[j]
count+=1
break
end
end
end
puts count
上が本番で提出したコード。Cで書いたのが以下だが、まずはWAになったコード。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 20
#define NS 8000
#define NT 5000
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
fgets(s1,N1,stdin);
int n=readint(s1);
int j=0;
while(*(s1+j)!=32)j++;
j++;
int m=readint(s1+j);
// printf("n=%d m=%d\n",n,m);
free(s1);
char* s2=(char*)malloc(sizeof(char)*NS);
char* s3=(char*)malloc(sizeof(char)*NT);
for(int i=0;i<n;i++){
fgets(s2+i*6,8,stdin);
}
for(int i=0;i<m;i++){
fgets(s3+i*3,5,stdin);
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int flag=1;
for(int k=0;k<3;k++){
if (*(s2+i*6+3+k)!=*(s3+j*3+k)){
flag=0;
break;
}
if (flag==0)break;
}
if (flag==1)ans++;
}
}
printf("%d\n",ans);
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;
}
WAになるテストケースを見てみると、tの要素に重複するものがある。つまり、この問題で問われているのは、「Sの要素のうち、tの要素のいずれかと一致するものがいくつあるか。」なので、s[i]がtの要素のうち2つ以上に一致しても、それは一回とか添えなければいけないのである。
すると、まずはtをユニークな配列に作り直さなければならないのか、これをCでやるとなると意外と面倒だなど思いつつ、まずはrubyで書いたときはどうしたか見てみることになる。すると、何か特別な処理をしているようには見えない。これは一体どういうことだ、としばらく悩んだ。(rubyでのコードを書いたのは一年近く前のことなので、その特に何を考えていたかなど覚えていない。)
しばらくして、ようやく、rubyで書いたコードでは、一致するものが見つかった時点でtの要素を回すループを抜けていることに気づく。こうすればよかったのが。意外と単純な解法があった。(なお、rubyではuniqという便利なメソッドがあるので、tを重複要素の無いものにすることも簡単にできる。)それでやり直してACになったのが以下。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 20
#define NS 8000
#define NT 5000
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
fgets(s1,N1,stdin);
int n=readint(s1);
int j=0;
while(*(s1+j)!=32)j++;
j++;
int m=readint(s1+j);
// printf("n=%d m=%d\n",n,m);
free(s1);
char* s2=(char*)malloc(sizeof(char)*NS);
char* s3=(char*)malloc(sizeof(char)*NT);
for(int i=0;i<n;i++){
fgets(s2+i*6,8,stdin);
}
for(int i=0;i<m;i++){
fgets(s3+i*3,5,stdin);
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int flag=1;
for(int k=0;k<3;k++){
if (*(s2+i*6+3+k)!=*(s3+j*3+k)){
flag=0;
break;
}
if (flag==0)break;
}
if (flag==1){
ans++;
break;
}
}
}
printf("%d\n",ans);
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;
}
列ごとに特定の値の要素を数える
ABC274-B
問題概要
要素が#または.である行列が与えられる。各列の#の数を順に出力せよ
解答
n,m=gets.chomp.split(" ").map(&:to_i)
a=[]
ans=Array.new(m,0)
n.times do |i|
a[i]=gets.chomp.split("").to_a
m.times do |j|
if a[i][j]=="#"
ans[j]+=1
end
end
end
puts ans.join(" ")
上が本番で提出したコード
他のやり方としては、転置行列を作って、各行の要素数を数えるというものも考えられる。そうすると、Arrayクラスのcountメソッドが使える。
n,m=gets.chomp.split(" ").map(&:to_i)
a=[]
b=Array.new(m){Array.new(n,"")}
n.times do |i|
a[i]=gets.chomp.split("").to_a
m.times do |j|
b[j][i]=a[i][j]
end
end
m.times do |i|
print b[i].count("#")
if i!=m-1
print(" ")
end
end
puts ""
ただ、最初のコードの実行時間が285msなのに対し、下のコード475msと、実行時間が約1.7倍に増えている。そのうえメモリ使用量も4%くらい増えているから、本番で敢えてこれを使うメリットはないだろう。
Cでやったのが以下。
void print_ivector(int* a,int n);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 1e6
int main(void){
char* s=(char*)malloc(sizeof(char)*N);
fgets(s,N,stdin);
int h=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int w=readint(s+i);
free(s);
//printf("%d %d\n",h,w);
char* s2=(char*)malloc(sizeof(char)*N+2);
for(int j=0;j<h;j++){
char* t=(char*)malloc(sizeof(char)*(w+2));
fgets(t,w+2,stdin);
for(int k=0;k<w;k++)*(s2+j*w+k)=*(t+k);
}
/*
for(int j=0;j<h;j++){
for(int k=0;k<w;k++){
printf("%c",*(s2+j*w+k));
}
printf("\n");
}
*/
int* a=(int*)malloc(sizeof(int)*w);
for(int j=0;j<w;j++){
int temp=0;
for(int k=0;k<h;k++){
if (*(s2+k*w+j)==35)temp++;
}
*(a+j)=temp;
}
print_ivector(a,w);
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 print_ivector(int* a,int n){
for(int i=0;i<n-1;i++){
printf("%d ",*(a+i));
}
printf("%d\n",*(a+n-1));
}
文字列中の文字の出現回数を数える
ABC279-A
問題概要
vとwからなる文字列が与えられる。下に尖った個所が何カ所あるかを求めよ。
解答
s=gets.chomp.split("").to_a
ans=0
s.size.times do |i|
if s[i]=="v"
ans+=1
elsif s[i]=="w"
ans+=2
end
end
puts ans
上が本番の提出コード。一文字ずつ見ていって、vが出てきたら1、wが出てきたら2を答えに加算している。
Cでやったのが以下。
#include<stdio.h>
#include<stdlib.h>
#define N 102
int main(void){
int ans=0;
char* s=(char*)malloc(sizeof(char)*N);
fgets(s,N,stdin);
for(int n=0;n<N;n++){
if (*(s+n)==118){
ans+=1;
}
if (*(s+n)==119){
ans+=2;
}
}
printf("%d\n",ans);
return 0;
}
行列中の特定の要素の数を数える。
ABC280-A
問題概要
.または#を要素とする行列が与えられる。#が何個あるか出力せよ。
解答
h,w=gets.chomp.split(" ").map(&:to_i)
ans=0
h.times do |i|
t=gets.chomp.split("").to_a
c=0
w.times do |j|
if t[j]=="#"
c+=1
end
end
ans+=c
end
puts ans
上が本番の提出コード。Cでやったのが以下。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 7
int main(void){
char* s1=(char*)malloc(sizeof(char)*N);
fgets(s1,N,stdin);
int i=0;
int h=readint(s1);
while(*(s1+i)!=32)i++;
i++;
int w=readint(s1+i);
free(s1);
// printf("%d %d\n",h,w);
int ans=0;
for(i=0;i<h;i++){
char* s2=(char*)malloc(sizeof(char)*(w+2));
fgets(s2,(w+2),stdin);
for(int j=0;j<w;j++){
// printf("%c",*(s2+j));
if(*(s2+j)==35)ans++;
}
// printf("\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;
}
ABC295-C
問題概要
数字を要素とする配列が与えられる。同じ数字のペアは何個作れるか。
解答
「正の字カウント」を使えばよい。
n=gets.to_i
a=gets.chomp.split(" ").map(&:to_i)
h=Hash.new
a.each do |item|
if h.has_key?(item)
h[item]+=1
else
h[item]=1
end
end
count=0
h.each_value do |v|
count+=v/2
end
puts count
上が本番の提出コードCでやったのが以下。まずは、以下のコードでTLEになった。
typedef struct {
int key;
int v;
struct tn *l;
struct tn *r;
} tn;
void print_ivector(int* a,int n);
int tree_to_pa(tn* f, int* a1, int* a2);
tn* create_tn(int key);
void insert_tn(int key, tn *node);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 8
#define N 1e7
tn *root=NULL;
int cnt=0,ar_idx=0;
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);
free(s1);
char* s=(char*)malloc(sizeof(char)*N);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
fgets(s,N,stdin);
int* a=(int*)malloc(sizeof(int)*n);
if (a==NULL){
printf("memory allocation to a failed.\n");
exit(1);
}
int i=0,j=0;
for(;i<n-1;i++){
*(a+i)=readint(s+j);
while(*(s+j)!=32)j++;
j++;
}
*(a+i)=readint(s+j);
free(s);
// print_ivector(a,n);
for(int i=0;i<n;i++){
insert_tn(*(a+i),root);
}
free(a);
int *a1=(int*)malloc(sizeof(int)*cnt);
if (a1==NULL){
printf("memory allocation to a1 failed.\n");
exit(1);
}
int *a2=(int*)malloc(sizeof(int)*cnt);
if (a2==NULL){
printf("memory allocation to a2 failed.\n");
exit(1);
}
tree_to_pa(root,a1,a2);
int ans=0;
for(i=0;i<cnt;i++){
ans+= *(a2+i)/2;
}
// print_ivector(a1,cnt);
// print_ivector(a2,cnt);
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;
}
tn* create_tn(int key){
tn* neu;
neu=(tn*)malloc(sizeof(tn));
if(neu==NULL){
printf("Memory allocation failed.");
exit(1);
}
neu->l=NULL;
neu->r=NULL;
neu->key=key;cnt++;
neu->v=1;
return neu;
}
void insert_tn(int key, tn *node){
if(node==NULL){
root=create_tn(key);
return;
} else if (key == node->key){
(node->v)+=1;
return;
} else if (key < node->key){
if (node->l !=NULL){
insert_tn(key,node->l);
} else {
node->l = create_tn(key);
}
} else if (node->key < key){
if (node->r !=NULL){
insert_tn(key,node->r);
} else {
node->r = create_tn(key);
}
}
return;
}
int tree_to_pa(tn* f, int* a1, int* a2){
if(f->l!=NULL){
tree_to_pa(f->l,a1,a2);
}
*(a1+(ar_idx))=f->key;
*(a2+(ar_idx))=f->v;ar_idx++;
if(f->r!=NULL){
tree_to_pa(f->r,a1,a2);
}
}
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));
}
少し前にABC329-Bで二分木を使うコードを書いたので、それを少し修正して、二分木の葉にキーと値の二つを持たせ、数字をキーとするハッシュとして使えるようにした。
AtCoderでの実行結果の詳細を見ると、sortedという名の付いた最後4件のデータでTLEになっている。どうやら、二分木にソート済みのデータを入れると枝が一方向に伸び、探索にO(n)の時間がかかるというあの現象が起きているようだ。
決まった要素の出現回数、+同数の場合の処理
ABC301-A
問題概要
AとTからなる文字列が与えられる。AとTのどちらが多いか。ただし、同数の場合、先にその数に達した方を答えよ。
解答
出現する要素の種類が分かっているので、その要素をキーとするハッシュの値を加算していけばよい。同数の場合については、「文字列の最後の要素でない方」を答えればよい。
n=gets.to_i
s=gets.chomp
count=Hash.new
count["A"]=0
count["T"]=0
n.times do |i|
count[s[i]]+=1
end
if count["A"]>count["T"]
puts "A"
elsif count["T"]>count["A"]
puts "T"
else
if s[-1]=="T"
puts "A"
else
puts "T"
end
end
上が本番で提出したコード。Cで書いたのが以下。
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 102
int main(void){
int n,na=0,nt=0;
char *sn=(char*)malloc(sizeof(char)*5);
fgets(sn,5,stdin);
n=readint(sn);
// printf("%d\n",n);
char *s=(char*)malloc(sizeof(char)*N1);
fgets(s,N1,stdin);
// printf("%s\n",s);
for(int i=0;i<n;i++){
if (*(s+i)==65)na++;
else if (*(s+i)==84)nt++;
}
if (na>nt)printf("A\n");
else if (na<nt)printf("T\n");
else if (na==nt){
if (*(s+n-1)==65)printf("T\n");
else printf("A\n");
}
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;
}
ABC308-B
問題概要
文字列を要素とする配列が与えられる。その各要素は品目名であり、品目名と価格を対応させた表が与えられる。ただし価格表に載っていない品目もあり、その価格はデフォルト値となる。価格の合計を出力せよ。
解答
n,m=gets.chomp.split(" ").map(&:to_i)
c=gets.chomp.split(" ")
d=gets.chomp.split(" ")
p=gets.chomp.split(" ").map(&:to_i)
ans=0
n.times do |i|
if !d.include?(c[i])
k=p[0]
else
k=p[d.find_index(c[i])+1]
end
ans+=k
end
puts ans
Cでまず書いたのが以下。このコードは、sample1だけWAになった。
typedef struct {
int id;
char key[21];
int v;
struct tn *l;
struct tn *r;
} tn;
void print_tn(tn* tns, int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
void print_ivector(int* a,int n);
int tree_to_pa(tn* f, int* a1, int* a2);
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N1 9
#define N2 2102
#define N 100000002
tn* create_tn(int key);
void insert_tn(int key, tn *node);
tn *root=NULL;
int cnt=0,ar_idx=0;
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
if(s1==NULL){
printf("Memory allocation to s1 failed.");
exit(1);
}
fgets(s1,N1,stdin);
int i=0;
int n=readint(s1);
while(*(s1+i)!=32)i++;
i++;
int m=readint(s1+i);
// printf("n=%d m=%d\n",n,m);
free(s1);
char* s2=(char*)malloc(sizeof(char)*(21*n+1));
if(s2==NULL){
printf("Memory allocation to s2 failed.");
exit(1);
}
fgets(s2,(21*n+1),stdin);
// printf("s2=%s\n",s2);
char* s3=(char*)malloc(sizeof(char)*(21*m+1));
if(s3==NULL){
printf("Memory allocation to s3 failed.");
exit(1);
}
fgets(s3,(21*m+1),stdin);
// printf("s3=%s\n",s3);
char* s4=(char*)malloc(sizeof(char)*(6*m+1));
if(s4==NULL){
printf("Memory allocation to s4 failed.");
exit(1);
}
fgets(s4,6*(m+1)+1,stdin);
// printf("s4=%s\n",s4);
int* p=(int*)malloc(sizeof(int)*(m+1));
if (p==NULL){
printf("memory allocation to p failed.\n");
exit(1);
}
input_iarray(s4,p,m+1,6*m+1);
// print_ivector(p,m+1);
free(s4);
tn* arr=(tn*)malloc(sizeof(tn)*m);
if (arr==NULL){
printf("memory allocation to arr failed.\n");
exit(1);
}
int s3_idx=0;
i=0;
for(;i<m;i++){
char* temp=(char*)malloc(sizeof(char)*22);
if (temp==NULL){
printf("memory allocation to temp(%d) failed.\n",i);
exit(1);
}
int k=0;
// printf("s3+s3_idx=%s\n",s3+s3_idx);
while(*(s3+s3_idx)!=32 && *(s3+s3_idx)!=0 && *(s3+s3_idx)!='\n'){
*(temp+k)=*(s3+s3_idx); k++; s3_idx++;
}
// printf("temp(%d)=%s\n",i,temp);
((arr+cnt)->id)=cnt;
strcpy((arr+cnt)->key,temp);
((arr+cnt)->v)=*(p+cnt+1);
s3_idx++;
cnt++;
}
// print_tn(arr,m);
int total=0;
int s2_idx=0;
for(i=0;i<n;i++){
char* temp2=(char*)malloc(sizeof(char)*22);
if (temp2==NULL){
printf("memory allocation to temp2(%d) failed.\n",i);
exit(1);
}
int k=0;
// printf("s2+s2_idx=%s\n",s2+s2_idx);
while(*(s2+s2_idx)!=32 && *(s2+s2_idx)!=0 && *(s2+s2_idx)!='\n'){
*(temp2+k)=*(s2+s2_idx); k++; s2_idx++;
}
s2_idx++;
// printf("temp2(%d)=%s\n",i,temp2);
int flag=0,price=0;
for(int j=0;j<m;j++){
if(strcmp(temp2,(arr+j)->key)==0){
flag=1;
price=(arr+j)->v;
break;
}
}
if(flag==1){
// printf("%s: price=%d\n",temp2,price);
total+=price;
}else{
// printf("%s: price=%d\n",temp2,*p);
total+=*p;
}
}
printf("%d\n",total);
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\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_tn(tn* tns, int n){
for(int i=0;i<n;i++){
printf("----\n");
printf("id=%d\n",(tns+i)->id);
printf("key=%s\n",(tns+i)->key);
printf("price=%d\n",(tns+i)->v);
}
}
AtCoderで提出するとsample1の一つだけWAになるのだが、sample1のデータを入れて実行すると、正しい答えが出ている。原因が分からないので、StackOverflowで質問した。
actorbugさんから頂いた回答によると、strcmpで比較するために文字列を入れたtemp,temp2の最後に\0を書き込んでいなかったのが原因らしい。(他にも幾つか修正すべき点を指摘していただいた。)
ちなみに、この比較の部分は、最初はCの標準関数のstrcmpを使うのではなく、自作関数で比較しようとしたのだが、構造体のメンバである文字列のアドレスを主とルする方法が分からず、strcmpを使うことにしたのだった。
指摘されたとおりに修正したら、全てACになった。そのコードが以下。
typedef struct {
int id;
char key[21];
int v;
struct tn *l;
struct tn *r;
} tn;
void print_tn(tn* tns, int n);
void input_iarray(char* s,int* a,int n,int imax);
int readint(char *s);
void print_ivector(int* a,int n);
int tree_to_pa(tn* f, int* a1, int* a2);
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N1 9
#define N2 2102
#define N 100000002
tn* create_tn(int key);
void insert_tn(int key, tn *node);
tn *root=NULL;
int cnt=0,ar_idx=0;
int main(void){
char* s1=(char*)malloc(sizeof(char)*N1);
if(s1==NULL){
printf("Memory allocation to s1 failed.");
exit(1);
}
fgets(s1,N1,stdin);
int i=0;
int n=readint(s1);
while(*(s1+i)!=32)i++;
i++;
int m=readint(s1+i);
// printf("n=%d m=%d\n",n,m);
free(s1);
char* s2=(char*)malloc(sizeof(char)*(21*n+1));
if(s2==NULL){
printf("Memory allocation to s2 failed.");
exit(1);
}
fgets(s2,(21*n+1),stdin);
// printf("s2=%s\n",s2);
char* s3=(char*)malloc(sizeof(char)*(21*m+1));
if(s3==NULL){
printf("Memory allocation to s3 failed.");
exit(1);
}
fgets(s3,(21*m+1),stdin);
// printf("s3=%s\n",s3);
char* s4=(char*)malloc(sizeof(char)*(6*(m+1)+1));
if(s4==NULL){
printf("Memory allocation to s4 failed.");
exit(1);
}
fgets(s4,6*(m+1)+1,stdin);
// printf("s4=%s\n",s4);
int* p=(int*)malloc(sizeof(int)*(m+1));
if (p==NULL){
printf("memory allocation to p failed.\n");
exit(1);
}
input_iarray(s4,p,m+1,6*m+1);
// print_ivector(p,m+1);
free(s4);
tn* arr=(tn*)malloc(sizeof(tn)*m);
if (arr==NULL){
printf("memory allocation to arr failed.\n");
exit(1);
}
int s3_idx=0;
i=0;
for(;i<m;i++){
char* temp=(char*)malloc(sizeof(char)*22);
if (temp==NULL){
printf("memory allocation to temp(%d) failed.\n",i);
exit(1);
}
int k=0;
// printf("s3+s3_idx=%s\n",s3+s3_idx);
while(*(s3+s3_idx)!=32 && *(s3+s3_idx)!=0 && *(s3+s3_idx)!='\n'){
*(temp+k)=*(s3+s3_idx); k++; s3_idx++;
}
*(temp+k)=0;
// printf("temp(%d)=%s\n",i,temp);
((arr+cnt)->id)=cnt;
strcpy((arr+cnt)->key,temp);
free(temp);
((arr+cnt)->v)=*(p+cnt+1);
s3_idx++;
cnt++;
}
free(s3);
// print_tn(arr,m);
int total=0;
int s2_idx=0;
for(i=0;i<n;i++){
char* temp2=(char*)malloc(sizeof(char)*22);
if (temp2==NULL){
printf("memory allocation to temp2(%d) failed.\n",i);
exit(1);
}
int k=0;
// printf("s2+s2_idx=%s\n",s2+s2_idx);
while(*(s2+s2_idx)!=32 && *(s2+s2_idx)!=0 && *(s2+s2_idx)!='\n'){
*(temp2+k)=*(s2+s2_idx); k++; s2_idx++;
}
*(temp2+k)=0;
s2_idx++;
// printf("temp2(%d)=%s\n",i,temp2);
int flag=0,price=0;
for(int j=0;j<m;j++){
if(strcmp(temp2,(arr+j)->key)==0){
flag=1;
price=(arr+j)->v;
break;
}
}
free(temp2);
if(flag==1){
// printf("%s: price=%d\n",temp2,price);
total+=price;
}else{
// printf("%s: price=%d\n",temp2,*p);
total+=*p;
}
}
free(s2);
free(arr);
free(p);
printf("%d\n",total);
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\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_tn(tn* tns, int n){
for(int i=0;i<n;i++){
printf("----\n");
printf("id=%d\n",(tns+i)->id);
printf("key=%s\n",(tns+i)->key);
printf("price=%d\n",(tns+i)->v);
}
}
ハッシュ
ABC319-A
問題概要
文字列と数値の組の表がある。表中の文字列の一つが与えられるので、それに対応する数値を出力せよ。
解答
data=<<EOF
tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481tourist 3858
EOF
d=data.split("\n")
da=Array.new(d.size){Array.new(2)}
i=0
d.each do |it|
s,n=it.split(" ")
da[i][0]=s
da[i][1]=n.to_i
i+=1
end
s=gets.chomp
da.each do |dd|
if dd[0]==s
puts dd[1]
exit
end
end
上が本番の提出コード。Cでやったのが以下。
typedef struct {
char key[21];
int v;
} tn;
void print_tn(tn* tns, int n);
int readint(char *s);
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N1 10
#define N2 12
#define N 100000002
int cnt=0,ar_idx=0;
int main(void){
char s1[]="tourist 3858,ksun48 3679,Benq 3658,Um_nik 3648,apiad 3638,Stonefeang 3630,ecnerwala 3613,mnbvmar 3555,newbiedmy 3516,semiexp 3481";
// printf("%s\n",s1);
tn* arr=(tn*)malloc(sizeof(tn)*N1);
if (arr==NULL){
printf("memory allocation to arr failed.\n");
exit(1);
}
int s1_idx=0,i=0;
for(i=0;i<N1;i++){
char* temp=(char*)malloc(sizeof(char)*22);
if (temp==NULL){
printf("memory allocation to temp(%d) failed.\n",i);
exit(1);
}
int k=0;
while(*(s1+s1_idx)!=32){
*(temp+k)=*(s1+s1_idx); k++; s1_idx++;
}
*(temp+k)=0;
strcpy((arr+i)->key,temp);
free(temp);
s1_idx++;
int point=readint(s1+s1_idx);
(arr+i)->v=point;
if (i!=N1-1){
while(*(s1+s1_idx)>=48 && *(s1+s1_idx)<=57){
s1_idx++;
}
while(*(s1+s1_idx)==44)s1_idx++;
}
}
// print_tn(arr,N1);
char* s2=(char*)malloc(sizeof(char)*N2);
if (s2==NULL){
printf("memory allocation to s2 failed.\n");
exit(1);
}
fgets(s2,N2,stdin);
char* temp2=(char*)malloc(sizeof(char)*(N2+1));
if (temp2==NULL){
printf("memory allocation to temp2 failed.\n");
exit(1);
}
int s2_idx=0,k=0;
while((*(s2+s2_idx)>=48 && *(s2+s2_idx)<=122)){
*(temp2+k)=*(s2+s2_idx); s2_idx++; k++;
}
*(temp2+k)=0;
// printf("%s\n",temp2);
int flag=0;
for(i=0;i<N1;i++){
if (strcmp((arr+i)->key,temp2)==0){
printf("%d",(arr+i)->v);
flag=1;
exit(0);
}
}
if (flag==0){
printf("name couldn't be found.\n");
exit(1);
}
free(arr);
free(temp2);
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_tn(tn* tns, int n){
for(int i=0;i<n;i++){
printf("----\n");
printf("key=%s\n",(tns+i)->key);
printf("point=%d\n",(tns+i)->v);
}
}
ABC325-B
問題概要
拠点iの標準時は世界標準時+w[i]で、x[i]人が所属している。(w[i]は整数。)整数時から始まる1時間に各拠点の標準時における9時から18時が完全に含まれる拠点の所属員を累計するとき、その値の最大値を求めよ。
解答
n=gets.to_i
x=[]
w=[]
n.times do |i|
x[i],w[i]=gets.chomp.split(" ").map(&:to_i)
end
h=Hash.new
(0..23).each do |i|
t=0
n.times do |j|
st=i+w[j]
if st>24
st-=24
end
if st>=9 && st<=17
t+=x[j]
end
end
h[i]=t
end
max=0
h.each {|key, value|
if value > max
max=value
end
}
puts max
この問題では開始時間は整数時の24通りに限られるので、0..23時をそれぞれ開始時間としたときに開始時間の現地標準時が9時から17時になる拠点の所属員数の累計値を、開始時間をキー、対応する累計値を値とするハッシュにまとめ、値の最大値を出力すればよい。
上が本番の提出コード。Cでやったのが以下。
typedef struct {
int hour;
int num;
} table;
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 6
#define N2 12
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);
free(s1);
int* w=(int*)malloc(sizeof(int)*n);
if(w==NULL){
printf("memory allocation to w failed\n");
exit(1);
}
int* x=(int*)malloc(sizeof(int)*n);
if(x==NULL){
printf("memory allocation to x failed\n");
exit(1);
}
for(int i=0;i<n;i++){
char* s2=(char*)malloc(sizeof(char)*N2);
if(s2==NULL){
printf("memory allocation to w failed\n");
exit(1);
}
fgets(s2,N2,stdin);
*(x+i)=readint(s2);
int j=0;
while(*(s2+j)!=32)j++;
j++;
*(w+i)=readint(s2+j);
// printf("w[%d]=%d x[%d]=%d\n",i,*(w+i),i,*(x+i));
free(s2);
}
table* t=(table*)malloc(sizeof(table)*24);
if(t==NULL){
printf("memory allocation to t failed\n");
exit(1);
}
for(int i=0;i<24;i++){
(t+i)->hour=i;
}
for(int i=0;i<n;i++){
int start=9;
int end=17;
start=((start+*(w+i))%24);
end=((end+*(w+i))%24);
// printf("start=%d end=%d\n",start,end);
if(start<end){
for(int j=start;j<=end;j++){
((t+j)->num) += *(x+i);
}
}else{
for(int j=start;j<=23;j++){
((t+j)->num) += *(x+i);
}
for(int j=0;j<=end;j++){
((t+j)->num) += *(x+i);
}
}
}
int max=0;
for(int i=0;i<24;i++){
//printf("from %d: %d person\n",i,(t+i)->num);
if ((t+i)->num > max){
max=(t+i)->num;
}
}
printf("%d\n",max);
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;
}
ほぼ出来上がったころに気づいたのだが、構造体tableのhourはインデックスと同じなので、構造体を作らなくても単なる配列でもよかった。
複数の最大値
ABC329-D
問題概要
1からnまでの整数のいずれかを要素とする配列(要素数m)が与えられる。i番目までの中で最も多く出現している数(ただし、最も多く出現している数が複数あるときは、そのうち最も小さい数)を出力せよ。
解答
n,mは最大で2*10^5なので、ほぼ二重ループになる下記のコードでTLEになることは分かっていたが、この日は開始から約30分後に参加登録したにもかかわらず、A,B問題はおろかC問題まであっさり解け、それで終了までかなり時間があったため、これもやってみることに。あくまでも、小規模なデータならこれで解けるということで書いたコードである。
n,m=gets.chomp.split(" ").map(&:to_i)
a=gets.chomp.split(" ").map(&:to_i)
c=Hash.new
(0...m).each do |i|
if c.has_key?(a[i])
c[a[i]]+=1
else
c[a[i]]=1
end
max=0
idxs=[]
c.each do |k,v|
if v>max
idxs.clear
idxs.push(k)
max=v
elsif v==max
idxs.push(k)
end
end
puts idxs.min
end
i番目まで数えた時の各要素の出現回数を、要素の値をキー、出現回数を値とするハッシュで保持、最大回数出現する要素を配列に記録し、その配列の最小値を出力している。
0 件のコメント:
コメントを投稿