【ABC347】AtCoder Beginner Contest 347【C++】

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

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

### 開催日
2024/03/30 21:00-22:40

---

## [A: Divisible](https://atcoder.jp/contests/abc347/tasks/abc347_a)
**解法**
- 問題文通りに実装する

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

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

    int a, cnt = 0;
    for(int i=0; i<n; i++){
        cin >> a;
        if(a%k==0){
            if(cnt){
                cout << " ";
            }
            cout << a/k;
            cnt++;
        }
    }

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

## [B: Substring](https://atcoder.jp/contests/abc347/tasks/abc347_b)
**解法**
- `substr()` で部分文字列をすべて求めて `unordered_set<string>` で重複を除く

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

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

    unordered_set<string> S;
    for(int i=0; i<s.size(); i++){
        for(int j=1; i+j-1<s.size(); j++){
            S.insert(s.substr(i, j));
        }
    }

    cout << S.size() << endl;
    return 0;
}
```

## [C: Ideal Holidays](https://atcoder.jp/contests/abc347/tasks/abc347_c)
**解法**
- 各 $D_i$ に対して $mod (A + B)$ をとる
1. 最小値と最大値の差が $A$ 日におさまるかを確かめる
    - 週をまたぐケースは $+A$ して対処する
2. 予定がない日が連続して $B$ 日以上あるかを確かめる
    - 週をまたぐケースは 2 週分考えることで対処する

```cpp:ABC347C_1.cpp
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n, a, b;
    cin >> n >> a >> b;

    int d;
    int minv = a+b, maxv = 0, minv2 = a+b, maxv2 = 0;
    for(int i=0; i<n; i++){
        cin >> d;
        minv = min(minv, d%(a+b));
        maxv = max(maxv, d%(a+b));
        minv2 = min(minv2, (d+a)%(a+b));
        maxv2 = max(maxv2, (d+a)%(a+b));
    }

    if(maxv-minv<a || maxv2-minv2<a){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
```

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

int main(){
    int n, a, b;
    cin >> n >> a >> b;

    vector<long long int> D(2*n);
    for(int i=0; i<n; i++){
        cin >> D[i];
        D[i] %= (a + b);
        D[i+n] = D[i] + a + b;
    }

    sort(D.begin(), D.end());
    for(int i=0; i<D.size()-1; i++){
        if(D[i+1]-D[i]>b){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}
```

## [D: Popcount and XOR](https://atcoder.jp/contests/abc347/tasks/abc347_d)
**解法**
- $C$ の $i$ 桁目が `1` ならば $X$ の $i$ 桁目か $Y$ の $i$ 桁目の一方が `1` で他方が `0`
- $C$ の $i$ 桁目が `0` ならば $X$ の $i$ 桁目と $Y$ の $i$ 桁目の両方が `1` か両方が `0`
- `1LL` に注意する
- $XOR$ は可換
- $0 \leqq X, Y, C < 2^{60}$ より 60 桁までだから $a + b + popcount(C) \leqq 120$
- $X \oplus Y = C$ より $popcount(C) \leqq a + b, a \leqq b + popcount(C), b \leqq popcount(C) + a$
1. $C$ の `1` である桁を $X$ か $Y$ のいずれかに `1` として振り分ける
2. $X$ と $Y$ が未完成ならば $C$ の `0` である桁を $X$ と $Y$ の両方に `1` として振り分ける

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

int main(){
    long long int a, b, c;
    cin >> a >> b >> c;

    int cnt = 0;
    for(int i=0; i<60; i++){
        if(c & (1LL<<i)){
            cnt++;
        }
    }
    
    int diff = (a + b) - cnt;
    if(diff%2!=0 || a+b+cnt>120 || a>b+cnt || b>a+cnt || cnt>a+b){
        cout << -1 << endl;
        return 0;
    }
    diff /= 2;

    long long int x = 0, y = 0;
    cnt = 0;
    for(int i=0; i<60; i++){
        if(c & (1LL<<i)){
            x += (1LL<<i);
            if(cnt<(b-diff)){
                y += (1LL<<i);
            }
            cnt++;
        }
    }

    x -= y;

    long long int z = 0;
    cnt = 0;
    for(int i=0; i<60; i++){
        if(cnt==diff){
            break;
        }
        if(!(c & (1LL<<i))){
            z += (1LL<<i);
            cnt++;
        }
    }

    x += z;
    y += z;

    cout << x << " " << y << endl;

    return 0;
}
```

## [E: Set Add Query](https://atcoder.jp/contests/abc347/tasks/abc347_e)
**解法**
- 累積和
- 先に集合 $S$ の要素の増減を `unordered_set<int>` でシミュレーションする
- 各値の追加と削除を `vector<vector<int>>` に記録する
- 最後まで集合 $S$ に含まれていた値の計算に注意する
  - $Q + 1$ 個目のクエリで削除されたものと考える

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

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

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

    unordered_set<int> S;
    vector<vector<int>> V(n);
    vector<long long int> cnt(q+1);
    for(int i=0; i<q; i++){
        if(S.count(X[i])){
            S.erase(X[i]);
            V[X[i]].push_back(i);
        }else{
            S.insert(X[i]);
            V[X[i]].push_back(i);
        }
        cnt[i+1] = S.size();
    }

    for(int i=0; i<n; i++){
        if(V[i].size()%2==1){
            V[i].push_back(q);
        }
    }

    for(int i=0; i<q; i++){
        cnt[i+1] += cnt[i];
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<V[i].size(); j+=2){
            A[i] += (cnt[V[i][j+1]]-cnt[V[i][j]]);
        }
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }
    
    cout << endl;
    return 0;
}
```