A번: Two Towers

빨간색(R)과 파란색(B) 블록으로 구성된 두 개의 탑이 주어진다. 한 번의 이동에서는 길이가 2 이상인 탑의 꼭대기 블록을 다른 탑으로 옮길 수 있다. 이동을 통해 두 탑 모두 빨강-파랑이 번갈아 나타나는 형태로 만들 수 있는지 판별하는 문제다.

핵심 관찰

탑의 구조를 분석하면 몇 가지 중요한 사실을 발견할 수 있다:

1. 각 탑 내부에서 인접한 동일 색상 블록 쌍의 개수를 conflict라고 정의하자. 예를 들어 "RRB"의 conflict는 1이다.
2. 두 탑 모두 conflict가 0이면 이미 조건을 만족한다.
3. 두 탑 모두 conflict가 1 이상이면 불가능하다. 어느 쪽을 움직여도 해결되지 않는다.
4. 한 탑만 conflict가 있을 때, 그 값이 1이어야 하고 두 탑의 꼭대기 색상이 달라야 가능하다.

구현

conflict 계산과 꼭대기 색상 비교로 충분하다.

#include <bits/stdc++.h>
using namespace std;

int calc(const string& str) {
    int cnt = 0;
    for (size_t i = 1; i < str.length(); ++i) {
        if (str[i] == str[i-1]) cnt++;
    }
    return cnt;
}

void solve() {
    int lenA, lenB;
    string towerA, towerB;
    cin >> lenA >> lenB;
    cin >> towerA >> towerB;
    
    int badA = calc(towerA);
    int badB = calc(towerB);
    
    if (badA > 0 && badB > 0) {
        cout << "NO\n";
    } else if (badA == 0 && badB == 0) {
        cout << "YES\n";
    } else {
        if (badA > 1 || badB > 1) {
            cout << "NO\n";
        } else if (towerA.back() == towerB.back()) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) solve();
    return 0;
}

B번: Ideal Point

n개의 구간과 정수 k가 주어진다. 일부 구간을 제거하여 k가 남은 구간들의 합집합에서 가장 많이 이는 점이 되도록 할 수 있는지 판별한다.

핵심 관찰

직관적으로 생각하면 k를 포함하는 구간만 남기면 될 것 같지만, 이는 충분조건이 아니다. k를 포함하는 구간들이 다른 어떤 점을 동시에 덮는다면, 그 점도 k만큼 많이 덮힐 수 있다.

따라서 다음 과정이 필요하다:

1. k를 포함하는 모든 구간에서 각 정수점의 덮힘 횟수를 센다
2. k의 덮힘 횟수가 이 범위 내 다른 모든 점의 덮힘 횟수보다 크면 "YES"

제약 조건이 작으므로(좌표 ≤ 50) 배열로 간단히 처리 가능하다.

구현

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, target;
    cin >> n >> target;
    
    vector<int> freq(55, 0);
    bool hasCover = false;
    
    for (int i = 0; i < n; i++) {
        int L, R;
        cin >> L >> R;
        if (L <= target && target <= R) {
            hasCover = true;
            for (int p = L; p <= R; p++) {
                freq[p]++;
            }
        }
    }
    
    if (!hasCover) {
        cout << "NO\n";
        return;
    }
    
    int kFreq = freq[target];
    for (int p = 1; p <= 50; p++) {
        if (p != target && freq[p] >= kFreq) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) solve();
    return 0;
}