【ABC344】AtCoder Beginner Contest 344【C++】

### コンテスト名
トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）

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

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

---

## [A: Spoiler](https://atcoder.jp/contests/abc344/tasks/abc344_a)
**解法**
- `|` を通過した回数で判別する
  - 1 回目の `|` から 2 回目の `|` までは出力しない

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

int main(){
    string s;
    cin >> s;
    bool flag = true;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='|'){
            flag = !flag;
        }else if(flag){
            cout << s[i];
        }
    }

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

## [B: Delimiter](https://atcoder.jp/contests/abc344/tasks/abc344_b)
**解法**
- `0` が入力されるまで `while` 文で `vector<int>` に読み込み続ける
- 逆順に出力

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

int main(){
    int x;
    vector<int> V;
    do{
        cin >> x;
        V.push_back(x);
    }while(x!=0);

    for(int i=V.size()-1; i>=0; i--){
        cout << V[i] << endl;
    }

    return 0;
}
```

## [C: A+B+C](https://atcoder.jp/contests/abc344/tasks/abc344_c)
**解法**
- 全探索
- そのまま 4 重ループにすると計算量は $O(NMLQ)$ になってしまう
- 数列 $A, B, C$ からそれぞれ 1 個ずつ要素を選んで作成できる和を `unordered_set<int>` で管理する
- `count(X_i)` で判別する
- 計算量は $O(NML + Q)$

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

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

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

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

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

    int sum;
    unordered_set<int> S; 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            for(int k=0; k<l; k++){
                sum = A[i]+B[j]+C[k];
                S.insert(sum);
            }
        }
    }

    for(int i=0; i<q; i++){
        if(S.count(X[i])){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}
```

## [D: String Bags](https://atcoder.jp/contests/abc344/tasks/abc344_d)
**解法**
- 動的計画法 (DP)
- $dp[i][k] :=$ 袋 $i$ までを用いて文字列 $T$ の $k$ 文字目までを作成するために必要な最小の金額
- 計算量は $O(NA|T||S|)$

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

string t;

bool check(int num, string s){
    if(t.size()<s.size()){
        return false;
    }

    string sub = t.substr(num, s.size());
    if(sub==s){
        return true;
    }

    return false;
}

int main(){
    cin >> t;

    int n;
    cin >> n;

    const int inf = t.size()+1;
    vector<vector<int>> dp(n+1, vector<int>(t.size()+1, inf));
    dp[0][0] = 0;

    int x;
    string s;
    for(int i=0; i<n; i++){
        cin >> x;
        for(int k=0; k<=t.size(); k++){
            dp[i+1][k] = dp[i][k];
        }
        for(int j=0; j<x; j++){
            cin >> s;
            for(int k=0; k<=t.size(); k++){
                if(check(k, s)){
                    dp[i+1][k+s.size()] = min(dp[i+1][k+s.size()], dp[i][k]+1);
                }
            }
        }
    }

    if(dp[n][t.size()]<inf){
        cout << dp[n][t.size()] << endl;
    }else{
        cout << -1 << endl;
    }
    
    return 0;
}
```

## [E: Insert or Erase](https://atcoder.jp/contests/abc344/tasks/abc344_e)
**解法**
- 双方向連結リストを実装する
- 前の要素と後ろの要素をそれぞれ `unordered_map<int, int>` で管理する
- 両端の番兵には `0` を利用できる
  - 制約条件からどの時点においても $1 \leqq A_i \leqq 10^9$ であり `0` が要素になることはないため

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

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

    unordered_map<int, int> F, B;
    F[0] = A[0];
    F[A[n-1]] = 0;
    B[A[0]] = 0;
    B[0] = A[n-1];
    for(int i=0; i<n-1; i++){
        F[A[i]] = A[i+1];
        B[A[i+1]] = A[i];
    }

    int q;
    cin >> q;
    int num, x, y;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> x >> y;
            F[y] = F[x];
            B[F[x]] = y;
            F[x] = y;
            B[y] = x;
        }else if(num==2){
            cin >> x;
            B[F[x]] = B[x];
            F[B[x]] = F[x];
        }
    }

    int a = 0, cnt = 0;
    do{
        if(cnt){
            cout << " ";
        }
        cnt++;
        cout << F[a];
        a = F[a];
    }while(F[a]);

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