【ABC406】AtCoder Beginner Contest 406【C++】

コンテスト名

パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 406）

コンテストURL

https://atcoder.jp/contests/abc406

開催日

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

---

A: Not Acceptable

解法

• 時刻を整数に変換して考える
  • $A \times 100 + B > C \times 100 + D$

ABC406A.cpp

#include <iostream>
using namespace std;

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

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

    return 0;
}

B: Product Calculator

解法

• オーバーフローに注意し、積算の判定を徐算の判定に置き換える

ABC406B.cpp

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

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

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

    long long int maxk = 1;
    for(int i=0; i<k; i++){
        maxk *= 10;
    }

    long long int ans = 1;
    for(int i=0; i<n; i++){
        if(A[i]>(maxk-1)/ans){
            ans = 1;
        }else{
            ans *= A[i];
        }
    }

    cout << ans << endl;

    return 0;
}

C: ~

解法

• ランレングス圧縮
• 「大なり $>$ 」のかたまりの左隣と右隣に「小なり $<$ 」がそれぞれいくつ連なっているかを数える

ABC406C.cpp

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

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

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

    vector<int> V(n-1);
    for(int i=0; i<n-1; i++){
        if(P[i]<P[i+1]){
            V[i] = 1;
        }else if(P[i]>P[i+1]){
            V[i] = 2;
        }
    }

    vector<pair<int, int>> L;
    for(int i=0; i<n-1; i++){
        if(L.size()==0){
            L.emplace_back(V[i], 1);
        }else{
            if(L.back().first==V[i]){
                L.back().second++;
            }else{
                L.emplace_back(V[i], 1);
            }
        }
    }

    long long int sum = 0;
    for(int i=0; i<L.size(); i++){
        long long int l = 0, r = 0;
        auto [num, cnt] = L[i];

        if(num==2 && i>0 && i<L.size()-1 && L[i-1].first==1 && L[i+1].first==1){
            l = L[i-1].second;
            r = L[i+1].second;
            sum += (l * r);
        }
    }

    cout << sum << endl;

    return 0;
}

D: Garbage Removal

解法

• vector<set<int>> で各行・各列のゴミを管理する
• erase() と clear() でゴミを取り除く

ABC406D.cpp

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

int main(){
    int h, w, n;
    cin >> h >> w >> n;

    vector<set<int>> X(h), Y(w);
    int x, y;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        x--;
        y--;
        X[x].insert(y);
        Y[y].insert(x);
    }

    int q, num, z;
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> num >> z;
        z--;
        if(num==1){
            cout << X[z].size() << '\n';

            for(auto a : X[z]){
                Y[a].erase(z);
            }

            X[z].clear();
        }else if(num==2){
            cout << Y[z].size() << '\n';

            for(auto a : Y[z]){
                X[a].erase(z);
            }

            Y[z].clear();
        }
    }

    return 0;
}