AtCoder Beginner Contest 386

## [A - Full House 2](https://atcoder.jp/contests/abc386/tasks/abc386_a)

O(1)
数字の組み合わせは、

- 1種類 `1 1 1 1`   
- 2種類 `1 1 2 2` `1 2 2 2`   
- 3種類 `1 1 2 3`   
- 4種類 `1 2 3 4`

を考察できます。
1, 3, 4種類は条件を満たしません。
数字が2種類か探索しましょう。

```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 = 4;
    map<int, int> mp;
    rep(i, n){
        int a;
        cin >> a;
        mp[a]++;
    }

    if(mp.size() != 2){
        cout << "No" << endl;
        return 0;
    }

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

## [B - Calculator](https://atcoder.jp/contests/abc386/tasks/abc386_b)

O(N)
`00`が2箇所続いているのを探索しましょう。
下記条件式で判定できます。

```C++:C++
if(i<n-1 && s[i] == '0' && s[i+1] == '0')
```

trueならiをインクリメントしましょう。

```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() {
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    rep(i, n){
        if(i<n-1 && s[i] == '0' && s[i+1] == '0'){
            i++;
        }
        ans++;
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - Operate 1](https://atcoder.jp/contests/abc386/tasks/abc386_c)

O(2)
3つのパターンを考察します。

```
abs(s.size() - t.size()) >= 2
```

が成立する時、`No`になります。

```
abs(s.size() - t.size()) == 0
```

```
rep(i, s.size()){
    if(s[i] != t[i]) cnt++;
}
```

の時、長さが同じ`s`と`t`の文字が2つ以上異なるなら`No`になります。

```
abs(s.size() - t.size()) == 1
```

の時、1文字を除いて長い文字列は短い文字列の並びと同じでなくてはいけません。
ループ内で短い文字列のindexを管理する`i`、長い文字列のindexを管理する`cnt`と分けて宣言して処理を行います。

```C++:C++
        if(ns > nt) swap(s, t); 
        int n = min(ns, nt);
        int cnt = 0;
        rep(i, n){
            while(s[i] != t[cnt]){
                cnt++;
                if(cnt-i > 1){
                    cout << "No" << endl;
                    return 0;
                }
            }
            cnt++;
        }
```

`s`と`t`の文字が異なるならcntを加算していきます。
`cnt-i > 1`なら`No`になります。

```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 K;
    cin >> K;
    string s, t;
    cin >> s >> t;
    int ns = s.size();
    int nt = t.size();

    if(abs(ns - nt) >= 2){
        cout << "No" << endl;
        return 0;
    }

    if(ns == nt){
        int cnt = 0;
        rep(i, ns){
            if(s[i] != t[i]) cnt++;
        }
        if(cnt >= 2){
            cout << "No" << endl;
            return 0;
        }
    }
    if(abs(ns - nt) == 1){
        if(ns > nt) swap(s, t); 
        int n = min(ns, nt);
        int cnt = 0;
        rep(i, n){
            while(s[i] != t[cnt]){
                cnt++;
                if(cnt-i > 1){
                    cout << "No" << endl;
                    return 0;
                }
            }
            cnt++;
        }
    }
    cout << "Yes" << endl;
    
    return 0;
} 
```

## [D - Diagonal Separation](https://atcoder.jp/contests/abc386/tasks/abc386_d)

O(NlonN)
貪欲法です。
`x1 < x2`の条件でマスをソートします。
マスを順番にループして処理を行います。
白いマスの最小の`y`を保持します。
それより大きい黒い`y`を持つマスが存在しているなら`No`になります。

問題文を理解するのが難しい問題です。

```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<tuple<int, int, char>> xyc;
    rep(i, M){
        int x, y;
        char c;
        cin >> x >> y >> c;
        xyc.push_back(tuple<int, int, char>(x, y, c));
    }
    
    sort(xyc.begin(), xyc.end(), [](const tuple<int, int, char> x, const tuple<int, int, char> y){
        return get<0>(x) == get<0>(y)? get<1>(x) < get<1>(y) : get<0>(x) < get<0>(y);
    });

    int miny = 1 << 30;
    rep(i, M){
        if(get<2>(xyc[i]) == 'W'){
            miny = min(get<1>(xyc[i]), miny);
        }else{
            if(get<1>(xyc[i]) >= miny){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
} 
```