【ABC399】AtCoder Beginner Contest 399【C++】

コンテスト名

AtCoder Beginner Contest 399

コンテストURL

開催日

2025/03/29 21:00-22:40

---

A: Hamming Distance

解法

• 問題文通りに判定する

ABC399A.cpp

#include <iostream>
#include <string>
using namespace std;

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

    string s, t;
    cin >> s >> t;

    int cnt = 0;
    for(int i=0; i<n; i++){
        if(s[i]!=t[i]){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

B: Ranking with Ties

解法

• map<int, int> に各点数を獲得した人の人数を記録する
  • map<int, int> はキーの昇順にソートされる
• 問題文通りに順位を決定する

ABC399B.cpp

#include <iostream>
#include <vector>
#include <map>
using namespace std;

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

    vector<int> P(n);
    map<int, int> M1;
    for(int i=0; i<n; i++){
        cin >> P[i];
        M1[-P[i]]++;
    }

    map<int, int> M2;
    int r = 1;
    for(auto [a, b] : M1){
        M2[-a] = r;
        r += b;
    }

    for(int i=0; i<n; i++){
        cout << M2[P[i]] << '\n';
    }

    return 0;
}

C: Make it Forest

解法

• Union-Find
• 頂点数が $X$ の連結成分において、残すことができる辺の本数の最大値は、 $X - 1$
• 連結成分数を $U$ とすると、求める答えは、 $M - \sum\limits_{i=1}^U (X_i - 1) = M - (N - U)$
• Union-Find で連結成分の個数を求める

ABC399C.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

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

    UnionFind(int n) : P(n), S(n, 1){
        for(int i=0; i<n; i++){
            P[i] = 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];
    }

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

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

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

    UnionFind uf(n);
    int u, v;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        u--;
        v--;
        uf.unite(u, v);
    }

    set<int> S;
    for(int i=0; i<n; i++){
        S.insert(uf.find(i));
    }

    cout << m - n + S.size() << endl;

    return 0;
}

D: Switch Seats

解法

• vector<vector<int>> に各数の位置を記録する
• 隣接しない条件に注意する

ABC399D.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

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

    for(int i=0; i<t; i++){
        int n;
        cin >> n;

        vector<int> A(2*n);
        vector<vector<int>> V(n);
        for(int j=0; j<2*n; j++){
            cin >> A[j];
            V[A[j]-1].push_back(j);
        }

        set<pair<int, int>> S;
        for(int j=0; j<2*n-1; j++){
            if(V[A[j]-1][0]+1==V[A[j]-1][1]){
                continue;
            }
            if(V[A[j+1]-1][0]+1==V[A[j+1]-1][1]){
                continue;
            }

            vector<int> V2{V[A[j]-1][0], V[A[j]-1][1], V[A[j+1]-1][0], V[A[j+1]-1][1]};
            sort(V2.begin(), V2.end());
            if(V2[0]+1==V2[1] && V2[2]+1==V2[3]){
                S.emplace(min(A[j], A[j+1]), max(A[j], A[j+1]));
            }
        }

        cout << S.size() << '\n';
    }

    return 0;
}