【ABC396】AtCoder Beginner Contest 396【C++】

コンテスト名

AtCoder Beginner Contest 396

コンテストURL

開催日

2025/03/08 21:00-22:40

---

A: Triple Four

解法

• 問題文通りに判定する

ABC396A.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];
    }

    for(int i=2; i<n; i++){
        if(A[i-2]==A[i-1] && A[i-1]==A[i]){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;

}

B: Card Pile

解法

• スタックで実装する

ABC396B.cpp

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

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

    vector<int> V;
    for(int i=0; i<100; i++){
        V.push_back(0);
    }

    int num, x;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> x;
            V.push_back(x);
        }else{
            cout << V.back() << '\n';
            V.pop_back();
        }
    }

    return 0;
}

C: Buy Balls

解法

• $B$ と $W$ をそれぞれ降順にソートする
• $W_i > 0$ かつ $B_i + W_i > 0$ となる最大の $i$ まで、黒色のボールと白色のボールを両方選ぶ
• $i$ より大きい範囲は、 $B_j > 0$ となる最大の $j$ まで、黒色のボールのみを選ぶ

ABC396C.cpp

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

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

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

    sort(B.rbegin(), B.rend());
    sort(W.rbegin(), W.rend());

    long long int sum = 0;
    int i;
    bool flag = true;
    for(i=0; i<min(n, m); i++){
        if(W[i]>0 && B[i]+W[i]>0){
            sum += (B[i]+W[i]);
        }else{
            flag = false;
            break;
        }
    }

    if(flag){
        i = min(n, m);
    }

    for(int j=i; j<n; j++){
        if(B[j]>0){
            sum += B[j];
        }else{
            break;
        }
    }

    cout << sum << endl;

    return 0;
}

D: Minimum XOR Path

解法

1. 順列全探索
2. 深さ優先探索 (DFS)

ABC396D_1.cpp

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

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

    vector<vector<long long int>> G(n, vector<long long int>(n, -1));
    int u, v;
    long long int w;
    for(int i=0; i<m; i++){
        cin >> u >> v >> w;
        u--;
        v--;
        G[u][v] = w;
        G[v][u] = w;
    }

    long long int minv = 1LL<<60;
    vector<int> P;
    for(int i=1; i<n; i++){
        P.push_back(i);
    }
    do{
        long long int sum = 0;
        int pre = 0;
        for(int i=0; i<n-1; i++){
            if(G[pre][P[i]]!=-1){
                sum ^= G[pre][P[i]];
                pre = P[i];
            }else{
                break;
            }

            if(P[i]==n-1){
                minv = min(minv, sum);
            }
        }
    }while(next_permutation(P.begin(), P.end()));

    cout << minv << endl;

    return 0;
}

ABC396D_2.cpp

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

long long int n, m;
vector<vector<pair<int, long long int>>> G;
vector<int> seen;
long long int minv = 1LL<<60;

void dfs(int x, long long int sum){
    seen[x] = 1;

    if(x==n-1){
        minv = min(minv, sum);
    }

    for(int i=0; i<G[x].size(); i++){
        auto [nx, w] = G[x][i];

        if(seen[nx]){
            continue;
        }

        dfs(nx, sum^w);
    }

    seen[x] = 0;
}

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

    G.resize(n);
    int u, v;
    long long int w;
    for(int i=0; i<m; i++){
        cin >> u >> v >> w;
        u--;
        v--;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    seen.resize(n);
    dfs(0, 0);

    cout << minv << endl;

    return 0;
}

E: Min of Restricted Sum

解法

• 頂点 $X_i$ と頂点 $Y_i$ を重み $Z_i$ の辺で結ぶ無向グラフを考える
• 連結成分ごとに幅優先探索 (BFS) する
  • 一つの頂点の値が決まれば、XOR の条件より、同じ連結成分のすべての値が決まる
• 各ビットは独立であることを利用する
• 各ビットにおいて、1 の数が過半数の場合は、0 と 1 を逆転する

ABC396E.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 x, y, z;
    for(int i=0; i<m; i++){
        cin >> x >> y >> z;
        x--;
        y--;
        G[x].emplace_back(y, z);
        G[y].emplace_back(x, z);
    }

    vector<int> A(n);
    vector<int> seen(n);
    vector<int> B(n, -1);

    for(int i=0; i<n; i++){
        if(seen[i]){
            continue;
        }
        
        queue<pair<int, int>> Q;
        Q.emplace(i, 0);
        B[i] = 0;
        vector<int> V;
        V.push_back(i);
        while(!Q.empty()){
            auto [x, z] = Q.front();
            Q.pop();
            seen[x] = 1;

            for(int j=0; j<G[x].size(); j++){
                auto [nx, nz] = G[x][j];

                if(B[nx]!=-1){
                    if(B[nx]!=(z^nz)){
                        cout << -1 << endl;
                        return 0;
                    }else{
                        continue;
                    }
                }

                Q.emplace(nx, z^nz);
                B[nx] = z^nz;
                V.push_back(nx);
            }
        }

        for(int j=0; j<30; j++){
            int cnt = 0;
            for(int l=0; l<V.size(); l++){
                if(B[V[l]]&(1<<j)){
                    cnt++;
                }
            }

            if(cnt<V.size()-cnt){
                for(int l=0; l<V.size(); l++){
                    if(B[V[l]]&(1<<j)){
                        A[V[l]] |= (1<<j);
                    }
                }
            }else{
                for(int l=0; l<V.size(); l++){
                    if(!(B[V[l]]&(1<<j))){
                        A[V[l]] |= (1<<j);
                    }
                }
            }
        }
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;

    return 0;
}