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

### コンテスト名
ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）

### コンテストURL
https://atcoder.jp/contests/abc372

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

---

## [A: delete .](https://atcoder.jp/contests/abc372/tasks/abc372_a)
**解法**
- 文字列 $S$ を前から順番に判定する
- `.` 以外ならそのまま出力する
```cpp: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](https://atcoder.jp/contests/abc372/tasks/abc372_b)
**解法**
- 大きいほうから貪欲に決定していく
- $3^{10}, \cdots, 3^0$ の順にそれぞれいくつ必要かを計算する
```cpp: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](https://atcoder.jp/contests/abc372/tasks/abc372_c)
**解法**
- 変更される文字の前後だけを確認すればよい
- 最初に文字列 $S$ に文字列 `ABC` が部分文字列として何箇所含まれるかを計算しておく
```cpp: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](https://atcoder.jp/contests/abc372/tasks/abc372_d)
**解法**
- スタックを利用する
- 逆から順に計算する
- 現在のビルよりスタックの先頭のビルが低くなるまでポップを続けてから、現在のビルをプッシュする
- 求める答えはスタック内の要素数
```cpp: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](https://atcoder.jp/contests/abc372/tasks/abc372_e)
**解法**
- Union-Find
- $1 \leqq k \leqq 10$ だから、各連結成分における頂点番号上位 10 個を `vector<vector<int>>` に記録する
- Union-Find の `unite()` と同時に頂点番号上位 10 個もマージしてソートし直す
```cpp: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;
}
```