【ABC352】AtCoder Beginner Contest 352【C++】

コンテスト名

AtCoder Beginner Contest 352

コンテストURL

https://atcoder.jp/contests/abc352

開催日

2024/05/04 21:00-22:40

---

A: AtCoder Line

解法

• 駅 $Z$ が駅 $X$ と駅 $Y$ の間にあるかを判別する

ABC352A.cpp

#include <iostream>
using namespace std;

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

    if(x>y && x>z && z>y){
        cout << "Yes" << endl;
    }else if(x<y && x<z && z<y){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Typing

解法

• 前から順番に比較する

ABC352B.cpp

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

int main(){
    string s, t;
    cin >> s >> t;

    int j = 0;
    for(int i=0; i<s.size(); i++){
        while(s[i]!=t[j]){
            j++;
        }
        if(i){
            cout << " ";
        }
        cout << j+1;
        j++;
    }

    cout << endl;
    return 0;
}

C: Standing On The Shoulders

解法

• どの巨人が一番上に立つと高さが最大になるかについて $O(N)$ の全探索をする
• 一番上に立つ巨人以外は肩の高さ $A_i$ 分だけ貢献する
• 一番上に立つ巨人は頭の高さ $B_i$ 分だけ貢献する
• $A_i$ の総和を求めて $B_i - A_i$ の最大値を足す
• 「巨人の肩の上に立つ」

ABC352C.cpp

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

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

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

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

    long long int maxv = 0;
    for(int i=0; i<n; i++){
        maxv = max(maxv, sum-A[i]+B[i]);
    }

    cout << maxv << endl;
    return 0;
}

D: Permutation Subsequence

解法

• どの連続する $K$ 個の数列を採用するかを全探索する
  • 連続する $K$ 個の数列は $N - K + 1$ 通り
• 数列が昇順になるように添字列を並び替える
• set<int> を用いて添字の最大値と最小値を更新する
  • erase() と insert() で更新する
    • 計算量はともに $O(\log N)$
  • 最大値は *.rbegin() 、最小値は *.begin() によって $O(1)$ で取得できる
• 最大値と最小値の差 $i_K - i_1$ の最小値を求める

ABC352D.cpp

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

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

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

    set<int> S;
    for(int i=0; i<k; i++){
        S.insert(P[i]);
    }

    int ans = *S.rbegin() - *S.begin();

    for(int i=k; i<n; i++){
        S.erase(P[i-k]);
        S.insert(P[i]);
        ans = min(ans, *S.rbegin() - *S.begin());
    }

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

E: Clique Connect

解法

• クラスカル法で最小全域木を求める
• 部分集合 $S_i = \lbrace A_{i, 1}, A_{i, 2},..., A_{i, K_i}, \rbrace$ のすべての頂点間に重み $C_i$ の辺を追加することは、すべての $A_{i, j}, A_{i, j+1}$ 間だけに重み $C_i$ の辺を追加することと同じ
  • 辺の数を $\frac{K_i (K_i - 1)}{2}$ 本から $K_i - 1$ 本に省略できる
• クラスカル法において、すでにすべての頂点が連結であるならばそれ以上は辺が追加されないという性質を利用する

ABC352E.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
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, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> V;
    int k, c;
    for(int i=0; i<m; i++){
        cin >> k >> c;
        int pre, a;
        for(int j=0; j<k; j++){
            cin >> a;
            a--;
            if(j){
                V.emplace_back(c, pre, a);
            }
            pre = a;
        }
    }

    sort(V.begin(), V.end());
    UnionFind uf(n);
    long long int sum = 0;
    for(int i=0; i<V.size(); i++){
        auto [c, a, b] = V[i];
        if(!uf.same(a, b)){
            sum += c;
            uf.unite(a, b);
        }
    }

    if(uf.size(0)!=n){
        cout << -1 << endl;
    }else{
        cout << sum << endl;
    }

    return 0;
}