【ABC420】AtCoder Beginner Contest 420 A~E 解説（C++コード付き）

AtCoder Beginner Contest 420（ABC420）の解説記事です。
本記事では A問題～E問題 について、考え方の要点と C++ での実装例を紹介します。

目次

• コンテスト情報
• A問題
• B問題
• C問題
• D問題
• E問題
• 全体の感想・補足
• 今回のキーワード

コンテスト情報

コンテスト名

AtCoder Beginner Contest 420

開催日

2025/8/24

コンテストURL

A問題 - What month is it?

解説

• X+Y <= 24なので、X+Yが12を超えたら12減らせばよさそうです
• 数学っぽく処理するなら(X+Y-2)%12+1というやり方もありますが、今回は上記でいきましょう

コード例（C++）

#include <iostream>
using namespace std;
int main(void){
    int X, Y;
    cin >> X >> Y;
    if(X+Y > 12){
        cout<<(X+Y - 12)<<endl;
    }
    else{
        cout << (X+Y) << endl;
    }
}

B問題 - Most Minority

解説

• 一見ややこしいですが、サンプルをみるとわかりやすいです
• 少数派かどうかの判定、少数派の人全員に+1、最大値を求める、ができればよさそうなので、関数を使いながら実装していきましょう

コード例（C++）

#include <bits/stdc++.h>
using namespace std;


//グローバル変数
int N, M;
vector<string> S;
vector<int> points; //各人のポイント


//a回目の投票で、bに投票した人数を数える関数
int count(int a, int b){
    int ret = 0;
    for(int i=0;i<N;i++){
        ret += (S[i][a] == b);
    }
    return ret;
}
//a回目の投票で、bに投票した人全員に+1ポイントあげる関数
void add_point(int a, char b){
    for(int i=0;i<N;i++){
        if(S[i][a] == b){
            points[i]++;
        }
    }
}


int main(void){
    //入力
    cin >> N >> M;
    S.resize(N);
    for(int i=0;i<N;i++){
        cin >> S[i];
    }
    points.resize(N, 0);
    
    //i回目投票について、少数派の人に+1ポイント
    //ただし、0と1が同票ならみんなに+1ポイント
    for(int i=0;i<M;i++){
        int zero = count(i, '0');
        int one = count(i, '1');
        if(zero < one){
            add_point(i, '0');
        }
        else if(one < zero){
            add_point(i, '1');
        }
        else{
            add_point(i, '0');
            add_point(i, '1');
        }
    }
    
    //最大値の人を昇順に出力
    int max_point = *max_element(points.begin(), points.end());
    for(int i=0;i<N;i++){
        if(points[i] == max_point){
            cout << (i+1) << " ";
        }
    }
}

C問題 - Sum of Min Query

解説

• よく考えると、$\sum_{i=1}^N min(A_i,B_i)$の値が変わるのは、min(A_i, B_i)の値が変わる時だけです
• 事前に上記の値を求めておいて、しかるべきタイミングで減らしていけば良さそうですね
• こういう前計算と差分処理のテクニックは頻出です

コード例（C++）

#include <bits/stdc++.h>
using ll = long long;
using namespace std;


//グローバル変数
int N, Q;
vector<int> A, B;


int main(void){
    //入力
    cin >> N >> Q;
    A.resize(N);
    B.resize(N);
    for(int i=0;i<N;i++) cin >> A[i];
    for(int i=0;i<N;i++) cin >> B[i];
    
    //全体の合計を計算しておく
    long long sum = 0;
    for(int i=0;i<N;i++){
        sum += min(A[i], B[i]);
    }
    
    //各クエリの処理
    for(int q=0;q<Q;q++){
        char c;
        int x, v;
        cin >> c >> x >> v;
        x--; //0-indexedで扱う
        
        //元々のmin(A[x], B[x])をsumから引いておく
        sum -= min(A[x], B[x]);
        //更新
        if(c == 'A') A[x] = v;
        else B[x] = v;
        //更新後のmin(A[x], B[x])をsumにたす
        sum += min(A[x], B[x]);
        
        cout << sum << endl;
    }
}

D問題 - Toggle Maze

解説

• グリッドの座標と状態がある問題では、グラフの拡張が使えそうです
• 現在の「頂点」を(i,j,s)（座標(i,j)で状態s）のようにしてダイクストラなり01-bfsなりをすればいいのですが、詳細はコードを追いつつ確認してください

コード例（C++）

#include <bits/stdc++.h>
using namespace std;

//グローバル変数
const int inf = 100000000LL;
int H, W;
vector<string> A;
//nexts[i] := 頂点iから行ける{cost,index}の集合
vector<vector<pair<int,int>>> nexts;


//startから各頂点までの最短距離を返す関数
//辿り着けない場合はinf
//ここは「そういうもんなんだなぁ」と思って飛ばして読んでもOK
vector<int> dijkstra(int start){
    struct dijk_comp{
        bool operator()(const pair<int,int> &p1,const pair<int,int> &p2) const{
            return p1.first > p2.first;
        }
    };
    vector<int> dijk(nexts.size(), inf);
    priority_queue<pair<int,int>,vector<pair<int,int>>,dijk_comp> q;
    dijk[start] = 0;
    q.push({0,start});
    while(!q.empty()){
        pair<int,int> now = q.top();
        q.pop();
        //すでに更新されていれば無視
        if(now.first > dijk[now.second]) continue;
        //全ての次行ける場所に対して、コストが更新できれば更新する
        for(pair<int,int> next: nexts[now.second]){
            int ncost = next.first + now.first;
            if(dijk[next.second] > ncost){
                dijk[next.second] = ncost;
                q.push({ncost, next.second});
            }
        }
    }
    return dijk;
}
//座標と盤面の状態から、頂点番号を計算する関数
int calc_index(int i, int j, int s){
    return s*H*W + (i*W + j);
}
//座標と状態から、その状態で座標(i,j)に来た時にできる頂点番号を計算する関数
int calc_new_index(int i, int j, int s){
    if(A[i][j] == '?') return calc_index(i, j, !s);
    return calc_index(i, j, s);
}
//座標と状態から、その状態でその座標に移動できるか？を返す関数
bool can_move_to(int i, int j, int s){
    if(i < 0 || H <= i || j < 0 || W <= j) return false;
    if(A[i][j] == '#') return false;
    if(s == 0 && A[i][j] == 'x') return false;
    if(s == 1 && A[i][j] == 'o') return false;
    return true;
}
//座標と状態から、近傍で移動可能な頂点の集合を返す関数
vector<int> get_valid_neighbors(int i, int j, int s){
    vector<int> ret;
    if(can_move_to(i+1, j, s)){
        ret.push_back(calc_new_index(i+1, j, s));
    }
    if(can_move_to(i-1, j, s)){
        ret.push_back(calc_new_index(i-1, j, s));
    }
    if(can_move_to(i, j+1, s)){
        ret.push_back(calc_new_index(i, j+1, s));
    }
    if(can_move_to(i, j-1, s)){
        ret.push_back(calc_new_index(i, j-1, s));
    }
    return ret;
}
//Aの中から、bの座標を返す関数
pair<int,int> find(char b){
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(A[i][j] == b) return {i,j};
        }
    }
    return {-1,-1};
}

int main(void){
    //入力
    cin >> H >> W;
    A.resize(H);
    for(int i=0;i<H;i++) cin >> A[i];
    nexts.resize(H*W*2);
    
    //各頂点から、移動可能な頂点を計算する
    for(int s=0;s<2;s++){
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                vector<int> neighbors = get_valid_neighbors(i, j, s);
                int index = calc_index(i, j, s);
                for(int neighbor: neighbors){
                    nexts[index].push_back({1,neighbor});
                }
            }
        }
    }
    
    //スタートの場所、頂点番号を計算
    pair<int,int> start_pos = find('S');
    int start = calc_index(start_pos.first, start_pos.second, 0);
    
    //ゴールの場所、頂点番号を計算
    pair<int,int> goal_pos = find('G');
    int goal0 = calc_index(goal_pos.first, goal_pos.second, 0);
    int goal1 = calc_index(goal_pos.first, goal_pos.second, 1);
    
    //startから、ゴール頂点までの最短距離を出す
    vector<int> min_dist = dijkstra(start);
    int ans = min(min_dist[goal0], min_dist[goal1]);
    
    //辿り着ければ最短を表示
    if(ans != inf){
        cout << ans << endl;
    }
    else{
        cout << -1 << endl;
    }
    
}

E問題 - Reachability Query

解説

• 自分と繋がっているグループの中に、黒頂点があるかどうかがわかればいいです（黒頂点があれば到達可能、なければ到達不可能なので）
• こういう「自分と繋がっているグループ」の情報が大切な時はUnionFindを使うと良いことが多いですね

コード例(C++)

#include <bits/stdc++.h>
using namespace std;

//二つの要素が同じグループに属すか？
//そのグループに特定の条件を満たす要素がいくつあるか？
//などが高速で判定できるデータ構造
//繋がっていなかった2要素を新しく繋げることには強いが、繋がりを消すことには弱い
struct UnionFind {
public:
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> black; // black[i] : iが属すグループの中の黒の個数を返す
    
    UnionFind(int n) : par(n), black(n) { //最初は全てが根であるとして初期化
        for(int i=0;i<n;i++){
            par[i] = i;
            black[i] = 0;
        }
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根
        black[ry] += black[rx];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


//グローバル変数
int N,Q;


int main(void){
    //入力
    cin >> N >> Q;
    UnionFind uf(N);
    vector<bool> isBlack(N, false);
    
    //各クエリを処理
    for(int i=0;i<Q;i++){
        //まずはタイプを入力し、分岐
        int t;
        cin >> t;
        if(t == 1){
            //まずは二つの頂点を入力（頂点番号を0-indexedにするため、--しておく）
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            //二つの要素を繋ぐには、UnionFindのunite関数を使う
            uf.unite(u, v);
        }
        else if(t == 2){
            //頂点vを入力（頂点番号を0-indexedにするため、--しておく）
            int v;
            cin >> v;
            v--;
            //白黒を反転する
            if(isBlack[v]) uf.black[uf.root(v)]--;
            else uf.black[uf.root(v)]++;
            isBlack[v] = !isBlack[v];
        }
        else{
            //頂点vを入力（頂点番号を0-indexedにするため、--しておく）
            int v;
            cin >> v;
            v--;
            //黒にたどり着けるかは、vが属す集合の黒の個数を見ればわかる
            if(uf.black[uf.root(v)] > 0) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

全体の感想・補足

緑以上の人たちにとっては比較的早解きコンテストだったんじゃないでしょうか。

D問題で出題された グラフの拡張（頂点倍化） や ダイクストラ法 は実装が重めなので、ライブラリを持っておくか、実装方法のテンプレートなどを確立させておくと良さそうです。

また、辺のコストが0か1しかないグラフでの最短経路は、ダイクストラ法より01-bfsの方が速いです。余力があればそちらも実装してみましょう。

今回のキーワード

• 前計算と差分処理
• グラフの拡張
• 頂点倍化
• ダイクストラ法
• 01-bfs
• UnionFind