【ABC350】AtCoder Beginner Contest 350【C++】

### コンテスト名
AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

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

### 開催日
2024/04/20 21:00-22:40

---

## [A: Past ABCs](https://atcoder.jp/contests/abc350/tasks/abc350_a)
**解法**
- `ABC000` や `ABC316` に注意する
1. 1 文字ずつ `int` 型に変換して番号を計算する方法
2. 部分文字列を求めてから `int` 型に変換する方法

```cpp:ABC350A_1.cpp
#include <iostream>
#include <string>
using namespace std;

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

    int num = 0;
    num += (s[3]-'0')*100;
    num += (s[4]-'0')*10;
    num += (s[5]-'0');

    if(num>0 && num<350 && num!=316){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
```

```cpp:ABC350A_2.cpp
#include <iostream>
#include <string>
using namespace std;

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

    int num = stoi(s.substr(3, 3));

    if(num>0 && num<350 && num!=316){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
```

## [B: Dentist Aoki](https://atcoder.jp/contests/abc350/tasks/abc350_b)
**解法**
- 歯の状態を `vector<int>` で管理してシミュレーションする

```cpp:ABC350B.cpp
#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> V(n, 1);
    int t;
    for(int i=0; i<q; i++){
        cin >> t;
        t--;
        if(V[t]==0){
            V[t]++;
        }else{
            V[t]--;
        }
    }

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

    cout << sum << endl;
    return 0;
}
```

## [C: Sort](https://atcoder.jp/contests/abc350/tasks/abc350_c)
**解法**
- 前から順番に正しい番号に入れ替える
- `unordered_map<int, int>` で各整数がどこにあるかを記録する

```cpp:ABC350C.cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

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

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

    vector<pair<int, int>> V;
    for(int i=0; i<n; i++){
        if(A[i]!=i){
            V.emplace_back(i+1, M[i]+1);
            M[A[i]] = M[i];
            A[M[i]] = A[i];
            M[i] = i;
            A[i] = i;
        }
    }

    cout << V.size() << endl;
    for(auto [x, y] : V){
        cout << x << " " << y << '\n';
    }

    return 0;
}
```

## [D: New Friends](https://atcoder.jp/contests/abc350/tasks/abc350_d)
**解法**
- 人を頂点、友人関係を辺としたグラフを考える
- 各連結成分を完全グラフにすることを考える
- 各連結成分の頂点数を $V$ 、辺数を $E$ とすると全体の合計操作数は $\sum ({}_V \mathrm{C}_2 - E) = \sum {}_V \mathrm{C}_2 - M$
  - 各連結成分を完全グラフにするために加える辺数を求める
      - 完全グラフになったときの辺数からすでにある辺数を引く
      - すでにある辺数は連結成分ごとに求めなくても合計で $M$ 本あるとわかっている
1. Union-Find
    - Union-Find で各連結成分の頂点数を求める
    - 連結成分ごとに 1 回ずつ加算するために頂点が連結成分の根のときだけ `size()` を求める
2. 深さ優先探索 (DFS)
    - DFS で頂点数と辺数を同時に求める
    - 辺数は 2 重にカウントされているため 2 で割る

```cpp:ABC350D_1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
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;

    UnionFind uf(n);
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        b--;
        uf.unite(a, b);
    }

    long long int sum = 0;
    for(int i=0; i<n; i++){
        if(uf.find(i)==i){
            int cnt = uf.size(i);
            sum += (long long int)cnt*(cnt-1)/2;
        }
    }

    sum -= m;

    cout << sum << endl;
    return 0;
}
```

```cpp:ABC350D_2.cpp
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> G;
vector<int> seen;

void dfs(int v, int &vcnt, int &ecnt){
    seen[v] = 1;
    vcnt++;

    for(int i=0; i<G[v].size(); i++){
        int next = G[v][i];
        ecnt++;
        if(seen[next]){
            continue;
        }
        dfs(next, vcnt, ecnt);
    }
}

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

    int a, b;
    G.resize(n);
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    seen.resize(n);
    long long int sum = 0;
    for(int i=0; i<n; i++){
        if(seen[i]){
            continue;
        }

        int vcnt = 0, ecnt = 0;
        dfs(i, vcnt, ecnt);
        ecnt /= 2;
        sum += (long long int)vcnt*(vcnt-1)/2 - ecnt;
    }

    cout << sum << endl;
    return 0;
}
```

## [E: Toward 0](https://atcoder.jp/contests/abc350/tasks/abc350_e)
**解法**
- メモ化再帰
- 問題文から漸化式を考える
  - $X$ 円を払う操作： $f(N) = X + f(\lfloor \frac{N}{A} \rfloor)$
  - $Y$ 円を払う操作： $f(N) = Y + \lbrace \frac{1}{6} f(\lfloor \frac{N}{1} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{6} \rfloor) \rbrace$
    - 両辺に $f(N) = f(\lfloor \frac{N}{1} \rfloor)$ があるため右辺の $f(\lfloor \frac{N}{1} \rfloor)$ を移項すると $\frac{5}{6} f(N) = Y + \lbrace \frac{1}{6} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{6} f(\lfloor \frac{N}{6} \rfloor) \rbrace$
    -  両辺に $\frac{6}{5}$ をかけて $f(N) = \frac{6}{5} Y + \lbrace \frac{1}{5} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{6} \rfloor) \rbrace$
- $f(N) = min(X + f(\lfloor \frac{N}{A} \rfloor), \frac{6}{5} Y + \lbrace \frac{1}{5} f(\lfloor \frac{N}{2} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{3} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{4} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{5} \rfloor) + \frac{1}{5} f(\lfloor \frac{N}{6} \rfloor) \rbrace)$
- 小数の扱いに注意する

```cpp:ABC350E.cpp
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstdio>
using namespace std;

int a, x, y;
unordered_map<long long int, double> M;

double f(long long int n){
    if(n==0){
        return 0;
    }

    if(M.count(n)){
        return M[n];
    }

    return M[n] = min(x + f(n/a), (double)6/5*y + (double)1/5*f(n/2) + (double)1/5*f(n/3) + (double)1/5*f(n/4) + (double)1/5*f(n/5) + (double)1/5*f(n/6));
}

int main(){
    long long int N;
    cin >> N >> a >> x >> y;

    printf("%.10f\n", f(N));
    return 0;
}
```