AtCoder Beginner Contest 344

## [A - Spoiler](https://atcoder.jp/contests/abc344/tasks/abc344_a)

'|'の間だけ出力をしないようにしましょう。

```C++:C++
#include <bits/stdc++.h>
 
#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
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
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() {
    string s;
    cin >> s;

    int cnt=0;
    rep(i, s.size()){
        if(s[i] == '|'){
            cnt++;
            continue;
        }
        switch (cnt)
        {
        case 0:
            cout << s[i];
            break;
        case 2:
            cout << s[i];
            break;
        default:
            break;
        }
    }
    cout << endl;

    return 0;
} 
```

## [B - Delimiter](https://atcoder.jp/contests/abc344/tasks/abc344_b)

0を終端にしましょう。
vectorでもデキューでもいいので逆順に出力しましょう。

```C++:C++
#include <bits/stdc++.h>
 
#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
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
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() {
    deque<int> que;

    while(1){
        int a;
        cin >> a;
        que.push_front(a);
        if(a==0) break;
    }

    while(que.size()){
        cout << que.front() << endl;
        que.pop_front();
    }
    
    return 0;
} 
```

## [C - A+B+C](https://atcoder.jp/contests/abc344/tasks/abc344_c)

N<=100の制約です。
N^3=1000000の計算量です。
まずは全ての組み合わせを前処理で計算します。
重複を除くためにsetのデータ構造を使用します。
setにあるデータにXのデータが存在するか二分探索で検索しましょう。

```C++:C++
#include <bits/stdc++.h>
 
#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
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
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() {
    ll N, M, L, Q;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    cin >> M;
    vector<ll> B(M);
    rep(i, M) cin >> B[i];
    cin >> L;
    vector<ll> C(L);
    rep(i, L) cin >> C[i];
    cin >> Q;
    vector<ll> D(Q);
    rep(i, Q) cin >> D[i];

    set<ll> st;
    rep(i, N){
        rep(j, M){
            rep(k, L){
                st.insert(A[i]+B[j]+C[k]);
            }
        }
    }

    rep(i, Q){
        auto itr = st.find(D[i]);
        if(itr == st.end()) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
} 
```

 ## [D - String Bags](https://atcoder.jp/contests/abc344/tasks/abc344_d)

 動的計画法の問題です。
 漸化式を組みましょう。

 ```
 dp[ 袋を何個目まで処理したか ][ T の接頭辞のうちどこまで一致させられたか ]= { 必要な最小金額 } 
 ```

1 <= T <= 100 
1 <= N <= 100 
1 <= A <= 10
1 <= S_i_j <= 10

の制約として、
ループN, ループA, ループT, ループS_i_j
とループしても、
100 *　10 * 100 * 10 = 1000000
間に合いますね

```C++:C++
#include <bits/stdc++.h>
 
#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
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
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() {
    string T;
    int N;
    cin >> T >> N;

    vector<vector<ll>> dp(101, vector<ll>(101, 1e9));
    for(int i=0; i<101; i++) for(int j=0; j<101; j++) dp[i][j] = 1e9;
    dp[0][0] = 0;

    rep(i, N){
        for(int j=0; j<101; j++) dp[i+1][j] = dp[i][j];
        int a;
        cin >> a;
        for(int j=0; j<a; j++){
            string s;
            cin >> s;
            for(int k=0; k+s.size()<=T.size(); k++){
                int ok=1;
                for(int l=0; l<s.size(); l++){
                    if(T[k+l] != s[l]){
                        ok=0;
                        break;
                    }
                }
                if(ok){
                    dp[i+1][k+s.size()] = min(dp[i+1][k+s.size()], dp[i][k]+1);
                }
            }
        }
    }
    if(dp[N][T.size()]>=1e9) dp[N][T.size()]=-1;
    cout << dp[N][T.size()] << endl;
    return 0;
} 
```