【ABC402】AtCoder Beginner Contest 402【C++】

コンテスト名

東京海上日動プログラミングコンテスト2025（AtCoder Beginner Contest 402）

コンテストURL

https://atcoder.jp/contests/abc402

開催日

2025/04/19 21:00–22:40

---

A: CBC

解法

• isupper() で大文字を判定する

ABC402A.cpp

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

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

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

    return 0;
}

B: Restaurant Queue

解法

• キューで問題文通りに操作する

ABC402B.cpp

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

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

    queue<int> Q;
    int num, x;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> x;
            Q.push(x);
        }else if(num==2){
            cout << Q.front() << '\n';
            Q.pop();
        }
    }

    return 0;
}

C: Dislike Foods

解法

• 逆から考える
• vector<vector<int>> で食材別の料理を記録する

ABC402C.cpp

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

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

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

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

    vector<int> V(m, 1);
    vector<int> ans(n, m);
    int cnt = 0;
    for(int i=n-1; i>0; i--){
        for(int j=0; j<G[B[i]].size(); j++){
            if(V[G[B[i]][j]]){
                V[G[B[i]][j]] = 0;
                cnt++;
            }
        }
        ans[i-1] -= cnt;
    }

    for(int i=0; i<n; i++){
        cout << ans[i] << '\n';
    }

    return 0;
}

D: Line Crossing

解法

• 余事象を考える
• 並行な直線の組が余事象である
• 並行な直線は、点の番号の和を $N$ で割った余りが等しい

ABC402D.cpp

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

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

    int a, b;
    long long int cnt = m*(m-1)/2;
    vector<int> V(n);
    for(int i=0; i<m; i++){
        cin >> a >> b;
        cnt -= V[(a+b)%n];
        V[(a+b)%n]++;
    }

    cout << cnt << endl;

    return 0;
}