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

### コンテスト名
AtCoder Beginner Contest 408

### コンテストURL
https://atcoder.jp/contests/abc408

### 開催日
2025/05/31 21:00–22:40

---

## [A: Timeout](https://atcoder.jp/contests/abc408/tasks/abc408_a)
**解法**
- $T_{i+1} - T_i$ と $S$ の関係で判定する
- $T_1$ の判定に注意する
```cpp: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](https://atcoder.jp/contests/abc408/tasks/abc408_b)
**解法**
- `set<int>` で管理する
```cpp: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](https://atcoder.jp/contests/abc408/tasks/abc408_c)
**解法**
- いもす法
- 最も守っている砲台の数が少ない城壁を守っている砲台の数が答えである
```cpp: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](https://atcoder.jp/contests/abc408/tasks/abc408_d)
**解法**
- 動的計画法 (DP)
- `1` のかたまりを中央につくることを考える
- $\text{dp}[i][j]$ := $i$ 番目の状態が $j$ であるときの $i$ 番目までの操作回数の最小値
    - $j=0$ ：`1` のかたまりの左の `0` のかたまりに属する
    - $j=1$ ：`1` のかたまりに属する
    - $j=2$ ：`1` のかたまりの右の `0` のかたまりに属する
```cpp: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](https://atcoder.jp/contests/abc408/tasks/abc408_e)
**解法**
- Union-Find
- 2 進数表記したときの大きい桁から順に、使用しないでもよいかを判定する
```cpp: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;
}
```