【ABC381】AtCoder Beginner Contest 381【C++】

### コンテスト名
AtCoder Beginner Contest 381

### コンテストURL
https://atcoder.jp/contests/abc381

### 開催日
2024/11/22 21:00-22:40

---

## [A: 11/22 String](https://atcoder.jp/contests/abc381/tasks/abc381_a)
**解法**
- 問題文通りに判定する
- 前半がすべて `1` か、中央が `/` か、後半がすべて `2` かを判定する
```cpp:ABC381A.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;

    if(n%2==0){
        cout << "No" << endl;
        return 0;
    }
    if(s[(int)((n+1)/2)-1]!='/'){
        cout << "No" << endl;
        return 0;
    }
    for(int i=0; i<(int)((n+1)/2)-1; i++){
        if(s[i]!='1'){
            cout << "No" << endl;
            return 0;
        }
    }
    for(int i=(int)((n+1)/2); i<n; i++){
        if(s[i]!='2'){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}
```

## [B: 1122 String](https://atcoder.jp/contests/abc381/tasks/abc381_b)
**解法**
- 問題文通りに判定する
- 各文字の登場は `set<char>` で記録する
```cpp:ABC381B.cpp
#include <iostream>
#include <string>
#include <set>
using namespace std;

int main(){
    string s;
    cin >> s;

    int n = s.size();
    if(n%2==1){
        cout << "No" << endl;
        return 0;
    }

    set<char> S;
    for(int i=0; i<(int)(n/2); i++){
        if(s[i*2]!=s[i*2+1]){
            cout << "No" << endl;
            return 0;
        }
        if(S.count(s[i*2])){
            cout << "No" << endl;
            return 0;
        }
        S.insert(s[i*2]);
    }

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

## [C: 11/22 Substring](https://atcoder.jp/contests/abc381/tasks/abc381_c)
**解法**
- 各 `/` から前後にどれだけ連続して `1` と `2` が並んでいるかを探索する
- 計算量は $\mathcal{O}(N)$
```cpp:ABC381C.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string s;

int calc(int idx){
    int cnt = 0;
    int x = idx-1, y = idx+1;
    while(x>=0 && y<n && s[x]=='1' && s[y]=='2'){
        cnt++;
        x--;
        y++;
    }

    return cnt*2 + 1;
}

int main(){
    cin >> n;
    cin >> s;

    int maxv = 0;
    for(int i=0; i<n; i++){
        if(s[i]=='/'){
            maxv = max(maxv, calc(i));
        }
    }

    cout << maxv << endl;

    return 0;
}
```

## [D: 1122 Substring](https://atcoder.jp/contests/abc381/tasks/abc381_d)
**解法**
- しゃくとり法
- 偶奇それぞれの場合を調べる
```cpp:ABC381D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    int maxv = 0;
    vector<int> V(n+1);
    int right = 0;
    for(int left=right; left<n; left+=2){
        while(right<n){
            if(A[right]!=A[right+1]){
                break;
            }
            if(V[A[right]]){
                break;
            }
            V[A[right]]++;
            right += 2;
        }

        maxv = max(maxv, right-left);
        if(left==right){
            right += 2;
        }else{
            V[A[left]]--;
        }
    }
    V.assign(n+1, 0);
    right = 1;
    for(int left=right; left<n; left+=2){
        while(right<n){
            if(A[right]!=A[right+1]){
                break;
            }
            if(V[A[right]]){
                break;
            }
            V[A[right]]++;
            right += 2;
        }

        maxv = max(maxv, right-left);
        if(left==right){
            right += 2;
        }else{
            V[A[left]]--;
        }
    }

    cout << maxv << endl;

    return 0;
}
```

## [E: 11/22 Subsequence](https://atcoder.jp/contests/abc381/tasks/abc381_e)
**解法**
- 答えを二分探索する
- $L$ 以上に `1` が $X$ 個、 $X$ 個の `1` 以降に `/` が $1$ 個、 $1$ 個の `/` 以降に `2` が $X$ 個、これらが $R$ 以下であることを判定する
```cpp:ABC381E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    vector<int> V1, V2, V3;
    for(int i=0; i<n; i++){
        if(s[i]=='1'){
            V1.push_back(i);
        }else if(s[i]=='2'){
            V2.push_back(i);
        }else{
            V3.push_back(i);
        }
    }

    bool flag = false;
    if(V3.size()==0){
        flag = true;
    }

    int l, r;
    const int INF = 1e9;
    for(int i=0; i<q; i++){
        cin >> l >> r;
        l--;
        
        if(flag){
            cout << 0 << '\n';
            continue;
        }

        int low = -1, high = n/2 + 1;
        while(high-low>1){
            int mid = low + (high-low)/2;
            int idx_1, idx_2, idx_3;

            if(mid==0){
                idx_1 = l;
            }else{
                idx_1 = lower_bound(V1.begin(), V1.end(), l) - V1.begin();
                idx_1 += mid - 1;
                if(idx_1<V1.size()){
                    idx_1 = V1[idx_1]+1;
                }else{
                    idx_1 = INF;
                }
            }
            
            if(V3.back()>=l && V3[0]<=r){
                idx_3 = lower_bound(V3.begin(), V3.end(), idx_1) - V3.begin();
                if(idx_3<V3.size()){
                    idx_3 = V3[idx_3]+1;
                }else{
                    idx_3 = INF;
                }
            }else{
                idx_3 = INF;
            }

            if(mid==0){
                idx_2 = idx_3;
            }else{
                idx_2 = lower_bound(V2.begin(), V2.end(), idx_3) - V2.begin();
                idx_2 += mid - 1;
                if(idx_2<V2.size()){
                    idx_2 = V2[idx_2]+1;
                }else{
                    idx_2 = INF;
                }
            }

            if(idx_2<=r){
                low = mid;
            }else{
                high = mid;
            }
        }

        if(low==-1){
            cout << 0 << '\n';
        }else{
            cout << low*2 + 1 << '\n';
        }
    }

    return 0;
}
```