【ABC428】AtCoder Beginner Contest 428【C++】

コンテスト名

AtCoder Beginner Contest 428（Promotion of AtCoderJobs）

コンテストURL

https://atcoder.jp/contests/abc428

開催日

2025/10/18 21:30–23:10

---

A: Grandma's Footsteps

解法

• 問題文通りにシミュレーションする

ABC428A.cpp

#include <iostream>
using namespace std;

int main(){
    int s, a, b, x;
    cin >> s >> a >> b >> x;

    int acnt = 0, bcnt = 0, sum = 0;
    bool flag = true;
    while(x--){
        if(flag){
            acnt++;
            sum += s;
            if(acnt%a==0){
                flag = false;
            }
        }else{
            bcnt++;
            if(bcnt%b==0){
                flag = true;
            }
        }
    }

    cout << sum << endl;

    return 0;
}

B: Most Frequent Substrings

解法

• map<string, int> で各部分文字列の出現回数を記録する

ABC428B.cpp

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

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

    string s;
    cin >> s;

    string t;
    map<string, int> M;
    for(int i=0; i<n-k+1; i++){
        t = s.substr(i, k);

        M[t]++;
    }

    vector<pair<int, string>> V;
    for(auto [t, cnt] : M){
        V.emplace_back(-cnt, t);
    }

    sort(V.begin(), V.end());
    int maxv = V[0].first;
    cout << -maxv << endl;
    for(int i=0; i<V.size(); i++){
        if(V[i].first!=maxv){
            break;
        }

        if(i){
            cout << " ";
        }

        cout << V[i].second;
    }
    cout << endl;

    return 0;
}

C: Brackets Stack Query

解法

• ( を $1$ 、) を $-1$ とみなし、合計で判定する

ABC428C.cpp

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

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

    int num;
    char c;
    vector<int> A{0}, B{0};
    while(q--){
        cin >> num;

        if(num==1){
            cin >> c;

            if(c=='('){
                A.push_back(A.back() + 1);
            }else if(c==')'){
                A.push_back(A.back() - 1);
            }

            B.push_back(min(B.back(), A.back()));
        }else if(num==2){
            A.pop_back();
            B.pop_back();
        }

        if(A.back()==0 && B.back()==0){
            cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }
    }

    return 0;
}