AtCoder Beginner Contest 346

## [A - Adjacent Product](https://atcoder.jp/contests/abc346/tasks/abc346_a)

O(N)
ループで表示をしましょう。

```
表示　 = A[i] * A[i+1]
```

```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() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    rep(i, N-1){
        cout << A[i] * A[i+1];
        if(i < N-2) cout << ' ';
    }
    cout << endl;

    return 0;
} 
```

## [B - Piano](https://atcoder.jp/contests/abc346/tasks/abc346_b)

O(N)
wbwbwwbwbwbwは12文字。
w=7個、b=5個です。
0≤W,B≤100の制約の為、B＝100の時のWの数は、

```
Wの数 = 7 * (B=100 / b=5個) = 140
```

となります。
文字数の最大値は、140 + 100 = 240が最大値になります。
wbwbwwbwbwbwを240文字以上になるように繋ぎ合わせて文字列Tを作成します。
文字列Tを全探索しましょう。

```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() {
    int W, B;
    cin >> W >> B;
    if(W == 0 && B == 0){
        cout << "Yes" << endl;
        return 0;
    }

    string S;
    rep(i, 240/12) S += "wbwbwwbwbwbw";
    vector<P> CumulativeSum(250);

    rep(i, 240){
        CumulativeSum[i+1].first = CumulativeSum[i].first;
        CumulativeSum[i+1].second = CumulativeSum[i].second;
        if(S[i] == 'w'){
            CumulativeSum[i+1].first += 1;
        }else{
            CumulativeSum[i+1].second += 1;
        }
    }

    for(int i=0; i<=240; i++){
        for(int j=i+1; j<=240; j++){
            int w = CumulativeSum[j].first - CumulativeSum[i].first;
            int b = CumulativeSum[j].second - CumulativeSum[i].second;
            if(w == W && b == B){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
} 
```

## [C - Σ](https://atcoder.jp/contests/abc346/tasks/abc346_c)

O(1)
A_1~A_Nに存在しない１〜Nまでの数を全探索（ループで計測）するとTLEになります。
1~Nまでの和は、

```
(1 + N) * N / 2
```
で求める事ができます。
1<=A_i<=Kの数の重複を除いた合計AAを計測し、
1~Nまでの和からAAを減算します。

```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, K;
    cin >> N >> K;
    set<ll> A;
    rep(i, N){
        int a;
        cin >> a;
        A.insert(a);
    }

    ll sum = 0;
    for(auto a:A){
        if(1 <= a && a <= K) sum += a;
    }
        
    cout << (1 + K) * K / 2 - sum << endl;

    return 0;
} 
```

## [D - Gomamayo Sequence](https://atcoder.jp/contests/abc346/tasks/abc346_d)

O(N)
文字列Sが010100101の時の考察します。
先頭が0から始まるパターンです。
0101...とT_iとT_(i+1)が一致するまで規則性を持ちます。
T_iとT_(i+1)が一致した後は、0101..と規則性を持ちます。

最初は、
i%2==0の時、'0'である。
i%2==1の時、'1'である。

T_iとT_(i+1)が一致したタイミングで
i%2==0の時、'1'である。
i%2==1の時、'0'である。
と条件が変わります。

先頭から累積和s0を、
上記の条件の文字の規則と異なる文字のとき、文字列SのS_iを変更し、コストC_iを加算して計測しましょう。
最後尾から累積和e0を、
上記の条件の文字の規則と異なる文字のとき、文字列SのS_iを変更し、コストC_iを加算して計測しましょう。

```
ans = min(ans,　s0[i] + e0[i]]）
```

が答えになります。
1010101の先頭が1からの時は上記の条件から導けると思います。

```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; }

ll dp[20010][2];

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<ll> C(N);
    rep(i, N) cin >> C[i];
    vector<ll> s0(N+1), s1(N+1), e0(N+1), e1(N+1);

    for(int i=0; i<S.size(); i++){
        s0[i+1] = s0[i];
        s1[i+1] = s1[i];
        if(i%2==0){
            if(S[i] - '0' == 0) s1[i+1] += C[i];
            else s0[i+1] += C[i];
        }else{
            if(S[i] - '0' == 0) s0[i+1] += C[i];
            else s1[i+1] += C[i];
        }
    }

    for(int i = S.size()-1; i>=0; i--){
        e0[i] = e0[i+1];
        e1[i] = e1[i+1];
        if(i%2==0){
            if(S[i] - '0' == 0) e0[i] += C[i];
            else e1[i] += C[i];
        }else{
            if(S[i] - '0' == 0) e1[i] += C[i];
            else e0[i] += C[i];
        }
    }

    ll ans = 2e18;
    for(int i=1; i<S.size(); i++){
        ans = min(ans, min(s0[i] + e0[i], s1[i] + e1[i]));
    }
    cout << ans << endl;

    return 0;
} 
```