【ABC404】AtCoder Beginner Contest 404【C++】

コンテスト名

AtCoder Beginner Contest 404（Promotion for Engineer Guild）

コンテストURL

https://atcoder.jp/contests/abc404

開催日

2025/05/03 21:00–22:40

---

A: Not Found

解法

• a から z まで全探索する

ABC404A.cpp

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

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

    for(char c='a'; c<='z'; c++){
        if(find(s.begin(), s.end(), c)==s.end()){
            cout << c << endl;
            return 0;
        }
    }

    return 0;
}

B: Grid Rotation

解法

• 全探索
• 90 度回転の回数は 0、1、2、3 の 4 通り

AB404B.cpp

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

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

    vector<vector<char>> S(n, vector<char>(n)), T(n, vector<char>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> S[i][j];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> T[i][j];
        }
    }

    int minv = 100000;
    int cnt = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(S[i][j]!=T[i][j]){
                cnt++;
            }
        }
    }
    minv = min(minv, cnt);

    cnt = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(S[n-j-1][i]!=T[i][j]){
                cnt++;
            }
        }
    }
    minv = min(minv, cnt);

    cnt = 2;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(S[n-i-1][n-j-1]!=T[i][j]){
                cnt++;
            }
        }
    }
    minv = min(minv, cnt);

    cnt = 3;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(S[j][n-i-1]!=T[i][j]){
                cnt++;
            }
        }
    }
    minv = min(minv, cnt);

    cout << minv << endl;

    return 0;
}

C: Cycle Graph?

解法

• サイクルグラフの頂点の数列の列挙を試み、成功すればサイクルグラフである
• 最後の $v_N$ と $v_1$ を結ぶ辺の存在判定に注意する

ABC404C.cpp

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

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

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

    if(n!=m){
        cout << "No" << endl;
        return 0;
    }

    vector<int> seen(n);
    int v = 0;
    bool flag = true;
    for(int i=0; i<n-1; i++){
        seen[v] = 1;
        flag = false;
        for(int j=0; j<G[v].size(); j++){
            if(seen[G[v][j]]==0){
                v = G[v][j];
                flag = true;
                break;
            }
        }
    }

    if(flag){
        flag = false;
        for(int i=0; i<G[v].size(); i++){
            if(G[v][i]==0){
                flag = true;
            }
        }
    }

    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

D: Goin' to the Zoo

解法

• 3 進数全探索
• 各動物園を訪れる回数は、0、1、2 の 3 通り
• bit 全探索のように実行する
• 計算量は $\mathrm{O}(3^N N M)$

ABC404D.cpp

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

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

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

    vector<vector<int>> Z(n);
    int k, a;
    for(int i=0; i<m; i++){
        cin >> k;
        for(int j=0; j<k; j++){
            cin >> a;
            a--;
            Z[a].push_back(i);
        }
    }

    int n3 = 1;
    vector<int> V(n);
    for(int i=0; i<n; i++){
        V[i] = n3;
        n3 *= 3;
    }

    long long int minv = 1e18;
    for(int i=0; i<n3; i++){
        vector<int> W(m);
        long long int sum = 0;
        for(int j=0; j<n; j++){
            if((i/V[j])%3==1){
                sum += C[j];
                for(int k=0; k<Z[j].size(); k++){
                    W[Z[j][k]]++;
                }
            }else if((i/V[j])%3==2){
                sum += (C[j] * 2);
                for(int k=0; k<Z[j].size(); k++){
                    W[Z[j][k]] += 2;
                }
            }
        }

        bool flag = true;
        for(int i=0; i<m; i++){
            if(W[i]<2){
                flag = false;
                break;
            }
        }

        if(flag){
            minv = min(minv, sum);
        }
    }

    cout << minv << endl;

    return 0;
}

E: Bowls and Beans

解法

• 豆は後ろから移動させる
• 移動できる範囲に豆が入っている茶碗がある場合は、豆が入っている茶碗に豆を移動させる
• 移動できる範囲に豆が入っている茶碗がない場合は、最も前に移動できる茶碗に豆を移動させる

ABC404E.cpp

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

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

    vector<int> C(n), A(n);
    for(int i=1; i<n; i++){
        cin >> C[i];
    }
    for(int i=1; i<n; i++){
        cin >> A[i];
    }

    A[0] = 1;
    int sum = 0;
    for(int i=n-1; i>0; i--){
        if(A[i]==0){
            continue;
        }

        sum++;

        int ni = 0;
        int minv = n + 1;
        bool flag = true;
        for(int j=0; j<C[i]; j++){
            if(A[i-1-j]>0){
                flag = false;
            }else if((i-1-j-C[i-1-j])<minv){
                ni = i-1-j;
                minv = i-1-j-C[i-1-j];
            }
        }

        if(flag){
            A[ni]++;
        }
    }

    cout << sum << endl;

    return 0;
}