A – Entrance Examination
Tasks - AtCoder Beginner Contest 117
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
比率の問題です。世界BでX*t進むと、世界Aではt進むので
X*t:t=T:ans t*T=ans*X*t ans=T/X
となります。ちなみに、こんな計算しなくてもA問題なら入力例で何となくエスパーできます。
(入力例1:8 3 -> 2.66666667なので、何となく8/3だなぁと読めます)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
double T,X;
cin>>T>>X;
printf("%.12f\n",T/X);
}
B – Polygon
問題文の定理の通り実装しましょう。
定理 : 一番長い辺が他のN−1辺の長さの合計よりも真に短い場合に限り、条件を満たすN角形が描ける。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int sum=0;
int mx=0;
for(int i=0;i<N;i++){
int L;
cin>>L;
sum+=L;
mx=max(L,mx);
}
if(sum-mx>mx) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
C – Streamline
N個置いたコマが同じ位置にいないように置いたり移動するのが最適です。(マス目が足りなくて、置かなければいけない場合は仕方なし)
そのため、N個コマを置いた後の移動は線が繋がるようになるはずです。
N=1 A--B--C--D--E--F ※--間を移動する N=2 A--B--C D--E--F N=3 A--B C D--E--F N=4 A--B C D--E F ...
と、なります。また、上の図から各座標間の移動が1つずつ消えていることが分かります。
消せる移動場所は、各コマの初期配置や移動を調整することで任意の場所を消すことができます。よって、この問題の最適解は
各座標間の間隔が大きい順にN-1個消す。 残った間隔の和が答え
となります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
if(M==1){
cout<<"0"<<endl;
return 0;
}
int X[M];
for(int i=0;i<M;i++){
cin>>X[i];
}
sort(X,X+M);
vector<int> v;
for(int i=1;i<M;i++){
v.push_back(X[i]-X[i-1]);
}
sort(v.begin(),v.end());
int sum=0;
for(int i=0;i<(int)v.size()-N+1;i++){
sum+=v[i];
}
cout<<sum<<endl;
}
D – XXOR
XORが出る場合、2進数で考えると分かりやすいです。
入力例1:1 6 3 の場合 1 -> 001 6 -> 110 3 -> 011 を足す。ここで xor 111(7)をそれぞれにすると 1 xor 7 -> 110 6 xor 7 -> 001 3 xor 7 -> 100
となります。
下位1桁に注目した場合、1+0+1が0+1+0とxorでbit反転したことにより小さくなっています。
結論として、Xによって各桁を反転させる場合、1の数が”反転前>反転後”であるようなbitを1にするのが最適です。
今回、Kという制約がありますが大きい桁からKを超えない範囲でXを作っていけばOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N,K;
cin>>N>>K;
long long A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
long long k=K;
int tw=0;
while(k!=0){
k/=2;
tw++;
}
long long X=0;
for(long long i=tw-1;i>=0;i--){
long long oc=0;
for(int j=0;j<N;j++){
if((A[j]>>i)%2==1) oc++;
}
//cout<<oc<<endl;
if(oc<N-oc){
if(K-(1ll<<i)>=0){
K-=(1ll<<i);
X+=(1ll<<i);
}
}
//cout<<K<<","<<X<<endl;
}
long long ans=0;
for(int i=0;i<N;i++){
ans+=A[i]^X;
}
cout<<ans<<endl;
}
if(K-(1ll<<i)>=0){
K-=(1ll<<i);
X+=(1ll<<i);
}
1llのllが無ければ、int型と見なされてover flowします。
llを付けて明示的にlong long型にしましょう。
コメント