AtCoder Beginner Contest 386

A - Full House 2

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++

#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

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

C++

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

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

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

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++

        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++

#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

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

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

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