【ABC412】AtCoder Beginner Contest 412【C++】

コンテスト名

日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）

コンテストURL

開催日

2025/06/28 21:00–22:40

---

A: Task Failed Successfully

解法

• 問題文通りに判定する

ABC412A.cpp

#include <iostream>
using namespace std;

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

    int a, b, cnt = 0;
    for(int i=0; i<n; i++){
        cin >> a >> b;

        if(b>a){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

B: Precondition

解法

• 問題文通りに判定する
• 文字列中に指定の文字が見つからないときは string::npos

ABC412B.cpp

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

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

    for(int i=1; i<s.size(); i++){
        if(isupper(s[i]) && t.find(s[i-1])==string::npos){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

C: Giant Domino

解法

• しゃくとり法
• ドミノ $1$ とドミノ $N$ 以外を昇順にソートする

ABC412C.cpp

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

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

    while(t--){
        int n;
        cin >> n;

        vector<int> S(n-2);
        int s1;
        cin >> s1;
        for(int i=0; i<n-2; i++){
            cin >> S[i];
        }
        int sn;
        cin >> sn;

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

        int maxv = s1;
        int cnt = 2;
        bool flag = false;

        if(maxv*2>=sn){
            cout << cnt << '\n';
            continue;
        }
        
        for(int i=0; i<n-2;){
            cnt++;

            int idx = i;
            int tmp = maxv;
            while(i<n-2 && maxv*2>=S[i]){
                tmp = S[i];
                i++;
            }

            maxv = tmp;

            if(i==idx){
                break;
            }

            if(maxv*2>=sn){
                flag = true;
                break;
            }
        }

        if(flag){
            cout << cnt << '\n';
        }else{
            cout << -1 << '\n';
        }
    }

    return 0;
}

D: Make 2-Regular Graph

解法

• すべての頂点の次数が $2$ であるとき、すべての連結成分が閉路グラフである
• 連結成分の数と閉路グラフ中の頂点の順番を全探索する

ABC412D.cpp

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

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

    int a, b;
    vector<vector<int>> G(n, vector<int>(n));
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        b--;

        G[a][b] = 1;
        G[b][a] = 1;
    }

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

    int minv = 1e9;
    do{
        int cnt = 0;
        vector<vector<int>> G2(n, vector<int>(n));
        for(int i=0; i<n-1; i++){
            G2[P[i]][P[i+1]] = 1;
            G2[P[i+1]][P[i]] = 1;
        }
        G2[P.back()][P[0]] = 1;
        G2[P[0]][P.back()] = 1;

        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(G[i][j]!=G2[i][j]){
                    cnt++;
                }
            }
        }

        minv = min(minv, cnt);

        for(int i=3; i<=n-3; i++){
            int cnt = 0;
            vector<vector<int>> G2(n, vector<int>(n));
            for(int j=0; j<i-1; j++){                
                G2[P[j]][P[j+1]] = 1;
                G2[P[j+1]][P[j]] = 1;
            }
            G2[P[i-1]][P[0]] = 1;
            G2[P[0]][P[i-1]] = 1;

            for(int j=i; j<n-1; j++){                
                G2[P[j]][P[j+1]] = 1;
                G2[P[j+1]][P[j]] = 1;
            }
            G2[P.back()][P[i]] = 1;
            G2[P[i]][P.back()] = 1;

            for(int j=0; j<n; j++){
                for(int k=j; k<n; k++){
                    if(G[j][k]!=G2[j][k]){
                        cnt++;
                    }
                }
            }

            minv = min(minv, cnt);
        }
    }while(next_permutation(P.begin(), P.end()));

    cout << minv << endl;

    return 0;
}