【ABC393】AtCoder Beginner Contest 393【C++】

### コンテスト名
AtCoder Beginner Contest 393

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

### 開催日
2025/02/15 21:00-22:40

---

## [A: Poisonous Oyster](https://atcoder.jp/contests/abc393/tasks/abc393_a)
**解法**
- 4 通りをすべて列挙して判定する
```cpp:ABC393A.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s1, s2;
    cin >> s1 >> s2;

    if(s1=="fine" && s2=="fine"){
        cout << 4 << endl;
    }else if(s1=="fine" && s2=="sick"){
        cout << 3 << endl;
    }else if(s1=="sick" && s2=="fine"){
        cout << 2 << endl;
    }else{
        cout << 1 << endl;
    }

    return 0;
}
```

## [B: A..B..C](https://atcoder.jp/contests/abc393/tasks/abc393_b)
**解法**
- `A`、`B`、`C` の位置をそれぞれ記録し、3 重ループで全探索する
```cpp:ABC393B.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

    vector<int> A, B, C;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='A'){
            A.push_back(i);
        }else if(s[i]=='B'){
            B.push_back(i);
        }else if(s[i]=='C'){
            C.push_back(i);
        }
    }

    int cnt = 0;
    for(int i=0; i<A.size(); i++){
        for(int j=0; j<B.size(); j++){
            for(int k=0; k<C.size(); k++){
                if(A[i]<B[j] && B[j]<C[k] && B[j]-A[i]==C[k]-B[j]){
                    cnt++;
                }
            }
        }
    }

    cout << cnt << endl;

    return 0;
}
```

## [C: Make it Simple](https://atcoder.jp/contests/abc393/tasks/abc393_c)
**解法**
- `set<pair<int, int>>` に辺を記録する
    - $u_i \leqq v_i$ となるようにしてから記録する
- 自己ループは不要であるため、記録せずに無視する
```cpp:ABC393C.cpp
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

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

    int u, v;
    set<pair<int, int>> S;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        u--;
        v--;

        if(u==v){
            continue;
        }

        if(u>v){
            swap(u, v);
        }
        S.emplace(u, v);
    }
    
    cout << m - S.size() << endl;

    return 0;
}
```

## [D: Swap to Gather](https://atcoder.jp/contests/abc393/tasks/abc393_d)
**解法**
- `1` だけを抜き出した配列を考えたときの中央値の位置にすべての `1` を集める
```cpp:ABC393D.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

    vector<int> V;
    for(int i=0; i<n; i++){
        if(s[i]=='1'){
            V.push_back(i);
        }
    }

    int size = V.size();
    int mid = V[size/2];

    long long int cnt = 0;
    if(size%2==0){
        int half = size/2;
        for(int i=0; i<half; i++){
            cnt += (mid-half+i) - V[i];
        }
        for(int i=half+1; i<V.size(); i++){
            cnt += V[i] - (mid+half-1-(size-i-1));
        }
    }else{
        int half = size/2;
        for(int i=0; i<half; i++){
            cnt += (mid-half+i) - V[i];
        }
        for(int i=half; i<V.size(); i++){
            cnt += V[i] - (mid+half-(size-i-1));
        }
    }

    cout << cnt << endl;

    return 0;
}
```

## [E: GCD of Subset](https://atcoder.jp/contests/abc393/tasks/abc393_e)
**解法**
- 動的計画法 (DP)
- $C[i]$ := $A$ に含まれる $i$ の倍数の個数
- $V[i]$ := $i$ を含むように $K$ 個の要素を $A$ から選ぶときの最大公約数の最大値
```cpp:ABC393E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    int maxv = *max_element(A.begin(), A.end());
    vector<int> C(maxv+1);
    for(int i=0; i<n; i++){
        C[A[i]]++;
    }
    for(int i=1; i<=maxv; i++){
        for(int j=2; j<=maxv/i; j++){
            C[i] += C[i*j];
        }
    }

    vector<int> ans(maxv+1);
    for(int i=1; i<=maxv; i++){
        if(C[i]>=k){
            ans[i] = i;
        }
    }
    for(int i=maxv; i>=1; i--){
        for(int j=2; j<=maxv/i; j++){
            ans[i*j] = max(ans[i*j], ans[i]);
        }
    }
    
    for(int i=0; i<n; i++){
        cout << ans[A[i]] << '\n';
    }

    return 0;
}
```