A – Cats and Dogs
AがXより大きければ、Bを全て犬にしても猫をXにすることができません。
A+BがXより小さければ、Bをすべて猫にしても猫をXにすることができません。
上記以外の場合、Bを上手いこと調整すれば猫をXにすることができます。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int A,B,X;
cin>>A>>B>>X;
if(A>X||A+B<X) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
始めに解いたときはBを全パターン試してXになるか全探索しました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int A,B,X;
cin>>A>>B>>X;
for(int i=0;i<=B;i++){
if(A+i==X){
cout<<"YES"<<endl;
return 0;
}
}
cout<<"NO"<<endl;
}
Aはforが無くても解けるように作られている(はずな)ので、ちょっとやりすぎ感はありますが、条件の漏れでWAすることがないので個人的には好きです。
(条件のややこしい難しい問題は、全探索が許されない制約だったりするのですが…)
B – Toll Gates
右端か左端かに行けばよく、途中の料金所の数がコストになります。
行って戻ることに意味はありません。無駄に料金所を踏めばコストが無駄に増えます。
なので、右にずっと行くか左にずっと行くかのどっちかが答えになります。
そのため、Xから右にある料金所と、左にある料金所の数のうち、少ないほうが答えになります。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N,M,X;
cin>>N>>M>>X;
int c=0;
for(int i=0;i<M;i++){
int A;
cin>>A;
if(X<A) c++;
}
cout<<min(c,M-c)<<endl;
}
C – Many Medians
1 2 3 4 5 6 7 8 9 10
の数列から各値を消して中央値を観察します。
2 3 4 5 6 7 8 9 10 -> 6 1 3 4 5 6 7 8 9 10 -> 6 1 2 4 5 6 7 8 9 10 -> 6 1 2 3 5 6 7 8 9 10 -> 6 1 2 3 4 6 7 8 9 10 -> 6 1 2 3 4 5 7 8 9 10 -> 5 1 2 3 4 5 6 8 9 10 -> 5 1 2 3 4 5 6 7 9 10 -> 5 1 2 3 4 5 6 7 8 10 -> 5 1 2 3 4 5 6 7 8 9 -> 5
元の数列の左半分のどれかを消すと、6番目の数字(N/2+1番目)が、元の数列の右半分のどれかを消すと、5番目の数字(N/2番目)が中央値になっていることがわかります。
なので、この問題は消した数字が左半分か右半分のどちらに属するかを調べることでOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin>>N;
int Xs[N];
int X[N];
for(int i=0;i<N;i++){
cin>>X[i];
Xs[i]=X[i];
}
sort(Xs,Xs+N);
int l=Xs[N/2-1];
int h=Xs[N/2];
for(int i=0;i<N;i++){
if(X[i]<=l) cout<<h<<endl;
else cout<<l<<endl;
}
}
D – Binomial Coefficients
Combの特徴が理解できていれば、C`より簡単な問題です。
nCrの特徴として
- rが同じならnが大きいほうが値が大きい
->単純に掛け算が大きくなる。 - nが同じならrはn/2に近いほうが値が大きい
->n/2を超えると、掛け算より割り算の方が大きくなり、値が小さくなる。
の2つがあります。上記特徴をコードに落とし込めばOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int ans1=a[n-1];
cout<<ans1<<" ";
int ans2=a[0];
double dis=abs(ans1/2.0-a[0]);
for(int i=1;i<n-1;i++){
if(dis>abs(ans1/2.0-a[i])){
ans2=a[i];
dis=abs(ans1/2.0-a[i]);
}
}
cout<<ans2<<endl;
}
おわりに
前回のコンテスト(ABC182)でレートが1405になりました。
順位は4248位です。
アクティブユーザ(過去二年以内のコンテスト参加者)の数は、上記ランキングサイトによると65301人です。つまり、上位6.5%です。
色んなゲームをやってきましたが、ここまでランキングを上げたゲームは初めてです。やっぱり楽しいですね…。
ちなみに、青最下位の順位が2889位で上位4.4%です。
目標の青まで、あと1500人くらいに勝たないといけませんね…。頑張りましょう…。
コメント