競プロ参加記030 AtCoder Beginner Contest 188 (ABC188)

Atcoder

今年もよろしくおねがいします。
(今年こそは青色に上がります!)

はじめに

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

D – Snuke Prime (atcoder.jp)

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

E – Peddler (atcoder.jp)

金は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

F – +1-1×2 (atcoder.jp)

毎操作で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は寝てました><)でしたが、何とかいいスタートを切れました。
今年こそは青くなります!

コメント

タイトルとURLをコピーしました