【ABC430】AtCoder Beginner Contest 430【C++】

コンテスト名

AtCoder Beginner Contest 430

コンテストURL

https://atcoder.jp/contests/abc430

開催日

2025/11/01 21:00–22:40

---

A: Candy Cookie Law

解法

• 問題文通りに判定する

ABC430A.cpp

#include <iostream>
using namespace std;

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

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

    return 0;
}

B: Count Subgrid

解法

• set<vector<vector<char>>> にマスの塗られ方を記録する

ABC430B.cpp

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

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

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

    set<vector<vector<char>>> S;
    for(int i=0; i<=n-m; i++){
        for(int j=0; j<=n-m; j++){
            vector<vector<char>> T(m, vector<char>(m));

            for(int a=i; a<i+m; a++){
                for(int b=j; b<j+m; b++){
                    T[a-i][b-j] = G[a][b];
                }
            }

            S.insert(T);
        }
    }

    cout << S.size() << endl;

    return 0;
}

C: Truck Driver

解法

• しゃくとり法

ABC430C.cpp

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

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

    vector<int> SA(n+1), SB(n+1);
    for(int i=0; i<n; i++){
        if(s[i]=='a'){
            SA[i+1] = 1;
        }else if(s[i]=='b'){
            SB[i+1] = 1;
        }
    }

    for(int i=0; i<n; i++){
        SA[i+1] += SA[i];
        SB[i+1] += SB[i];
    }

    long long int ans = 0;
    int idxa = 0, idxb = 0;
    for(int i=1; i<=n; i++){
        if(idxa<i-1){
            idxa = i - 1;
        }
        if(idxb<i-1){
            idxb = i - 1;
        }

        while(idxa<n && SA[idxa+1]-SA[i-1]<a){
            idxa++;
        }
        while(idxb<n && SB[idxb+1]-SB[i-1]<b){
            idxb++;
        }
        idxb--;

        if(idxa<=idxb){
            ans += idxb - idxa + 1;
        }
    }

    cout << ans << endl;

    return 0;
}