AtCoder Beginner Contest 396

## [A - Triple Four](https://atcoder.jp/contests/abc396/tasks/abc396_a)

O(N)
forループの問題です。

```math
a_i = a_{i+1} = a_{i+2} 
```

が成立した時に`Yes`を出力します。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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-2){
        if(A[i] == A[i+1] && A[i+1] == A[i+2]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
} 
```

## [B - Card Pile](https://atcoder.jp/contests/abc396/tasks/abc396_b)

O(N)
全探索の問題です。
`タイプ1 : 整数xの書かれたカードを1枚カードの山の一番上に積み重ねる。`
とあるので、問題文通りに0のデータを100枚ほどデータ構造へ追加します。
データ構造は、`山の一番上`とあるのでstackを使用します。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 Q;
    cin >> Q;
    stack<int> st;
    rep(i, 100) st.push(0);
    rep(i, Q){
        int op;
        cin >> op;
        if(op == 1){
            int x;
            cin >> x;
            st.push(x);
        }
        if(op == 2){
            cout << st.top() << endl;
            st.pop();
        }
    }

    return 0;
} 
```

## [C - Buy Balls](https://atcoder.jp/contests/abc396/tasks/abc396_c)

O(N)
貪欲法の問題です。
`黒色のボールの個数が白色のボールの個数以上になるようにボールを0個以上選ぶとき、`
とあり、白色のボールの個数を先に探索する必要があります。

```math
B_i + W_i >= 0 
```
```math
W_i >= 0
```

この２つの条件を満たす時、白色のボールを選んで良いです。
黒色のボールの個数は、まず白色のボールの個数と同じ数だけ選びます。
さらに、

```math
B_i >= 0
```

の条件を満たす要素を探索します。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, M;
    cin >> N >> M;
    vector<ll> B(N), W(M);
    rep(i, N) cin >> B[i];
    rep(i, M) cin >> W[i];
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());
    sort(W.begin(), W.end());
    reverse(W.begin(), W.end());

    ll ans = 0;
    int K = min(N, M);
    int cnt = 0;
    rep(i, K){
        if(W[i] >= 0 && B[i] + W[i] >= 0){
            ans += W[i];
            cnt++;
        }
    }
    rep(i, N){
        if(i < cnt || B[i] >= 0){
            ans += B[i];
        }
    }
    cout << ans << endl;

    return 0;
} 
```

もっと綺麗にコーディングできないか考察しましょう。

```C++:C++
    ll ans = 0;
    ll sumb = 0;
    ll maxw = 0, sumw = 0;
    rep(i, N){
        // Bの要素の合計
        sumb += B[i];
        // Wの要素の合計
        if(i < M) sumw += W[i];
        maxw = max(maxw, sumw);
        // Bの合計とWの合計の最大値を加算した最大値を求める
        ans = max(ans, sumb+maxw);
    }
    cout << ans << endl;
```

すぬけさんのコードはいつみても綺麗ですね。
コンテスト中に自分のコードは誤っていると思いましたが、このコードに辿りつきませんでした。
下記が整理したコードです。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, M;
    cin >> N >> M;
    vector<ll> B(N), W(M);
    rep(i, N) cin >> B[i];
    rep(i, M) cin >> W[i];
    sort(B.rbegin(), B.rend());
    sort(W.rbegin(), W.rend());

    ll ans = 0;
    ll sumb = 0;
    ll maxw = 0, sumw = 0;
    rep(i, N){
        sumb += B[i];
        if(i < M) sumw += W[i];
        maxw = max(maxw, sumw);
        ans = max(ans, sumb+maxw);
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - Minimum XOR Path](https://atcoder.jp/contests/abc396/tasks/abc396_d)

O(N!)
グラフの問題です。
頂点Nに、M個の辺を探索する最大の計算量は、

```math
10! = 3628800
```

全探索で間に合います。
xorと書かれていて難しそうに見えますが要領は加算と同じです。
この時点で順列全探索とDFSの選択肢が見えます。
今回はDFSを選択しましょう。

・現在、通過した頂点を配列usedで管理する
・dfs関数の呼び出し前にxorでコストを計算、dfs関数の呼び出し後にxorでコストを計算

ここまで考察できたのでコーディングします。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, M;
    cin >> N >> M;
    vector<vector<pair<int, ll>>> graph(N);
    rep(i, M){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--; v--;

        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    ll ans = 2e18;
    vector<bool> used(N);
    auto dfs = [&](auto dfs, int u, ll num){
        if(u == N-1){
            ans = min(ans, num);
            return;
        }

        used[u] = true;

        for(auto [v, w]:graph[u]){
            if(used[v]) continue;
            num ^= w;
            dfs(dfs, v, num);
            num ^= w;
        }

        used[u] = false;
    };

    dfs(dfs, 0, 0);

    cout << ans << endl;

    return 0;
} 
```

グラフの全探索に関する問題として典型問題ですね。
似たような問題はいくつもあるので解いて練習しましょう。