【ABC410】AtCoder Beginner Contest 410【C++】

コンテスト名

CodeQUEEN 2025 予選（AtCoder Beginner Contest 410）

コンテストURL

https://atcoder.jp/contests/abc410

開催日

2025/06/14 21:00–22:40

---

A: G1

解法

• 問題文通りに判定する

ABC410A.cpp

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

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

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

    int k;
    cin >> k;
    int cnt = 0;
    for(int i=0; i<n; i++){
        if(k<=A[i]){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

B: Reverse Proxy

解法

• 「現在入っているボールが最も少ない箱のうち番号が最小である箱」を前から全探索する

ABC410B.cpp

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

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

    vector<int> V(n);
    int x;
    vector<int> B;
    for(int i=0; i<q; i++){
        cin >> x;

        if(x>=1){
            x--;
            V[x]++;
            B.push_back(x+1);
        }else if(x==0){
            int minidx = -1, minv = 1e9;
            for(int j=0; j<n; j++){
                if(V[j]<minv){
                    minidx = j;
                    minv = V[j];
                }
            }
            V[minidx]++;
            B.push_back(minidx+1);
        }
    }

    for(int i=0; i<q; i++){
        if(i){
            cout << " ";
        }

        cout << B[i];
    }
    cout << endl;

    return 0;
}

C: Rotatable Array

解法

• タイプ 3 の「 $A$ の先頭の要素を末尾にする」という操作を、 $N$ で割ったあまりを添字とすることで工夫する

ABC410C.cpp

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

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

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

    int num, p, x, k;
    int cnt = 0;
    for(int i=0; i<q; i++){
        cin >> num;

        if(num==1){
            cin >> p >> x;
            p--;
            x--;
            A[(p+cnt)%n] = x;
        }else if(num==2){
            cin >> p;
            p--;
            cout << A[(p+cnt)%n] + 1 << '\n';
        }else if(num==3){
            cin >> k;
            cnt += k;
            cnt %= n;
        }
    }

    return 0;
}

D: XOR Shortest Walk

解法

• 頂点倍化
  • $N \times 2^{10}$ 頂点のグラフとみなす
• 幅優先探索 (BFS)
  • $\text{seen}[i][j]$ := 頂点 $i$ に $\text{XOR}$ が $j$ の状態で到達したか

ABC410D.cpp

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

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

    vector<vector<pair<int, int>>> G(n);
    int a, b, w;
    for(int i=0; i<m; i++){
        cin >> a >> b >> w;
        a--;
        b--;

        G[a].emplace_back(b, w);
    }

    vector<vector<int>> seen(n, vector<int>(1<<10));
    queue<pair<int, int>> Q;
    seen[0][0] = 1;
    Q.emplace(0, 0);
    while(!Q.empty()){
        auto [v, w] = Q.front();
        Q.pop();

        for(int i=0; i<G[v].size(); i++){
            auto [nv, nw] = G[v][i];

            if(seen[nv][w^nw]){
                continue;
            }

            seen[nv][w^nw] = 1;
            Q.emplace(nv, w^nw);
        }
    }

    for(int i=0; i<1<<10; i++){
        if(seen[n-1][i]){
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}