【ABC394】AtCoder Beginner Contest 394【C++】

コンテスト名

鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）

コンテストURL

https://atcoder.jp/contests/abc394

開催日

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

---

A: 22222

解法

• 文字列 $S$ を前から 1 文字ずつ調べ、2 なら出力する

ABC394A.cpp

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

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

    for(int i=0; i<s.size(); i++){
        if(s[i]=='2'){
            cout << s[i];
        }
    }
    cout << endl;

    return 0;
}

B: cat

解法

• 文字列の長さと文字列を vector<pair<int, string>> に記録して、昇順にソートする

ABC394B.cpp

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

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

    string s;
    vector<pair<int, string>> V;
    for(int i=0; i<n; i++){
        cin >> s;
        V.emplace_back(s.size(), s);
    }

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

    for(int i=0; i<n; i++){
        auto [x, t] = V[i];
        cout << t;
    }
    cout << endl;

    return 0;
}

C: Debug

解法

• 文字列 $S$ を後ろから調べ、WA を AC に変換する

ABC394C.cpp

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

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

    for(int i=s.size()-1; i>0; i--){
        if(s[i-1]=='W' && s[i]=='A'){
            s[i-1] = 'A';
            s[i] = 'C';
        }
    }

    cout << s << endl;

    return 0;
}

D: Colorful Bracket Sequence

解法

• スタックを用いて判定する

ABC394D.cpp

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

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

    if(s.size()%2!=0){
        cout << "No" << endl;
        return 0;
    }

    map<char, char> M;
    M[')'] = '(';
    M[']'] = '[';
    M['>'] = '<';

    vector<char> V;
    for(int i=0; i<s.size(); i++){
        if(V.empty() || M.count(s[i])==0){
            V.push_back(s[i]);
        }else{
            char c = V.back();
            if(c==M[s[i]]){
                V.pop_back();
            }else{
                cout << "No" << endl;
                return 0;
            }
        }
    }

    if(V.empty()){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    return 0;
}

E: Palindromic Shortest Path

解法

• 回文の中央から幅優先探索 (BFS) する

ABC394E.cpp

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

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

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

    const int INF = 1e9;
    vector<vector<int>> A(n, vector<int>(n, INF));
    queue<pair<int, int>> Q;
    for(int i=0; i<n; i++){
        A[i][i] = 0;
        Q.emplace(i, i);
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(j==i){
                continue;
            }
            if(C[i][j]!='-'){
                A[i][j] = 1;
                Q.emplace(i, j);
            }
        }
    }

    while(!Q.empty()){
        auto [x, y] = Q.front();
        Q.pop();

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(C[i][x]!='-' && C[i][x]==C[y][j] && A[i][j]>A[x][y]+2){
                    A[i][j] = A[x][y] + 2;
                    Q.emplace(i, j);
                }
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(j){
                cout << " ";
            }
            if(A[i][j]==INF){
                cout << -1;
            }else{
                cout << A[i][j];
            }
        }
        cout << '\n';
    }

    return 0;
}