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

コンテスト名

AtCoder Beginner Contest 381

コンテストURL

開催日

2024/11/22 21:00-22:40

---

A: 11/22 String

解法

• 問題文通りに判定する
• 前半がすべて 1 か、中央が / か、後半がすべて 2 かを判定する

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

解法

• 問題文通りに判定する
• 各文字の登場は set<char> で記録する

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

解法

• 各 / から前後にどれだけ連続して 1 と 2 が並んでいるかを探索する
• 計算量は $\mathcal{O}(N)$

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

解法

• しゃくとり法
• 偶奇それぞれの場合を調べる

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

解法

• 答えを二分探索する
• $L$ 以上に 1 が $X$ 個、 $X$ 個の 1 以降に / が $1$ 個、 $1$ 個の / 以降に 2 が $X$ 個、これらが $R$ 以下であることを判定する

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