【ABC392】AtCoder Beginner Contest 392【C++】

コンテスト名

日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）

コンテストURL

開催日

2025/02/08 21:00-22:40

---

A: Shuffled Equation

解法

• 昇順にソートしたうえで、 $A_1 \times A_2 = A_3$ が成り立つかを判定する

ABC392A.cpp

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

int main(){
    vector<int> A(3);
    for(int i=0; i<3; i++){
        cin >> A[i];
    }

    sort(A.begin(), A.end());

    if(A[0]*A[1]==A[2]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Who is Missing?

解法

• $A$ の各要素を set<int> に記録する
• $1$ 以上 $N$ 以下の整数が含まれているかを順に判定する

ABC392B.cpp

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

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

    int a;
    set<int> A;
    for(int i=0; i<m; i++){
        cin >> a;
        A.insert(a);
    }

    vector<int> ans;
    for(int i=1; i<=n; i++){
        if(!A.count(i)){
            ans.push_back(i);
        }
    }

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

    cout << endl;

    return 0;
}

C: Bib

解法

• $i$ が書かれたゼッケンを着けている人の番号を vector<int> $V$ に記録しておく
• 求める答えは $Q[P[V[i]]] + 1$

ABC392C.cpp

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

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

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

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << Q[P[V[i]]]+1;
    }

    cout << endl;

    return 0;
}

D: Doubles

解法

• vector<map<int, double>> で $i$ 番目のサイコロを振ったとき、数 $A_{i, j}$ が出る確率を記録する
• サイコロの組み合わせを全探索し、出目が等しくなる確率の最大値を求める

ABC392D.cpp

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

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

    vector<map<int, double>> A(n);
    int k, num;
    for(int i=0; i<n; i++){
        cin >> k;
        for(int j=0; j<k; j++){
            cin >> num;
            A[i][num] += 1.0/k;
        }
    }

    double maxv = 0.0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            double sum = 0.0;
            if(A[i].size() < A[j].size()){
                for(auto [a, b] : A[i]){
                    if(A[j].count(a)){
                        sum += b * A[j][a];
                    }
                }
            }else{
                for(auto [a, b] : A[j]){
                    if(A[i].count(a)){
                        sum += b * A[i][a];
                    }
                }
            }
            maxv = max(maxv, sum);
        }
    }

    printf("%.10f\n", maxv);

    return 0;
}

E: Cables and Servers

解法

• Union-Find
• ケーブルを繋ぎ変えずに、可能な限り、全域木を作成する
• すべてのサーバーが一つの同じ全域木に含まれるまで、余ったケーブルを使用して別々の連結成分を繋ぐ

ABC392E.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
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 a, b;
    vector<pair<int, int>> V;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        b--;
        if(uf.same(a, b)){
            V.emplace_back(i, a);
        }else{
            uf.unite(a, b);
        }
    }

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

    vector<tuple<int, int, int>> ans;
    for(auto [i, v] : V){
        int top = uf.find(v);
        for(auto s : S){
            if(!uf.same(top, s)){
                ans.emplace_back(i+1, v+1, s+1);
                uf.unite(top, s);
                S.erase(s);
                break;
            }
        }
    }

    cout << ans.size() << endl;
    for(auto [a, b, c] : ans){
        cout << a << " " << b << " " << c << '\n';
    }

    return 0;
}