🔵
【ABC372】AtCoder Beginner Contest 372【C++】

2024/09/22に公開
C++
 コンテスト名ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）

 コンテストURLhttps://atcoder.jp/contests/abc372

 開催日2024/09/21 21:00-22:40

 A: delete .
解法
文字列 S を前から順番に判定する

. 以外ならそのまま出力する
ABC372A.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin >> s;

    for(int i=0; i<s.size(); i++){
        if(s[i]!='.'){
            cout << s[i];
        }
    }
    cout << endl;
    
    return 0;
}

 B: 3^A
解法
大きいほうから貪欲に決定していく

3^{10}, \cdots, 3^0 の順にそれぞれいくつ必要かを計算する
ABC372B.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int m;
    cin >> m;

    int cnt = 0;
    int x = 1;
    while(true){
        if(x*3<=m){
            x *= 3;
            cnt++;
        }else{
            break;
        }
    }

    vector<int> ans;
    while(m){
        for(int i=0; i<m/x; i++){
            ans.push_back(cnt);
        }
        m %= x;
        x /= 3;
        cnt--;
    }

    cout << ans.size() << endl;
    for(int i=0; i<ans.size(); i++){
        if(i){
            cout << " ";
        }
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

 C: Count ABC Again
解法
変更される文字の前後だけを確認すればよい
最初に文字列 S に文字列 ABC が部分文字列として何箇所含まれるかを計算しておく
ABC372C.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(){
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    int cnt = 0;
    for(int i=0; i<s.size()-2; i++){
        if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C'){
            cnt++;
        }
    }

    int x;
    char c;
    for(int i=0; i<q; i++){
        cin >> x >> c;
        x--;

        if(x<s.size()-2 && s[x]=='A' && s[x+1]=='B' && s[x+2]=='C'){
            if(c!='A'){
                cnt--;
            }
        }
        if(x>0 && x<s.size()-1 && s[x-1]=='A' && s[x]=='B' && s[x+1]=='C'){
            if(c!='B'){
                cnt--;
            }
        }
        if(x>1 && s[x-2]=='A' && s[x-1]=='B' && s[x]=='C'){
            if(c!='C'){
                cnt--;
            }
        }
        if(x<s.size()-2 && s[x]!='A' && s[x+1]=='B' && s[x+2]=='C'){
            if(c=='A'){
                cnt++;
            }
        }
        if(x>0 && x<s.size()-1 && s[x-1]=='A' && s[x]!='B' && s[x+1]=='C'){
            if(c=='B'){
                cnt++;
            }
        }
        if(x>1 && s[x-2]=='A' && s[x-1]=='B' && s[x]!='C'){
            if(c=='C'){
                cnt++;
            }
        }

        s[x] = c;

        cout << cnt << endl;
    }

    return 0;
}

 D: Buildings
解法
スタックを利用する
逆から順に計算する
現在のビルよりスタックの先頭のビルが低くなるまでポップを続けてから、現在のビルをプッシュする
求める答えはスタック内の要素数
ABC372D.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> H(n);
    for(int i=0; i<n; i++){
        cin >> H[i];
    }

    vector<int> V;
    vector<int> ans(n);
    for(int i=n-1; i>=1; i--){
        while(V.size()>0 && H[i]>V.back()){
            V.pop_back();
        }
        V.push_back(H[i]);
        ans[i-1] = V.size();
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

 E: K-th Largest Connected Components
解法
Union-Find

1 \leqq k \leqq 10 だから、各連結成分における頂点番号上位 10 個を vector<vector<int>> に記録する
Union-Find の unite() と同時に頂点番号上位 10 個もマージしてソートし直す
ABC372E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct UnionFind{
    vector<int> P;
    vector<int> S;
    vector<vector<int>> G;

    UnionFind(int n) : P(n), S(n, 1), G(n){
        for(int i=0; i<n; i++){
            P[i] = i;
            G[i].push_back(i);
        }
    }

    int find(int x){
        if(x==P[x]){
            return x;
        }

        return P[x] = find(P[x]);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);

        if(x==y){
            return;
        }

        if(S[x]<S[y]){
            swap(x, y);
        }

        P[y] = x;
        S[x] += S[y];
        G[x].insert(G[x].end(), G[y].begin(), G[y].end());
        sort(G[x].rbegin(), G[x].rend());
        if(G[x].size()>10){
            G[x].resize(10);
        }
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    int size(int x){
        return S[find(x)];
    }
};

int main(){
    int n, q;
    cin >> n >> q;

    UnionFind uf(n);
    int num, u, v, k;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> u >> v;
            u--;
            v--;
            uf.unite(u, v);
        }else{
            cin >> v >> k;
            v--;
            if(uf.G[uf.find(v)].size()<k){
                cout << -1 << endl;
            }else{
                cout << uf.G[uf.find(v)][k-1]+1 << endl;
            }
        }
    }

    return 0;
}
コンテスト名

コンテストURL

開催日

A: delete .

B: 3^A

C: Count ABC Again

D: Buildings

E: K-th Largest Connected Components

Discussion
