【ABC371】AtCoder Beginner Contest 371【C++】

コンテスト名

AtCoder Beginner Contest 371

コンテストURL

開催日

2024/09/14 21:00-22:40

---

A: Jiro

解法

• 答えを全探索する
• 3 重ループもしくは順列全探索

ABC371A.cpp

#include <iostream>
using namespace std;

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

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                bool flag = true;
                if(x=='<' && i>=j){
                    flag = false;
                }
                if(x=='>' && i<=j){
                    flag = false;
                }
                if(y=='<' && i>=k){
                    flag = false;
                }
                if(y=='>' && i<=k){
                    flag = false;
                }
                if(z=='<' && j>=k){
                    flag = false;
                }
                if(z=='>' && j<=k){
                    flag = false;
                }

                if(flag){
                    if(i==1){
                        cout << "A" << endl;
                    }else if(j==1){
                        cout << "B" << endl;
                    }else if(k==1){
                        cout << "C" << endl;
                    }
                    return 0;
                }
            }
        }
    }
}

B: Taro

解法

• 各家で男の子がすでに生まれているかを vector<int> に記録する

ABC371B.cpp

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

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

    vector<int> V(n);
    int a;
    char b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        if(b=='M' && V[a]==0){
            V[a]++;
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}

C: Make Isomorphic

解法

• 順列全探索で頂点番号の付け替えを実現する
• グラフ $G$ とグラフ $H$ を比較して異なる辺に対応する $A_{i,j}$ を加算する

ABC371C.cpp

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

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

    vector<vector<int>> G(n, vector<int>(n)), H(n, vector<int>(n)), A(n, vector<int>(n));
    int mg;
    cin >> mg;
    int u, v;
    for(int i=0; i<mg; i++){
        cin >> u >> v;
        u--;
        v--;
        G[u][v] = 1;
        G[v][u] = 1;
    }
    int mh;
    cin >> mh;
    int a, b;
    for(int i=0; i<mh; i++){
        cin >> a >> b;
        a--;
        b--;
        H[a][b] = 1;
        H[b][a] = 1;
    }

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

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

    int minv = 1e9;
    do{
        int sum = 0;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if(G[V[i]][V[j]]!=H[i][j]){
                    sum += A[i][j];
                }
            }
        }
        minv = min(minv, sum);
    }while(next_permutation(V.begin(), V.end()));
    
    cout << minv << endl;
    return 0;
}

D: 1D Country

解法

• 座標圧縮の考え方と累積和
• 整数 $L_i, R_i$ が何番目の $X_i$ に対応するかを二分探索で求める

ABC371D.cpp

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

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

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

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

    vector<long long int> S(n+1);
    for(int i=0; i<n; i++){
        S[i+1] = S[i] + P[i];
    }

    int q;
    cin >> q;
    int l, r;
    for(int i=0; i<q; i++){
        cin >> l >> r;
        int lidx = lower_bound(X.begin(), X.end(), l) - X.begin();
        int ridx = upper_bound(X.begin(), X.end(), r) - X.begin();
        ridx--;
        if(ridx<lidx){
            cout << 0 << endl;
        }else{
            cout << S[ridx+1] - S[lidx] << endl;
        }
    }

    return 0;
}

E: I Hate Sigma Problems

解法

• 各値が含まれる連続部分列の個数の合計が求める答えである
• 各値が含まれる連続部分列の個数は余事象を考えて求める
• 左端と右端に番兵を挿入しておくと簡単になる

ABC371E.cpp

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

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

    vector<vector<int>> A(n, vector<int>(1, -1));
    int a;
    for(int i=0; i<n; i++){
        cin >> a;
        a--;
        A[a].push_back(i);
    }
    for(int i=0; i<n; i++){
        A[i].push_back(n);
    }

    long long int ans = 0;
    long long int all = ((long long int)n * (n-1)) / 2 + n;
    for(int i=0; i<n; i++){
        long long int sum = 0;
        for(int j=0; j<A[i].size()-1; j++){
            int diff = A[i][j+1] - A[i][j];
            sum += ((long long int)(diff-1) * (diff-2)) / 2 + (diff-1);
        }
        ans += (all - sum);
    }

    cout << ans << endl;
    return 0;
}