【ABC408】AtCoder Beginner Contest 408【C++】

コンテスト名

AtCoder Beginner Contest 408

コンテストURL

開催日

2025/05/31 21:00–22:40

---

A: Timeout

解法

• $T_{i+1} - T_i$ と $S$ の関係で判定する
• $T_1$ の判定に注意する

ABC408A.cpp

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

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

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

    for(int i=0; i<n; i++){
        if(T[i+1]-T[i]>s){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

B: Compression

解法

• set<int> で管理する

ABC408B.cpp

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

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

    set<int> S;
    int a;
    for(int i=0; i<n; i++){
        cin >> a;
        S.insert(a);
    }

    cout << S.size() << endl;
    int cnt = 0;
    for(int a : S){
        if(cnt){
            cout << " ";
        }
        cout << a;
        cnt++;
    }
    cout << endl;

    return 0;
}

C: Not All Covered

解法

• いもす法
• 最も守っている砲台の数が少ない城壁を守っている砲台の数が答えである

ABC408C.cpp

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

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

    vector<int> S(n+1);
    int l, r;
    for(int i=0; i<m; i++){
        cin >> l >> r;
        l--;
        r--;
        S[l]++;
        S[r+1]--;
    }

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

    int minv = 1e9;
    for(int i=0; i<n; i++){
        minv = min(minv, S[i]);
    }

    cout << minv << endl;

    return 0;
}

D: Flip to Gather

解法

• 動的計画法 (DP)
• 1 のかたまりを中央につくることを考える
• $\text{dp}[i][j]$ := $i$ 番目の状態が $j$ であるときの $i$ 番目までの操作回数の最小値
  • $j=0$ ：1 のかたまりの左の 0 のかたまりに属する
  • $j=1$ ：1 のかたまりに属する
  • $j=2$ ：1 のかたまりの右の 0 のかたまりに属する

ABC408D.cpp

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

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

    const int INF = 1e9;
    for(int i=0; i<t; i++){
        int n;
        cin >> n;
        string s;
        cin >> s;

        vector<vector<int>> dp(n+1, vector<int>(3, INF));
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = 0;
        for(int j=0; j<n; j++){
            if(s[j]=='0'){
                dp[j+1][0] = dp[j][0];
                dp[j+1][1] = min(dp[j][0]+1, dp[j][1]+1);
                dp[j+1][2] = min(dp[j][1], dp[j][2]);
            }else if(s[j]=='1'){
                dp[j+1][0] = dp[j][0] + 1;
                dp[j+1][1] = min(dp[j][0], dp[j][1]);
                dp[j+1][2] = min(dp[j][1]+1, dp[j][2]+1);
            }
        }

        cout << min({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
    }
}

E: Minimum OR Path

解法

• Union-Find
• 2 進数表記したときの大きい桁から順に、使用しないでもよいかを判定する

ABC408E.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 u, v, w;
    for(int i=0; i<m; i++){
        cin >> u >> v >> w;
        u--;
        v--;
        V.emplace_back(u, v, w);
    }

    int ans = 0;
    for(int i=29; i>=0; i--){
        UnionFind uf(n);
        for(auto [u, v, w] : V){
            if(((w>>i)|(ans>>i))!=(ans>>i)){
                continue;
            }

            uf.unite(u, v);
        }

        if(!uf.same(0, n-1)){
            ans |= 1<<i;
        }
    }

    cout << ans << endl;

    return 0;
}