ABC392個人的備忘録

周りの速さに食らいついた男の備忘録です

### コンテスト概要
日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）

https://atcoder.jp/contests/abc392

開催日:2025年2月8日 21:00-22:40

## [A - Shuffled Equation](https://atcoder.jp/contests/abc392/tasks/abc392_a)
#### 考察
３つの数のうち一番大きいものが積になる必要がある。
なので３つの数をソートしたもの$[A,B,C]$が$A*B=C$になっているかを確認。

#### 提出
``` c++:A.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int>num (3);
    for(int i = 0;i<3;i++) cin >> num[i];
    sort(num.begin(),num.end());

    //小さい二つの積と大きい数を比べる
    if(num[0]*num[1] == num[2]) cout << "Yes" << endl;
    else cout << "No" <<  endl;
}
```

## [B - Who is Missing?](https://atcoder.jp/contests/abc392/tasks/abc392_b)
#### 考察
Aの数はすべて違うことが保証されている。なので呼ばれてない数は$n-m$個である。
何かしらで既に呼ばれた数字を管理しておき、それ以外を出力。

#### 提出
``` c++:B.cpp
#include <bits/stdc++.h>
using namespace std;

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

    //呼ばれないのはn-m個
    cout << n  - m << endl;
    map<int,bool>mp;
    for(int i=0;i<m;i++){
        int x;
        cin >> x;
        //数字が呼ばれたかを管理
        mp[x] = true;
    }

    for(int i=1;i<=n;i++){
        //呼ばれてなければ出力
        if(!mp[i]) cout << i << endl;
    }    
}
```

## [C - Bib](https://atcoder.jp/contests/abc392/tasks/abc392_c)
#### 考察
言われた通りにすればいい。
ただ参照元で参照するので混乱しないよう落ち着いて処理。

#### 提出
``` c++:C.cpp
#include <bits/stdc++.h>
using namespace std;

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

    //前からi番目の人が誰を見ているか、何番のゼッケンかを管理
    vector<int>gz (n),num (n);
    map<int,int>mp;
    for(int i=0;i<n;i++) cin >> gz[i];
    for(int i=0;i<n;i++){
        cin >> num[i];
        mp[num[i]] = i;
    }

    for(int i=1;i<=n;i++){
        //i番目の人が見ている人がつけているゼッケンを出力
        cout << num[gz[mp[i]] - 1] << endl;
    }
    
}
```

## [D - Doubles](https://atcoder.jp/contests/abc392/tasks/abc392_d)
#### 考察
さいころは100個しかないので二重ループで組み合わせを全探査。
さいころごとに出目の数を数えておき、(同じで目の通り数)/(2つの出目の通り数)をチェック。
$10^7$個のデータが通るか不安だったが意外とOKだった。
だったら変にこねくり回さなければよかった(2敗)

#### 提出
``` c++:D.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<ll>num (n);
    //さいころiの出目の一覧
    vector<set<int>>dc (n);
    //さいころiに出目jがいくつ出るか？
    vector<vector<ll>>cnt (n,vector<ll>(100001,0));

    for(int i=0;i<n;i++){
        cin >> num[i];

        for(int j=0;j<num[i];j++){
            int x;
            cin >> x;
            dc[i].insert(x);
            cnt[i][x]++;
        }
    }

    double ans = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            double d = num[i]*num[j];
            double sum = 0;

            //さいころiの出目だけに注目しぞろ目をチェック
            for(auto x:dc[i]){
                sum += cnt[i][x] * cnt[j][x];
            }
            ans = max(ans,sum/d);
        }
    }

    cout << fixed << setprecision(9) << ans << endl;    
}
```

## [E - Cables and Servers](https://atcoder.jp/contests/abc392/tasks/abc392_e)
#### 考察
とりあえずすべてのサーバーがつながっているかをUnion-Findでチェック。
つながっていないなら無駄なケーブルを別のサーバーグループに接続。
無駄なケーブルに関しては初め2つのサーバーを結ぶときに確認。
すでに同じグループなら無駄なケーブルリストに追加を繰り返す。

最後に無駄なケーブルが多い順にとりあえずつないでいく。方法としては無駄なケーブルの片方を外し別グループの親に接続。

REが全く取れず困る。25分でDまで通していたのでまあ何とかなるだろうと思っていたが2500位。突然焦る。
Fを通した後意地でREを修正。残り1分。危なかった。

#### 提出
``` c++:E.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<int,int>>num;

struct UF{
    vector<int>par;
    vector<vector<int>>ws;
    //親かどうかの確認用（正直いらんかった）
    vector<bool>st;
    //グループの数を管理    
    int siz;

    UF(int n):par(n),ws(n,vector<int>(0)),st(n,true){
        for(int i=0;i<n;i++){
            par[i] = i;
            st[i] = true;
        }

        siz = n;
    }

    int root(int n){
        if(par[n] == n) return n;
        return par[n]  = root(par[n]);
    }

    void unite(int n,int m,int x){
        int rn = root(n),rm = root(m);
        if(rn == rm){
            ws[rn].push_back(x);
            return;            
        }

        par[rn] = rm;
        st[rn] = false;
        siz--;
        //無駄なケーブルを親に伝える
        if(ws[rn].size() != 0) ws[rm].insert(ws[rm].end(),ws[rn].begin(),ws[rn].end());
        return;
    }

    void ans(int n){
        cout << siz - 1 << endl;
        if(siz == 1) return;

        priority_queue<pair<int,int>> que;
        for(int i=0;i<n;i++){
            if(!st[i]) continue;
            que.push({ws[i].size(),i});
        }

        //一番無駄なケーブルが多いものからケーブルをつなぐ
        auto [s,pos] = que.top();
        que.pop(); 

        while(!que.empty()){
            auto [x,y] = que.top();
            que.pop();

            //ケーブルの無駄なものを一本つなぎなおす。
            int t = ws[pos].back();
            ws[pos].pop_back();
            unite(y,pos,0);

            cout << t+1 << " " << num[t].first + 1 << " " << y + 1 << endl;
        }
        return;
    }
};


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

    num.resize(m);
    UF tree(n);

    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        x--,y--;

        tree.unite(x,y,i);
        num[i] = {x,y};
    }

    tree.ans(n);
}
```

## [F - Insert](https://atcoder.jp/contests/abc392/tasks/abc392_f)
#### 考察
前からやっていくと席移動が発生してめんどくさい。なので後ろから座ってもらう。
後ろから考えれば「空いてる中で前からi番目に座る」を繰り返せばよい。
前からi番目は何らかの高速な方法を使えばOK。私はいいのが思いつかずセグメントツリーと二分探査のごり押しでAC。

#### 提出
``` c++:F.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct ST_SUM{
    vector<ll>num;
    int siz;

    ST_SUM(int n){
        int x = 1;
        while(n > x) x <<= 1;
        
        siz = x; 
        num = vector<ll> ((x<<1),0LL); 
    }

    void Update(int x,ll i){ 
        x = x + siz - 1; 
        num[x] = i; 
        while(x != 0){
            x = (x-1)/2; //一段上に上がる
            num[x] = num[x*2 + 1]+num[x*2 + 2]; 
        }
    }

    ll Serch(int n,int m,int k,int l,int r){
        if(r <= n || m <= l) return 0; 
        if(n <= l && r <= m) return num[k]; 
        k *= 2;
        int lx = Serch(n, m, k+1, l, (r+l)/2); 
        int rx = Serch(n, m, k+2, (l+r)/2, r); 

        return lx + rx;
    }

    ll Origin_Serch(int n,int m){
        return Serch(n, m+1, 0, 0, siz); 
    }
};


int main(){
    int n;
    cin >> n;
    vector<int> num (n);

    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        x--;
        num[i] = x;
    }
    vector<int> ans (n,0);

    //埋まった席がいくつあるかを確認する用
    ST_SUM tree(n);
    for(int i = n-1;i>-1;i--){
        int h = 0,t = n-1;
        while(h != t){
            int c = (h+t) / 2;

            //前からC席までに何席埋まっているかをチェック
            int k = tree.Origin_Serch(0,c);
            //num[i]席空いているかの確認
            if(c-k >= num[i]) t = c;
            else h = c + 1;
        }

        //h番目が前からnum[i]番目である。
        ans[h] = i+1;
        //h番目に座る。
        tree.Update(h,1);        
    }

    for(auto x:ans) cout << x << endl;    
}
```

## 結果
ABCD(2)E(2)F 6完　117:55

順位 1331位
パフォーマンス　1467

## 感想
人生初6完&入水やったー。
E問題の途中2500位だったときは絶望していたが何とか巻き返した。

落緑しないように頑張るぞ