競プロ参加日記019 AtCoder Beginner Contest 180

ぬるから

LPIC受けてたり、Kaggleでボコボコになってたり、

この辺りのゲームにはまってたせいで最近なかなか参加できませんでしたが、ABC180は何とか参加できました。

・結果

A,B,C,D,Eの5完で400位くらい。久々にしては上手くハマりました。

・A - box

問題の通りです。NからAを引いてBを足します。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
   int N,A,B;
   cin>>N>>A>>B;
   cout<<N-A+B<<endl;
}

・B - Various distances

これも問題文通り、3通りの距離を出力します。
sqrtが絡むため少し誤差が怖いですが、意識しなくてもAC取れました。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
   double m=0,y=0,t=0;
   double x;
   int N;
   cin>>N;
   while(N-->0){
       cin>>x;
       m+=abs(x);
       y+=x*x;
       t=max(t,abs(x));
   }
   y=sqrt(y);
   printf("%.16f\n%.16f\n%.16f\n",m,y,t);
}

・C - Cream puff

約数列挙です。ぐぐれば約数列挙のコードはたくさん出てくるので、それをペタっと張りました。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://qiita.com/DaikiSuyama/items/946fb4db8fb3cb04d27e
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define PB push_back //挿入
#define ALL(x) x.begin(),x.end()
using ll=long long;
vector<ll> divisors;//約数を格納する配列
void make_divisors(ll n){
   FOR(i,1,sqrt(n)){
       if(n%i==0){
           divisors.PB(i);
           if(i!=n/i){
               divisors.PB(n/i);
           }
       }
   }
   //約数の小さい順にソートしたい場合
   sort(ALL(divisors));
   //約数の大きい順にソートしたい場合
   //sort(ALL(divisors),greater<ll>());
}

int main(){
   ll N;
   cin>>N;
   make_divisors(N);
   for(int i=0;i<divisors.size();i++){
       cout<<divisors[i]<<endl;
   }
}

上記コードでは、実際に1～sqrt(N)までを確かめることで約数を列挙しています。aqrt(N)+1～Nの約数が漏れそうですが、

           if(i!=n/i){
               divisors.PB(n/i);
           }

とすることで漏れなく列挙できています。

・D - Takahashi Unevolved

久々にいろはちゃんを見かけた気がします。
A倍するかBを加えるかの2操作を任意数行い、XがYを超えないときの操作の最大数を求めます。
A倍に関しては、Xの値によって増加量が変わります。
XによってA倍かBを加えるのかを判定し、小さい増加量の方を選択します。

また、A倍の増加量は単調増加していくため、Bを加えるの方が増加量が小さいなら、その後ずっと小さいといえます。

なので、
・A倍の方が小さいならA倍する。を繰り返す。
・A倍の方が大きくなったら残り全部Bを加えるとして、割り算で求める。
※両方ともYを超えない程度までする。
をすればOKです。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
#include<boost/multiprecision/cpp_int.hpp> 
using namespace std;
using namespace boost::multiprecision;
int main(){
   cpp_int A,B,X,Y;
   cin>>X>>Y>>A>>B;
   cpp_int ans=0;
   while(X*(A-1)<B){
       if(X*A>=Y) break;
       X*=A;
       ans++;
   }
   cpp_int nokori=Y-X-1;
   ans+=nokori/B;
   cout<<ans<<endl;
}

オーバーフローが怖いので多倍長を使いました。桁数もそこまで増えないので時間的にも安心です。

・E - Traveling Salesman among Aerial Cities

Nの制約が少なく、2^17=131072と少ないため、bitで訪れた都市を管理しながら行うダイクストラで何とかなりそうです。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
/*
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
*/
int dat[131072][17];
int main(){
   int N;
   cin>>N;
   int x[N],y[N],z[N];
   for(int i=0;i<N;i++){
       cin>>x[i]>>y[i]>>z[i];
   }
   vector<pair<int,int>> e[N];
   for(int i=0;i<N;i++){
       for(int j=0;j<N;j++){
           if(i!=j){
               int mv=abs(x[j]-x[i])+abs(y[j]-y[i])+max(0,z[j]-z[i]);
               e[i].push_back(make_pair(j,mv));
           }
       }
   }
   for(int i=0;i<131072;i++){
       for(int j=0;j<N;j++){
           dat[i][j]=-1;
       }
   }
   queue<long long> qn,qd;
   qn.push(0);
   qd.push(1);
   dat[1][0]=0;
   while(!qn.empty()){
       int nn=qn.front();
       int nd=qd.front();
       qn.pop();
       qd.pop();
       for(int i=0;i<e[nn].size();i++){
           int to=e[nn][i].first;
           int mv=e[nn][i].second;
           int tod=nd|(1<<to);
           //cout<<"---"<<to<<","<<mv<<","<<tod<<endl;
           if(dat[tod][to]==-1||dat[nd][nn]+mv<dat[tod][to]){
               dat[tod][to]=dat[nd][nn]+mv;
               //cout<<to<<","<<tod<<","<<dat[nd][nn]+mv<<endl;
               qn.push(to);
               qd.push(tod);
           }
       }
   }
   cout<<dat[(int)pow(2,N)-1][0]<<endl;
}

・F - Unbranched

コンビネーションで頑張って通り数を求めるのだと考えましたが、立式できず...。

・終わりに

ネットのソースが充実していて、ぐぐればほぼ解答のコードが出るのは楽でいいですね...。
約数列挙とかソラで書こうとしたら、素因数分解して死んでたと思う...。

この記事が気に入ったらサポートをしてみませんか？