【ABC386】AtCoder Beginner Contest 386【C++】

コンテスト名

AtCoder Beginner Contest 386

コンテストURL

開催日

2024/12/28 21:00-22:40

---

A: Full House 2

解法

• 条件を満たすすべての場合を調べて判定する

ABC386A.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> V(4);
    for(int i=0; i<4; i++){
        cin >> V[i];
    }

    sort(V.begin(), V.end());
    if(V[0]==V[1] && V[2]==V[3] && V[0]!=V[2]){
        cout << "Yes" << endl;
        return 0;
    }
    if(V[0]==V[1] && V[1]==V[2] && V[3]!=V[2]){
        cout << "Yes" << endl;
        return 0;
    }
    if(V[1]==V[2] && V[2]==V[3] && V[3]!=V[0]){
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;

    return 0;
}

B: Calculator

解法

• 0 が 2 つ連続している箇所の個数を数える
• 文字列 $S$ の長さから0 が 2 つ連続している箇所の個数を引いたものが求める答えである

ABC386B.cpp

#include <iostream>
#include <string>
using namespace std;

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

    int cnt = 0;
    for(int i=0; i<s.size()-1; i++){
        if(s[i]=='0' && s[i+1]=='0'){
            cnt++;
            i++;
        }
    }

    cout << s.size() - cnt << endl;

    return 0;
}

C: Operate 1

解法

• 文字列 $S$ の長さと文字列 $T$ の長さの差が 1 以下である場合のみ、条件を満たす可能性がある
• 挿入・削除・変更が 1 回未満で済むかを判定する

ABC386C.cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

    string s, t;
    cin >> s >> t;

    if(s==t){
        cout << "Yes" << endl;
        return 0;
    }

    int cnt = 0, j = 0;
    if(s.size()==t.size()){
        for(int i=0; i<s.size(); i++){
            if(s[i]!=t[i]){
                cnt++;
            }
        }

        if(cnt<=1){
            cout << "Yes" << endl;
            return 0;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }else if(s.size()==t.size()+1){
        cnt = 0;
        j = 0;
        for(int i=0; i<t.size(); i++){
            if(s[j]!=t[i]){
                cnt++;
                i--;
            }
            j++;
            if(cnt>1){
                cout << "No" << endl;
                return 0;
            }
        }

        if(cnt<=1){
            cout << "Yes" << endl;
            return 0;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }else if(s.size()+1==t.size()){
        swap(s, t);
        cnt = 0;
        j = 0;
        for(int i=0; i<t.size(); i++){
            if(s[j]!=t[i]){
                cnt++;
                i--;
            }
            j++;
            if(cnt>1){
                cout << "No" << endl;
                return 0;
            }
        }
        
        if(cnt<=1){
            cout << "Yes" << endl;
            return 0;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

D: Diagonal Separation

解法

• 黒のマスを先に塗ってから、白のマスの条件を満たせるかを判定する
• $C_i$ の色ごとにそれぞれ、vector<pair<int, int>> に $X_i, Y_i$ を記録する
• $C_i$ が B の vector<pair<int, int>> を $X_i$ の昇順にソートして、条件を満たすように最低限必要な黒のマスを塗る
• $C_i$ が W の $X_i, Y_i$ について、先に塗った黒のマスと矛盾しないかを判定する

ABC386D.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<pair<int, int>> B, W;
    int x, y;
    char c;
    for(int i=0; i<m; i++){
        cin >> x >> y >> c;
        x--;
        y--;
        if(c=='B'){
            B.emplace_back(x, -y);
        }else{
            W.emplace_back(x, y);
        }
    }
    
    sort(B.begin(), B.end());
    if(B.size()){
        for(int i=B.size()-1; i>0; i--){
            auto [x1, y1] = B[i-1];
            auto [x2, y2] = B[i];
            y1 *= -1;
            y2 *= -1;
            if(y1<y2){
                B[i-1] = make_pair(x1, -y2);
            }
        }
    }
    
    if(B.size()==0 || W.size()==0){
        cout << "Yes" << endl;
        return 0;
    }
    
    auto [maxx, maxy] = B.back();
    for(int i=0; i<W.size(); i++){
        auto [x1, y1] = W[i];
        if(x1>maxx){
            continue;
        }
        int idx = lower_bound(B.begin(), B.end(), make_pair(x1, -n)) - B.begin();
        auto [x2, y2] = B[idx];
        y2 *= -1;
        if(y2>=y1){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;

    return 0;
}