AtCoder Beginner Contest 392

## [A - Shuffled Equation](https://atcoder.jp/contests/abc392/tasks/abc392_a)

O(logN)
配列Aをソートして、

```
A[i] * A[i+1] == A[i+2]
```
を判定します。

```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; }

int main() {
    int N = 3;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    sort(A.begin(), A.end());
    if(A[0] * A[1] == A[2]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
} 
```

## [B - Who is Missing?](https://atcoder.jp/contests/abc392/tasks/abc392_b)

O(NM)
配列Aをソートしましょう。
1~N+1までループAをします。
ループA内で1~MまでループBをします。

```
i == A[j]
```

の判定が一つでもtrueの時、`Aの要素として含まれている`ので出力結果に含めない。
出力結果の要素の数は、`N - A.size()`です。

```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; }

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    rep(i, M) cin >> A[i];
    sort(A.begin(), A.end());

    cout << N - A.size() << endl;
    repx(i, 1, N+1){
        int ok = 1;
        rep(j, M) if(i == A[j]) ok = 0;
        if(ok) cout << i << " ";
    }
    cout << endl;

    return 0;
} 
```

## [C - Bib](https://atcoder.jp/contests/abc392/tasks/abc392_c)

O(P)
配列Pと配列Qの間を補完する配列を用意しましょう。

```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; }

int main() {
    int N;
    cin >> N;
    vector<int> P(N), Q(N), mid(N);
    rep(i, N) cin >> P[i], P[i]--;
    rep(i, N) cin >> Q[i], Q[i]--;
    rep(i, N) mid[Q[i]] = i;
    rep(i, N) cout << Q[P[mid[i]]] + 1 << " ";
    cout << endl;
    return 0;
} 
```

## [D - Doubles](https://atcoder.jp/contests/abc392/tasks/abc392_d)

O(`N*N*K_i`)
`100*100*100000=10^9`
もしかして全探索で間に合うのでは？というのがスタート地点でした。

２つのサイコロを判定するためにO(N^2)のループをしましょう。
i, jの変数を使用したループとして、
jの目の種類を個数を連想配列mpへ探索しましょう。
A_iの目の要素をmpのキーとして探索し、個数の合計cntを求めます。

```
ans = max(ans, (double)cnt/(double)(K[i]*K[j]));
```

にて、「2つのサイコロの出目が等しくなる確率の最大値」を求めることができます。
少数8桁は、

```
fixed << setprecision((n))
```

で求めることができます。

```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; }

int main() {
    int N;
    cin >> N;
    vector<vector<ll>> A;
    vector<ll> K(N);
    rep(i, N){
        cin >> K[i];
        A.push_back(vector<ll>(K[i]));
        rep(j, K[i]){
            cin >> A[i][j];
        }
    } 

    double ans = 0.0;
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            map<ll, ll> mp;
            int M = A[j].size();
            for(int k=0; k<M; k++) mp[A[j][k]]++;
            ll cnt = 0;
            for(auto a:A[i]){
                if(mp.find(a) != mp.end()) cnt+=mp[a];
            }
            ans = max(ans, (double)cnt/(double)(K[i]*K[j]));
        }
    }
    cout << fixed_setprecision(8) << ans << endl;

    return 0;
} 
```

## [E - Cables and Servers](https://atcoder.jp/contests/abc392/tasks/abc392_e)

勉強中

```C++:C++
```