久々のABC埋めですが、ぼちぼち再開しようかと思います。
A – Colorful Transceivers
A – Colorful Transceivers (atcoder.jp)
書かれている通りのことをします。
具体的には、A-C間の距離がD以下か、A-B間とB-C間の距離がD以下の場合はYesとします。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int A,B,C,D;
cin>>A>>B>>C>>D;
if(abs(A-C)<=D||(abs(A-B)<=D&&abs(B-C)<=D)){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
B – Exponential
X<=1000であるため、愚直に計算しても問題なさそうです。
全探索します。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int X;
cin>>X;
int ans=1;
for(int i=2;i<=X;i++){
for(int j=2;;j++){
if(pow(i,j)>X) break;
ans=max(ans,(int)pow(i,j));
}
}
cout<<ans<<endl;
}
C – K-th Substring
C – K-th Substring (atcoder.jp)
O(|s|^2=2.5*10^7)はいけそうと考え、愚直に全通り作る方法を実装しましたが…
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
string s;
int K;
cin>>s>>K;
set<string> ms;
for(int i=0;i<s.size();i++){
string tmp;
for(int j=0;i+j<s.size();j++){
tmp+=s[i+j];
ms.insert(tmp);
}
}
auto it=ms.begin();
for(int i=0;i<K-1;i++) it++;
cout<<*it<<endl;
}
TLEしました。
setのlog2の計算量が無視できないほど大きくなっているっぽいです。
問題文をよくよく見るとK<=5と、Kの値がかなり小さいです。
そのため、上記コードの2重forのjの部分は、高々5回程度回すだけで良いと考えられます。(6回以上回しても、辞書順で6番目より後ろになるのは明らかなため)
これで計算量がグッと減ります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
string s;
int K;
cin>>s>>K;
set<string> ms;
for(int i=0;i<s.size();i++){
string tmp;
for(int j=0;i+j<s.size()&&j<5;j++){
tmp+=s[i+j];
ms.insert(tmp);
}
}
auto it=ms.begin();
for(int i=0;i<K-1;i++) it++;
cout<<*it<<endl;
}
D – Equals
各整数を頂点とし、ペア同士に辺を張ると考えます。
このとき、同じグラフに属する数字はその中で自由に数字が入れ替えれると言えます。(バブルソートの要領で、端に数字を追いやっていくことで好きに並べていける)
“同じグラフに属する”ということでUnionFindが良さそうです。具体的には、ペア同士でmergeしながらUnionFindを作っていき、piとiが同じグループに属するかを見ていけば良いです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
int p[N];
for(int i=0;i<N;i++){
cin>>p[i];
}
dsu ds(N+1);
for(int i=0;i<M;i++){
int x,y;
cin>>x>>y;
ds.merge(x,y);
}
int ans=0;
for(int i=0;i<N;i++){
ans+=ds.same(i+1,p[i]);
}
cout<<ans<<endl;
}
コメント