AtCoder Beginner Contest 120(ABC120) 解説

ARC108がズタボロだったので、忘れるためにAC埋めをしていきます！(ARCの参加記は気が向いたらで…)

A – Favorite Sound
B – K-th Common Divisor
C – Unification
D – Decayed Bridges

A – Favorite Sound

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

B円で聞ける回数はA/B回です。
ただ、これがC回を上回ってもC回しか聞きません。
上記を、if文なりminなりを使って書けばOKです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int A,B,C;
    cin>>A>>B>>C;
    cout<<min(B/A,C)<<endl;
}

B – K-th Common Divisor

B - K-th Common Divisor

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

制約がA,B<=100なので、線形探索で十分間に合います。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int A,B,K;
    cin>>A>>B>>K;
    for(int i=min(A,B);i>=0;i--){
        if(A%i==0&&B%i==0) K--;
        if(K==0) {
            cout<<i<<endl;
            break;
        }
    }
}

C – Unification

C - Unification

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ARC108のこれに似ています。

B - Abbreviate Fox

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ちょうど、このABCを潰す前に解説ACしたので同じ手法で解きました。
Abbreviate Foxではfoxを削っていましたが、今回は01か10を削っていきます。

#include<bits/stdc++.h>

using namespace std;

int main(){
    vector<char> v;
    string S;

    cin>>S;

    for(int i=0;i<S.size();i++){
        v.push_back(S[i]);
        if(v.size()>=2&&v[v.size()-1]!=v[v.size()-2]){
            v.pop_back();
            v.pop_back();
        }
    }

    cout<<S.size()-v.size()<<endl;
}

この解き方、ぜひ覚えておきたいですね。この手の問題がすごく楽に解けます。

D – Decayed Bridges

D - Decayed Bridges

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

i番目の橋が崩壊していくを逆から見ると、
M-i番目の橋が建築されていく
と言い換えることができます。
辺が増えていく場合、UnionFindが使えそうです。
具体的には、初期値N*(N-1)/2 (すべての頂点が互いに行けない)からスタートし、辺を付けた頂点が違うグループの場合、それぞれのグループの大きさの積を引いていけばいいです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    long long N,M;
    cin>>N>>M;
    int A[M],B[M];

    for(int i=0;i<M;i++){
        cin>>A[i]>>B[i];
    }


    long long c=N*(N-1)/2;
    dsu d(N+1);

    vector<long long> ans;
    ans.push_back(c);
    for(int i=M-1;i>=1;i--){
        if(!d.same(A[i],B[i])){
            c-=(long long)d.size(A[i])*(long long)d.size(B[i]);
            d.merge(A[i],B[i]);
        }
        ans.push_back(c);
    }

    for(int i=ans.size()-1;i>=0;i--){
        cout<<ans[i]<<endl;
    }
}

N<=10^5なので、答えが10^10くらいになることがあります。intではなくlong longにしましょう。(少しハマりました)