AtCoder Beginner Contest 399

## [A - Hamming Distance](https://atcoder.jp/contests/abc399/tasks/abc399_a)

O(N)
forループの問題です。
異なる時にカウントをする。

```math
S_i ≠ T_i
```

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;

    int ans = 0;
    rep(i, N){
        if(S[i] != T[i]) ans++;
    }
    cout << ans << endl;

    return 0;
} 
```

## [B - Ranking with Ties](https://atcoder.jp/contests/abc399/tasks/abc399_b)

O(N^2)

大きい要素の順に、順位をつけていきます。

|     |  1  |  2  |  3  |  4  |
|-----|-----|-----|-----|-----|
| P_i |  3  |  12  |  9  |  9  |
| ans |  4  |  1  |  2  |  2  |

1. 順位の決まっていない要素で最も大きい数字`x`を探索
2. `x`の要素に現在の順位をつける
3. 全ての要素に順位をつけたなら終了

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    rep(i, N) cin >> P[i];

    vector<int> ans(N, -1);
    int r = 1;
    while(1){
        int x = -1;
        rep(i, N){
            if(ans[i] != -1) continue;
            x = max(x, P[i]);
        }

        if(x == -1) break;
        int k = 0;
        rep(i, N){
            if(x == P[i]){
                ans[i] = r;
                k++;
            }
        } 

        r += k;
    }
    rep(i, N){
        cout << ans[i] << endl;
    }

    return 0;
} 
```

すぬけさんのコードを見て勉強しました。
凄い参考になりました。

## [C - Make it Forest](https://atcoder.jp/contests/abc399/tasks/abc399_c)

O(N+Mα(M))
UnionFindの問題です。
閉路とは、グラフ理論において始点と終点が同じ経路の事を
いいます。
UnionFindへ２点を追加する時に、同じグループに属していないか確認しましょう。
UnionFindのデータ構造を知っているか知っていないかの問題です。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

class UnionFind {
  private:
    vector<int> par_;
    
  public:
    UnionFind(int N) : par_(N) {
      rep(i, N)  par_[i] = i;
    }
    
    int root(int x){
      if(par_[x] == x) return x;
      return par_[x] = root(par_[x]);
    }
    
    void unite(int x, int y){
      int rx = root(x);
      int ry = root(y);
      
      if(rx == ry) return;
      par_[rx] = ry;
    }
    
    bool same(int x, int y){
      int rx = root(x);
      int ry = root(y);
      
      return rx == ry;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    
    int ans = 0;
    UnionFind uf(N);
    rep(i, M){
      int u, v;
      cin >> u >> v;
      u--; v--;
      if(uf.same(u, v)){
        ans++;
      }else{
        uf.unite(u, v);
      }
    }
    
    cout << ans << endl;
    return 0;
} 
```

## [D - Switch Seats](https://atcoder.jp/contests/abc399/tasks/abc399_d)

O(N)
組み合わせの問題です。
下記のテストケースを元に考察します。

```
3
3
1 2 3 3 2 1
4
1 1 2 2 3 3 4 4
5
1 2 3 4 5 1 2 3 4 5
```

テストケースの3行目、`1 2`と`2 1`の様な組み合わせの時にカウントします。
カウントしてはいけない組み合わせは、
テストケースの3行目の時、`2 3`、`3 3`、`3 2`の様な組み合わせです。

i-0からN*2-1までループして判定する組み合わせを探索しましょう。
`a1`と`a2`が等しい時は除外します。
`a1`と`a2`の順番が異なる時は揃えます。

```C++:C++
    set<pair<int, int>> st;
    rep(i, N*2-1){
        int a1 = A[i];
        int a2 = A[i+1];
        if(a1 == a2) continue;
        if(a1 > a2) swap(a1, a2);
        st.emplace(a1, a2);
    }
```

配列内の全ての組み合わせを探索しました。
ここから組み合わせの数字が隣り合っているか判定します。
各数字のインデックスを前処理で保持しておきます。

```C++:C++
    vector<vector<int>> P(N);
    rep(i, N*2) P[A[i]].push_back(i);
```

各数字のインデックスを見て、

- 同じ数字の要素が隣合っていた時は除外
- 組み合わせの数字のインデックスが隣り合っている

を判定して処理します。

```C++:C++
    int ans = 0;
    for(auto [x, y]:st){
        int xl = P[x][0], xr = P[x][1];
        int yl = P[y][0], yr = P[y][1];
        if(xl+1 == xr) continue;
        if(yl+1 == yr) continue;
        if(abs(xl-yl) == 1 && abs(xr-yr) == 1) ans++;
    }
```

考察が終わりました。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

void solve(int N, vector<int>& A){
    vector<vector<int>> P(N);
    rep(i, N*2) P[A[i]].push_back(i);

    set<pair<int, int>> st;
    rep(i, N*2-1){
        int a1 = A[i];
        int a2 = A[i+1];
        if(a1 == a2) continue;
        if(a1 > a2) swap(a1, a2);
        st.emplace(a1, a2);
    }

    int ans = 0;
    for(auto [x, y]:st){
        int xl = P[x][0], xr = P[x][1];
        int yl = P[y][0], yr = P[y][1];
        if(xl+1 == xr) continue;
        if(yl+1 == yr) continue;
        if(abs(xl-yl) == 1 && abs(xr-yr) == 1) ans++;
    }
    cout << ans << endl;
}

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

    rep(i, T){
        int N;
        cin >> N;
        vector<int> A(N*2);
        rep(i, N*2) cin >> A[i];
        rep(i, N*2) A[i]--;
        solve(N, A);
    }

    return 0;
} 
```

すぬけさんのコードを見て勉強しました。
凄い参考になりました。