競プロ参加日記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
解きました。
・最後に
青色になりたいので精進します...
この記事が気に入ったらサポートをしてみませんか?