【ABC424】AtCoder Beginner Contest 424【C++】

コンテスト名

AtCoder × Engineer Guild オンサイトコンテスト ～集結！高レート人材～予選（AtCoder Beginner Contest 424）

コンテストURL

https://atcoder.jp/contests/abc424

開催日

2025/09/20 21:00–22:40

---

A: Isosceles

解法

• すべての辺の組み合わせについて確認する

ABC424A.cpp

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;

    if(a==b || b==c || c==a){
        cout << "Yes" << endl;
    }else{
       cout << "No" << endl; 
    }

    return 0;
}

B: Perfect

解法

• vector<int> に各参加者の正答数を記録する

ABC424B.cpp

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

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

    vector<int> V(n);
    vector<int> ans;
    int a, b;
    for(int i=0; i<k; i++){
        cin >> a >> b;
        a--;
        V[a]++;
        if(V[a]==m){
            ans.push_back(a+1);
        }
    }

    if(ans.size()==0){
        return 0;
    }

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

    return 0;
}

C: New Skill Acquired

解法

• 幅優先探索 (BFS)
• スキル $A_i$ と $B_i$ からスキル $i$ へそれぞれ有向辺を張ったグラフを考える

ABC424C.cpp

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

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

    int a, b;
    vector<vector<int>> G(n);
    queue<int> Q;
    vector<int> V(n);
    for(int i=0; i<n; i++){
        cin >> a >> b;

        if(a==0 && b==0){
            Q.push(i);
            V[i]++;
            continue;
        }
        if(a!=0){
            G[a-1].push_back(i);
        }
        if(b!=0){
            G[b-1].push_back(i);
        }
    }

    int sum = 0;
    while(!Q.empty()){
        int x = Q.front();

        Q.pop();
        sum++;

        for(int i=0; i<G[x].size(); i++){
            int nx = G[x][i];
            if(V[nx]!=0){
                continue;
            }
            Q.push(nx);
            V[nx]++;
        }
    }

    cout << sum << endl;

    return 0;
}