ABC238-A
問題概要
2^n > n^2 か。
解答
n=gets.to_i
if n==1 || n>4 then
puts "Yes"
else
puts "No"
end
上がコンテスト中に提出したコード。(2022-02-05 21:11:21)
Cで書いたのが以下。(2024-12-10 11:39:44)
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 12
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int n=readint(s);
free(s);
if(n==1 || n>4){
printf("Yes\n");
}else{
printf("No\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;
}
グラフを書いてみると明らかなように、nが少し大きくなると指数関数の方が平方よりもずっと大きくなる。(高2の頃にやったことだ。実数 x について極限を取ると、a \gt 1 のとき、 \lim_{x \to ∞}\frac{a^x}{x^a} = ∞ である。)
| n | 2^n | n^2 |
| 1 | 2 | 1 |
| 2 | 4 | 4 |
| 3 | 8 | 9 |
| 4 | 16 | 16 |
| 5 | 32 | 25 |
| 6 | 64 | 36 |
| 7 | 128 | 49 |
| 8 | 256 | 64 |
| 9 | 512 | 81 |
| 10 | 1024 | 100 |
n=10までを表にすると上のようになる。常に 2^n の方が大きくなるのは n=5 からだが、その前に n=1 の時にも 2^n の方が大きくなっていることに注意が必要。Rubyで書いたコードもCで書いたコードも上の表を念頭に場合分けして書いている。制約上nは最大で10^9なので、実際に2^nやn^2を計算するのはRubyでならともかくCでは無理。n=32で既に2^nはint型で扱える範囲を超えてしまうのだ。
確率
ABC242-A
問題概要
1からnまでの数がある。この数から、小さい順にa個選び、続いて、a+1からbまでの数のうちc個をランダムに選ぶ。ある数xが選ばれる確率を求めよ。
解答
a,b,c,x=gets.chomp.split(" ").map(&:to_i)
p=0.0
if x<=a
p=1.0
elsif
x>b
p=0.0
else
p=c/(b-a).to_f
end
puts p
上がまずコンテスト中に提出したコード。(2022-03-05 21:08:04)
ところで、この日はなぜかA問題でコンテスト中に同じRubyのコードを2回回提出している。その二番目が以下。(2022-03-05 21:09:46)
a,b,c,x=gets.chomp.split(" ").map(&:to_i)
p=0.0
if x<=a
p=1.0
elsif
x>b
p=0.0
else
p=c/(b-a).to_f
end
puts p
先のコードと比べると、xがa以下かbより大のときに代入する1と0が整数か小数かの違いだけなのだが、それだけで実行速度が61ms から 137ms へと大幅に遅くなっている。
Cで書いたのが以下。(2025-01-03 19:35:10)
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 21
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int a=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int b=readint(s+i);
i++;
while(*(s+i)!=32)i++;
i++;
int c=readint(s+i);
while(*(s+i)!=32)i++;
i++;
int x=readint(s+i);
free(s);
// printf("a=%d b=%d c=%d x=%d\n",a,b,c,x);
double p=0;
if (x<=a)p=1.0;
else if (x<=b)p=(double)c/(b-a);
printf("%lf\n",p);
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;
}
周期算
ABC243-A
問題概要
初期値がVの数値を、3個単位周期の数列a,b,c,a,b,c,...に従い、k回目にはその数列の第k項の数を減算していく。数値が0未満になるのはいつか。(それぞれ数aを減算した時に0未満になるならばF,bを減算した時ならばM,cを減算した時ならばTを出力。)
解答
v,a,b,c=gets.chomp.split(" ").map(&:to_i)
t=a+b+c
v=v%t
if v<a
puts "F"
elsif v<a+b
puts "M"
else
puts "T"
end
上が、コンテスト中に提出したコード。(2022-03-12 21:06:08)
Cで書いたのが以下。(2025-01-03 21:15:30 )
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 29
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int v=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int a=readint(s+i);
i++;
while(*(s+i)!=32)i++;
i++;
int b=readint(s+i);
while(*(s+i)!=32)i++;
i++;
int c=readint(s+i);
free(s);
// printf("a=%d b=%d c=%d v=%d\n",a,b,c,v);
int t=a+b+c;
int r=v%t;
if (r-a<0)printf("F");
else if (r-a-b<0)printf("M");
else printf("T");
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;
}
ABC245-A
問題概要
a時b分とc時d分1秒とでどちらが早い時刻か判定せよ。
解答
a=gets.chomp.split(" ").map(&:to_i)
ta=a[0]*3600+a[1]*60
ao=a[2]*3600+a[3]*60+1
if ta<ao
puts "Takahashi"
else
puts "Aoki"
end
これが、コンテスト中に提出したコード。(2022-03-26 21:06:19)
Cで書いたのが以下。(2025-01-04 23:42:51)
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 21
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int a=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int b=readint(s+i);
i++;
while(*(s+i)!=32)i++;
i++;
int c=readint(s+i);
while(*(s+i)!=32)i++;
i++;
int d=readint(s+i);
free(s);
// printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
int taka=3600*a+60*b;
int ao=3600*c+60*d+1;
if(taka<ao)printf("Takahashi\n");
else printf("Aoki\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;
}
場合分け
ABC249-A
問題概要
- 甲は「A 秒間 B (m/s)で進み、C 秒間停止する」ことを繰り返す。
- 乙は「D 秒間 E (m/s)で進み、F 秒間停止する」ことを繰り返す。
解答
a,b,c,d,e,f,x=gets.chomp.split(" ").to_a.map(&:to_i)
taka=0
aoki=0
n1,r1=x.divmod(a+c)
if r1>=a
taka=(n1+1)*a*b
else
taka=(n1*a+r1)*b
end
t2=0
n2,r2=x.divmod(d+f)
if r2>=d
aoki=(n2+1)*d*e
else
aoki=(n2*d+r2)*e
end
#p [taka,aoki]
if taka==aoki
puts "Draw"
elsif taka>aoki
puts "Takahashi"
else
puts "Aoki"
end
上がコンテスト中に提出したコード。(2022-04-23 21:25:57)
Cで書いたコードは以下。(2025-02-12 22:50:12)
#define N1 29
int readint(char *s);
int min(int a,int b);
#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 a=readint(s1);
int i=0;
while(*(s1+i)!=32)i++;
i++;
int b=readint(s1+i);
while(*(s1+i)!=32)i++;
i++;
int c=readint(s1+i);
while(*(s1+i)!=32)i++;
i++;
int d=readint(s1+i);
while(*(s1+i)!=32)i++;
i++;
int e=readint(s1+i);
while(*(s1+i)!=32)i++;
i++;
int f=readint(s1+i);
while(*(s1+i)!=32)i++;
i++;
int x=readint(s1+i);
// printf("a=%d b=%d c=%d d=%d e=%d f=%d x=%d\n",a,b,c,d,e,f,x);
int q1=x/(a+c); int r1=x%(a+c);
int q2=x/(d+f); int r2=x%(d+f);
int takahashi=q1*a*b+min(r1,a)*b;
int aoki=q2*d*e+min(r2,d)*e;
// printf("Takahashi=%d\n",takahashi);
// printf("Aoki=%d\n",aoki);
if(takahashi>aoki){
printf("Takahashi\n");
}else if(takahashi==aoki){
printf("Draw\n");
}else{
printf("Aoki\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 min(int a,int b){
if(a<b)return a;
else return b;
}
中学受験の周期算でも割とあるパターンの問題なのだが、こういう、「進む」「休む」を繰り返す場合には、進んだ時間と休んだ時間をまとめて一周期として、これが何周期あるかを考える。まず甲について、進んだ距離を計算する。全体の時間xを一周期の時間(a+c)で割り、商がnになったとして、余りの時間が一周期に進む時間a以上ならば、全体としてn+1周期分進んでいることになる。余りがaよりも小さければ、それは端数の時間として秒単位で加算して、全体でn周期分+(x%(a+c))秒間進んでいることになる。最後はこの秒数に秒速をかければ進んだ距離が求められる。乙についても同様に進んだ距離を求め、両者を比較すればよい。
