🔵

【ABC420】AtCoder Beginner Contest 420【C++】

に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 420

コンテストURL

https://atcoder.jp/contests/abc420

開催日

2025/08/24 21:00–22:40

A: What month is it?

解法

  • X+Y を 12 で割った余りを求める
  • 12 月のときに余りが 0 になることに注意する
ABC420A.cpp
#include <iostream>
using namespace std;

int main(){
    int x, y;
    cin >> x >> y;

    if((x+y)%12!=0){
        cout << (x+y)%12 << endl;
    }else{
        cout << 12 << endl;
    }

    return 0;
}

B: Most Minority

解法

  • 問題文通りにシミュレーションする
ABC420B.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

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

    vector<int> V(n);
    for(int i=0; i<m; i++){
        int x = 0, y = 0;
        for(int j=0; j<n; j++){
            if(S[j][i]=='0'){
                x++;
            }else{
                y++;
            }
        }


        if(x==0 || y==0){
            for(int j=0; j<n; j++){
                V[j]++;
            }
        }else if(x<y){
            for(int j=0; j<n; j++){
                if(S[j][i]=='0'){
                    V[j]++;
                }
            }
        }else if(x>y){
            for(int j=0; j<n; j++){
                if(S[j][i]=='1'){
                    V[j]++;
                }
            }
        }
    }

    int maxv = *max_element(V.begin(), V.end());
    int cnt = 0;
    for(int i=0; i<n; i++){
        if(V[i]==maxv){
            if(cnt){
                cout << " ";
            }
            cnt++;
            cout << i + 1;
        }
    }
    cout << endl;

    return 0;
}

C: Sum of Min Query

解法

  • 差分に着目する
ABC420C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    vector<int> M(n);
    long long int sum = 0;
    for(int i=0; i<n; i++){
        M[i] = min(A[i], B[i]);
        sum += M[i];
    }

    char c;
    int x, v;
    while(q--){
        cin >> c >> x >> v;
        x--;

        if(c=='A'){
            A[x] = v;          
        }else if(c=='B'){
            B[x] = v;
        }

        sum -= (M[x]-min(A[x], B[x]));
        M[x] = min(A[x], B[x]);
        cout << sum << '\n';
    }

    return 0;
}

D: Toggle Maze

解法

  • 幅優先探索 (BFS)
  • 当該マスに到達した時点までのスイッチマスに移動した合計回数が偶数が奇数かで 2 通り考える
ABC420D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;

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

    vector<vector<char>> A(h, vector<char>(w));
    int sx, sy, gx, gy;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> A[i][j];
            if(A[i][j]=='S'){
                sx = i;
                sy = j;
            }else if(A[i][j]=='G'){
                gx = i;
                gy = j;
            }
        }
    }

    const int INF = 1e9;
    vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    vector<vector<vector<int>>> dist(h, vector<vector<int>>(w, vector<int>(2, INF)));
    queue<tuple<int, int, int>> Q;
    dist[sx][sy][0] = 0;
    Q.emplace(sx, sy, 0);
    while(!Q.empty()){
        auto [x, y, num] = Q.front();
        Q.pop();

        if(A[x][y]=='?'){
            num ^= 1;
        }

        for(int i=0; i<4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx<0 || nx>=h || ny<0 || ny>=w){
                continue;
            }
            if(A[nx][ny]=='#'){
                continue;
            }
            if(dist[nx][ny][num]<INF){
                continue;
            }
            if(num==0 && A[nx][ny]=='x'){
                continue;
            }
            if(num==1 && A[nx][ny]=='o'){
                continue;
            }

            if(A[x][y]=='?'){
                dist[nx][ny][num] = dist[x][y][num^1] + 1;
            }else{
                dist[nx][ny][num] = dist[x][y][num] + 1;
            }
            Q.emplace(nx, ny, num);
        }
    }

    if(dist[gx][gy][0]==INF && dist[gx][gy][1]==INF){
        cout << -1 << endl;
    }else{
        cout << min(dist[gx][gy][0], dist[gx][gy][1]) << endl;
    }

    return 0;
}

E: Reachability Query

解法

  • Union-Find
  • 各連結成分について、黒色の頂点の個数を記録する
  • 「タイプ 1 」の結合操作の際、黒色の頂点の個数を加算することに注意する
ABC420E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct UnionFind{
    vector<int> P;
    vector<int> S;

    UnionFind(int n) : P(n), S(n, 1){
        for(int i=0; i<n; i++){
            P[i] = i;
        }
    }

    int find(int x){
        if(x==P[x]){
            return x;
        }

        return P[x] = find(P[x]);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);

        if(x==y){
            return;
        }

        if(S[x]<S[y]){
            swap(x, y);
        }

        P[y] = x;
        S[x] += S[y];
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    int size(int x){
        return S[find(x)];
    }
};

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

    UnionFind uf(n);
    int num, u, v;
    vector<int> V(n);
    vector<int> C(n);
    while(q--){
        cin >> num;

        if(num==1){
            cin >> u >> v;
            u--;
            v--;
            if(!uf.same(u, v)){
                int pu = V[uf.find(u)];
                int pv = V[uf.find(v)];
                uf.unite(u, v);
                V[uf.find(u)] = pu + pv;
            }
        }else if(num==2){
            cin >> v;
            v--;
            if(C[v]==0){
                C[v] = 1;
                V[uf.find(v)]++;
            }else{
                C[v] = 0;
                V[uf.find(v)]--;
            }
        }else if(num==3){
            cin >> v;
            v--;

            if(V[uf.find(v)]>0){
                cout << "Yes" << '\n';
            }else{
                cout << "No" << '\n';
            }
        }
    }
}

Discussion