AtCoder 生活　67日目

[前回](https://qiita.com/flandrescarlet237/items/4c22dff7f8c0108dcee1)

#67日目
今回はD問題を2問解き、とバーチャル参加を2回しました。

|問題|難易度|自力で解けた|かかった時間|
|:-:|:-:|:-:|---|---|
|ABC161|D|✕|139分4秒|
|ABC157|D|✕|170分|

![スクリーンショット 2020-05-27 12.56.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/851a3d5b-3ee9-2c28-ad17-a0fe9eb51262.png)
![スクリーンショット 2020-05-27 14.58.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/f4fabc30-fc62-8c96-aa07-c5908a5246c5.png)


##[ABC147](https://atcoder.jp/contests/abc147)

###A

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a+b+c < 22) cout << "win" << endl;
    else cout << "bust" << endl;
}

```

###B


```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    string s,t;
    cin >> s;
    t = s;
    reverse(t.begin(),t.end());
    int a = t.size;
    int c = 0;
    rep(i,a){
        if(s[i] != t[i])c++;
    }
    c /= 2;
    cout << c << endl;
}

```


##[ABC146](https://atcoder.jp/contests/abc146)

###A

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    string s;
    cin >> s;
    if(s == "SUN")cout << 7;
    if(s == "MON")cout << 6;
    if(s == "TUE")cout << 5;
    if(s == "WED")cout << 4;
    if(s == "THU")cout << 3;
    if(s == "FRI")cout << 2;
    if(s == "SAT")cout << 1;
}

```

###B


```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    int n;
    string s;
    cin >> n >> s;
    int t = s.size();
    rep(i,t){
        if(s[i]+n <= 'Z') cout << char(s[i]+n);
        else cout << char(s[i]+n-'Z'+'A'-1);
    }
}

```

##[ABC161_D](https://atcoder.jp/contests/abc161/tasks/abc161_d)

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main() {
    int k;
    cin >> k;
    queue<ll> a;
    for (int i = 1; i < 10; ++i) a.push(i);
    rep(i,k-1){
        ll s = a.front();
        a.pop();
        for (int j = -1; j <= 1; j++) {
            ll add = (s % 10) + j;
            if (add >= 0 && add <= 9) a.push(s * 10 + add);
        }
    }
    cout << a.front() << endl;
}

```

解くのにかかった時間：139分4秒
感想：何故か書き写したときはTLEになった


##[ABC157_D](https://atcoder.jp/contests/abc157/tasks/abc157_d)

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

struct UnionFind {
    vector<int> d;
    UnionFind(int n): d(n,-1) {}
    int find(int x){
        if(d[x] < 0) return x;
        return find(d[x]);
    }
    bool unite(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y);}
    int size(int x) { return -d[find(x)];}
};

int deg[100005];
vector<int> to[100005];

int main(){
    int n,m,k;
    cin >> n >> m >> k;
    UnionFInd uf(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        deg[a]++;
        deg[b]++;
        uf.unite(a,b);
    }
    rep(i,k){
        int a,b;
        cin >> a >> b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    rep(i,n){
        int ans = uf.size(i) - 1 - deg[i];
        for(int u : to[i]){
            if(uf.same(i,u)) ans--;
        }
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

```

解くのにかかった時間：170分
感想：友達候補の条件が、友達を伝ってたどり着けることと友達ではないということだと問題から読み解けなかった。
今回はじめてUnionFindに触った


###最後に
UnionFindを今回はじめて知った。理解を深めるためにまたやりたい