AtCoder Beginner Contest 212

##[A - Alloy](https://atcoder.jp/contests/abc212/tasks/abc212_a)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 A, B;
    cin >> A >> B;
 
    if(A>0 && B==0) cout << "Gold" << endl;
    else if(A==0 && B>0) cout << "Silver" << endl;
    else cout << "Alloy" << endl;
 
    return 0;
}
```

##[B - Weak Password](https://atcoder.jp/contests/abc212/tasks/abc212_b)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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;
 
    if(s[0] == s[1] && s[1] == s[2] && s[2] == s[3]){
        cout << "Weak" << endl;
        return 0;
    }
 
    int sum=0;
    rep(i, s.length()-1){
        int x = (s[i] - '0') + 1;
        int y = s[i+1] - '0';
        if(x % 10 == y) sum++;
    }
 
    if(sum==3){
        cout << "Weak" << endl;
        return 0;
    }
 
    cout << "Strong" << endl;
 
    return 0;
}
```

##[C - Min Difference](https://atcoder.jp/contests/abc212/tasks/abc212_c)

O(N)
全探索では解けないです。
配列Cに、AとBの要素とAかBを判別できる要素のpairを追加していきます。
C(i) と C(i+1)の比較しAとBの異なる要素だった際にminを取ります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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, M;
    cin >> N >> M;
 
    vector<P> v(N+M);
    rep(i, N){
        int a;
        cin >> a;
        v[i].first = a;
        v[i].second = 0;
    }
    rep(i, M){
        int b;
        cin >> b;
        v[i+N].first = b;
        v[i+N].second = 1;
    }
 
    sort(v.begin(), v.end(), [](const auto &x, const auto &y ){
        return get<0>( x ) == get<0>( y ) ? get<1>( x ) < get<1>( y ) : get<0>( x ) < get<0>( y );
    });
 
    int res=1000000007;
    rep(i, v.size()-1){
        if(v[i].second != v[i+1].second){
            int s = abs(v[i].first - v[i+1].first);
            res = min(res, s);
        }
    }
    cout << res << endl;
 
    return 0;
}
```

##[D - Querying Multiset](https://atcoder.jp/contests/abc212/tasks/abc212_d)

O(N)
累積和の応用です。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 Q;
    cin >> Q;
 
    multiset<ll> ms;
    ll sum=0;
    rep(i, Q){
        int q;
        cin >> q;
 
        if(q==1){
            int x;
            cin >> x;
            ms.insert(x-sum);
        }else if(q==2){
            int x;
            cin >> x;
            sum += x;
        }else{
            multiset<ll>::iterator itr = ms.begin();
            cout << *itr+sum << endl;
            ms.erase(itr);
        }
    }
 
    return 0;
}
```