今年もよろしくおねがいします。
(今年こそは青色に上がります！)
はじめに
AtCoder Beginner Contest 188 – AtCoder
全完できました！
レートも+57上がって、良いスタートを切ることができました。
A – Three-Point Shot
A – Three-Point Shot (atcoder.jp)
XとYの点差が2点以下であれば、スリーポイントを決めて勝つことができます。
逆に3点以上であれば、同点か入れても勝つことができません。
上記をそのまま実装すればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int X,Y;
cin>>X>>Y;
if(abs(X-Y)<3) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
B – Orthogonality
B – Orthogonality (atcoder.jp)
問題文に丁寧に計算方法が書いてあります。
その通り実装すればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
long long sum=0;
for(int i=0;i<N;i++){
int B;
cin>>B;
sum+=A[i]*B;
}
if(sum==0) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
C – ABC Tournament
C – ABC Tournament (atcoder.jp)
問題文に色々書いていますが、所謂普通の勝ち上がりトーナメントをしていき、準優勝を出力すればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int n=pow(2,N);
pair<int,int> A[n];
for(int i=0;i<n;i++){
int Ain;
cin>>Ain;
A[i]=make_pair(Ain,i+1);
}
while(n!=2){
pair<int,int> B[n];
for(int i=0;i<n;i+=2){
if(A[i].first<A[i+1].first){
B[i/2]=A[i+1];
}
else{
B[i/2]=A[i];
}
}
for(int i=0;i<n/2;i++){
A[i]=B[i];
}
n/=2;
}
if(A[0].first<A[1].first) cout<<A[0].second<<endl;
else cout<<A[1].second<<endl;
}
シミュレーションしなくても、トーナメントを左半分と右半分に分けた場合、決勝戦は左半分の中で一番レートが高い選手と、右半分の中で一番レートが高い選手になるはずです。
なので答えは、min(max(左半分),max(右半分))となります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int n=pow(2,N);
int A[n];
map<int,int> m;
int l=0,r=0;
for(int i=0;i<n/2;i++){
cin>>A[i];
m[A[i]]=i+1;
l=max(l,A[i]);
}
for(int i=n/2;i<n;i++){
cin>>A[i];
m[A[i]]=i+1;
r=max(r,A[i]);
}
cout<<m[min(l,r)]<<endl;;
}
D – Snuke Prime
imosをしたくなりますが、範囲が大きすぎるため単純にするとアウトです。
基本的にはimosの考え方ですが、料金が変わるタイミング(各サービスを利用する開始日と終了日)を中心に考えると解けます。
具体的には、料金が変わるタイミングをset等で管理し、日数の早い順に見ていくことで、あるタイミングからあるタイミングで”すぬけプライム”に加入していない場合のサービスの料金が分かるようになります。
このタイミングは2N個しかないため、タイミングごとにサービスの料金を計算し、”すぬけプライム”の料金と安いほうを合計金額に足していけばいいです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
long long C;
cin>>N>>C;
map<int,long long> m;
for(int i=0;i<N;i++){
int a,b;
long long c;
cin>>a>>b>>c;
m[a]+=c;
m[b+1]-=c;
}
long long ans=0;
long long cs=0;
auto it=m.begin();
while(it!=m.end()){
int fs=it->first;
it++;
int fe=it->first;
int lng=fe-fs;
it--;
cs+=it->second;
if(cs<C) ans+=cs*lng;
else ans+=C*lng;
it++;
}
cout<<ans<<endl;
}
E – Peddler
金は1回しか売買できません。
そのため、dp[各頂点][金を買っているかどうか]が最大になるように拡張ダイクストラ(っぽいこと)をしていけばOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
long long A[N+1];
for(int i=1;i<=N;i++){
cin>>A[i];
}
vector<int> v[N+1];
bool sf[N+1];
for(int i=0;i<M;i++){
int X,Y;
cin>>X>>Y;
v[X].push_back(Y);
}
long long ans=LLONG_MIN;
long long dp[N+1][2];
for(int i=0;i<=N;i++){
dp[i][0]=LLONG_MIN;
dp[i][1]=LLONG_MIN;
}
for(int i=1;i<=N;i++){
for(int j=0;j<2;j++){
for(int k=0;k<v[i].size();k++){
int t=v[i][k];
//cout<<i<<","<<t<<endl;
if(j==0){
dp[t][1]=max(dp[t][1],-A[i]);
}
else{
if(dp[i][1]==LLONG_MIN) continue;
dp[t][1]=max(dp[t][1],dp[i][1]);
}
if(dp[t][1]!=LLONG_MIN&&dp[t][1]+A[t]>dp[t][0]){
//cout<<i<<","<<t<<","<<dp[t][1]<<","<<A[t]<<endl;
dp[t][0]=dp[t][1]+A[t];
ans=max(ans,dp[t][0]);
}
}
}
}
cout<<ans<<endl;
}
上の拡張ダイクストラ(っぽいこと)を見ると分かると思いますが、買っていないパターンのメモ値(dp[i][0])を計算に使っていません。
1回しか売買できないため、売った後の金額は保持しておく必要がありません。(答えとしての保持だけで充分)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
long long A[N+1];
for(int i=1;i<=N;i++){
cin>>A[i];
}
vector<int> v[N+1];
bool sf[N+1];
for(int i=0;i<M;i++){
int X,Y;
cin>>X>>Y;
v[X].push_back(Y);
}
long long ans=LLONG_MIN;
long long dp[N+1];
for(int i=0;i<=N;i++){
dp[i]=LLONG_MIN;
}
for(int i=1;i<=N;i++){
for(int k=0;k<v[i].size();k++){
int t=v[i][k];
//cout<<i<<","<<t<<endl;
dp[t]=max(dp[t],-A[i]);
dp[t]=max(dp[t],dp[i]);
ans=max(ans,dp[t]+A[t]);
}
}
cout<<ans<<endl;
}
こんな感じに1次元のdpテーブルでまとめることができました。ここまで簡略化すると、拡張ダイクストラっぽさもなく、ただのdpという感じです。
F – +1-1×2
毎操作で3つ値が増えるため、単純にやるとTLEです。
X,Y<=10^18なので、メモ化でゴリ押すのもだめそうです。いくつか、状態遷移が減りそうな方法を考えました。
- Yから考えたほうが良さそう
- Y%2==1のときにY/2が使えないので、その分パターンが減りそう
- 遷移数が同じ場合、最小値*2より大きい値は捨てて良さそう
この2つをパッと思いつきましたが、それでもTLEでした。
最終的には以下のようなコードでACを取りました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long X,Y;
cin>>X>>Y;
if(X>Y){
cout<<X-Y<<endl;
return 0;
}
set<long long> s;
s.insert(Y);
long long c=0;
long long c2=LLONG_MAX;
while(1){
auto it=s.begin();
long long mn=*it;
set<long long> s2;
while(it!=s.end()){
//cout<<c<<","<<c2<<","<<*it<<endl;
if(mn*2<*it) break;
if(c>=c2){
cout<<c2<<endl;
return 0;
}
if(*it==X){
cout<<c<<endl;
return 0;
}
if(*it<X) c2=min(c2,c+X-*it);
else{
c2=min(c2,c+*it-X);
if(*it%2==0) s2.insert(*it/2);
else{
s2.insert(*it+1);
s2.insert(*it-1);
}
}
it++;
}
if(s2.empty()||c>=100000000){
cout<<c2<<endl;
break;
}
c++;
s=s2;
}
}
if(*it<X) c2=min(c2,c+X-*it);
else{
c2=min(c2,c+*it-X);
if(*it%2==0) s2.insert(*it/2);
else{
s2.insert(*it+1);
s2.insert(*it-1);
}
}
が遷移部分です。
足すことでしかXに合わせられない場合は足していきます。
ただ、他の遷移の方が早い可能性があるためc2という変数に一旦格納します。
そうでない場合、
c2=min(c2,c+*it-X);
引くだけでXに合わす答えをc2に格納
if(*it%2==0) s2.insert(*it/2);
else{
s2.insert(*it+1);
s2.insert(*it-1);
}
足す引くのパターンは既にやったので、後は割り算で一気にXに近づくパターンで遷移させます。
一時格納変数のc2が明らか低いと分かった時点でc2を答えに、割るパターンで小さくなった場合はそちらを答えにします。
計算量が読めなかったのですが、実行時間9msと意外と早く終わるそうです…。
おわりに
今年初のABC(ABC187は寝てました＞＜）でしたが、何とかいいスタートを切れました。
今年こそは青くなります！
コメント