競プロ参加日記006 AtCoder Beginner Contest 174(ABC174) 参加

ぬるから

ぬるからです。
久々ですが、Atcoderのコンテストに参加しました。
https://atcoder.jp/contests/abc174

・全体的に

C問題難しい！！！

・A問題　Air Conditioner

https://atcoder.jp/contests/abc174/tasks/abc174_a
書いてある通り実装するだけです。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   int X;
   cin>>X;
   if(X>=30) cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
}

・B問題　Distance

https://atcoder.jp/contests/abc174/tasks/abc174_b
変にsqrtを使うと誤差が怖いので、両辺二乗し
D^2>=p^2+q^2
としたほうが安全です。制約的にlong longならオーバーフローもなさそうです。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   int N,K;
   int c=0;
   cin>>N>>K;
   K=K*K;
   for(int i=0;i<N;i++){
       int x,y;
       cin>>x>>y;
       int d=x*x+y*y;
       if(d<=K) c++;
   }
   cout<<c<<endl;
}

・C問題　Repsept

https://atcoder.jp/contests/abc174/tasks/abc174_c
C問題ってたまにハマるとやばい問題が出てきますね。コンテスト中に解けませんでした。

問題文の数列は、
a[n+1]=a[n]*10+7　(a[1]=7)
と言い換えることができます。また、この問題はKで割り切れるかどうかを調べたいだけなため、
a[n+1]=(a[n]*10+7)%K (a[1]=7%K)
としても問題ありません。
a[n]==0となれば、その時のnが答えです。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   int K;
   cin>>K;
   int m=7%K;
   int c=1;
   while(1){
       if(m==0) break;
       if(c!=1&&c>K+100){
           c=-1;
           break;
       }
       m*=10;
       m+=7;
       m%=K;
       c++;
   }
   cout<<c<<endl;
}

・D問題　Alter Altar

https://atcoder.jp/contests/abc174/tasks/abc174_d
問題文がややこしいですが、要するにRRR....WWW...という文字列を作る問題です。
操作が二つあるのですが、実は色を変える操作は必要ありません。というのも、色を変えて救える白い石は1個が最大ですが、場所変更は最大2個の白い石が救えるからです。
※WRWWWRW
　左から二つ目のRをWに変えてもWWWWWRWと一番左のWが助かるだけですが、
　一番左のWと右から二番目のRを場所交換するとRRWWWWWとなり、一番左にあったWと右から三番目のWの二つ助かります。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   int N;
   string c;
   cin>>N;
   cin>>c;
   int wc=0;
   for(int i=0;i<N;i++){
       if(c[i]=='W') wc++;
   }
   int n=0;
   for(int i=N-1;i>N-1-wc;i--){
       if(c[i]=='R') n++;
   }
   cout<<n<<endl;
}

・E問題　Logs

https://atcoder.jp/contests/abc174/tasks/abc174_e
ど典型な問題。(というか、SRM329に似た問題があったような)
丸太を長さL以下にするために、何回のカットが必要かは
A/L+(A%L!=0)-1
を各Aiに対してシグマを取ることで分かります。なので、K回以下で最大の長さをLにできるかはO(N)で分かります。
そこで、Lを1～Amaxの範囲で二分探索することでO(N*log(Amax))でLの最小値(=答え)を求めることができます。
最大の最小は二分探索が基本(らしい)。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   vector<int> log;
   int N,K;
   cin>>N>>K;
   for(int i=0;i<N;i++){
       int A;
       cin>>A;
       log.push_back(A);
   }
   int l=0;
   int r=LLONG_MAX;
   while(1){
       int m=(l+r)/2;
       if(m==0) break;
       int c=0;
       for(int i=0;i<log.size();i++){
           c+=log[i]/m+(log[i]%m!=0)-1;
       }
       if(c<=K){
           if(r==m) break;
           r=m;
       }
       else{
           if(l==m) break;
           l=m;
       }
   }
   cout<<r<<endl;
}

・F問題　Range Set Query

解きました。

・最後に

青色になりたいので精進します...

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