Educational Codeforces Round 101 (Rated for Div. 2) 풀이

A. Regular Bracket Sequence

문제: codeforces.com/contest/1469/problem/A

• 괄호의 상태를 정수로 나타낼 변수 state, (현재까지) ?의 개수를 나타내는 변수 unknown 생성
• '('이면 state++, ')'이면 state--, '?'이면 unknown++
• ')'일 때, state 또는 unknown이 음수라면 정상적인 괄호가 형성되지 않으므로 Say "NO"! -> 바로 break
• 예: ((????
  • -> state=2, unknown=4
  • ? 두 개를 앞에 (와 매칭 시킨다. -> unknown(?) 2개 남음
  • 남은 ?가 짝수라면 각각 () 쌍으로 만들어 줄 수 있으므로 Say "YES"!

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int tc, state, unknown;
string seq;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> tc;
    while (tc--) {
        state = unknown = 0;

        cin >> seq;
        
        int seqLen = seq.size();
        for (int i = 0; i < seqLen; i++) {
            if (seq[i] == '(') state++;
            else if (seq[i] == ')') {
                state--;
                if (state < 0) {
                    if (unknown > 0) {
                        unknown--;
                        state++;
                    }
                    else break;
                }
            }
            else unknown++;
        }
        int remain = unknown - state;
        if (seq[0] == ')' || seq[seqLen - 1] == '(') cout << "NO\n";
        else if (state >= 0 && remain >= 0 && remain % 2 == 0) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

연말에 답안 제출하니 "Happy New Year!"로 정답 표시해준다. 귀욤 ㅎㅎ

 

B. Red and Blue

문제: codeforces.com/contest/1469/problem/B

• Red, Blue 각각 앞에서부터 순차적으로 누적하여 합을 구한다. 
• 두 sequence에서 각각 가장 큰 누적 합을 뽑아낸 후, 더해주면 끝

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int tc, redN, blueN;
int maxRedSum, maxBlueSum;
int redSum, blueSum;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> tc;
    while (tc--) {
        //init
        maxRedSum = maxBlueSum = 0;
        redSum = blueSum = 0;

        cin >> redN;
        for (int i = 0; i < redN; i++) {
            int red;
            cin >> red;
            redSum += red;
            maxRedSum = max(maxRedSum, redSum);
        }

        cin >> blueN;
        for (int i = 0; i < blueN; i++) {
            int blue;
            cin >> blue;
            blueSum += blue;
            maxBlueSum = max(maxBlueSum, blueSum);
        }
        cout << maxRedSum + maxBlueSum << '\n';
    }

    return 0;
}

 

 

C. Building a Fence

문제: codeforces.com/contest/1469/problem/C

• 문제 조건:
  1. 인접한 펜스는 최소 높이 1만큼 맞닿아있어야 한다.
  2. 양끝의 펜스는 ground 바로 위에 펜스를 지어야 한다.
  3. 그 외의 펜스는 ground 바로 위부터 (k-1)이하로 띄워서 지울 수 있다.
• 문제 풀이:
  • 양끝에 먼저 펜스 설치
  • 다음부터는 ground가 높은 곳부터 펜스 설치
  • 최대한 낮게 펜스 설치(주변에 펜스가 있다면 조건 1에 맞게 설치)
    • 이때, 조건 3을 만족할 수 없다면 펜스 설치 불가 -> Say "NO"
  • 마지막에 양끝 펜스가 조건 1을 만족하는지 확인

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int, int> P;

int tc, n, k;
int ground[200001],height[200001];
vector<P> groundH; //<높이, 위치>

bool buildFence() {

    // 양끝 먼저 펜스 세우기
    height[0] = ground[0] + k;
    height[n - 1] = ground[n - 1] + k;

    // ground level이 높은 곳부터 펜스 설치해나감
    sort(groundH.begin(), groundH.end());
    for (int i = n - 1; i >= 0; i--) { 
        int pos = groundH[i].second;
        if (height[pos]!=0) continue; // 이미 펜스 세워진 경우 패스

        int minH = max(height[pos - 1], height[pos + 1]) - k + 1; // 양옆의 펜스와 겹치게 설치할 수 있는 가장 낮은 높이

        if (ground[pos] + 2 * k - 1 < minH) return false; // 최대한 높게 설치했는데 옆에 펜스와 안 겹치면 -> 설치 불가능
        
        height[pos] = max(minH, ground[pos] + k); // 조건을 만족하면서 가능한 낮게 설치
    }

    // 양옆 펜스가 안쪽 펜스와 겹치는지 확인
    if (abs(height[0] - height[1]) >= k) return false;
    if (abs(height[n - 1] - height[n - 2]) >= k) return false;

    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> tc;
    while (tc--) {
        cin >> n >> k;

        //init
        memset(height, 0, sizeof(height));
        groundH.clear();

        for (int i = 0; i < n; i++) {
            cin >> ground[i];
            groundH.push_back({ ground[i],i });
        }
        
        if (buildFence()) cout << "YES\n";
        else cout << "NO\n";

    }

    return 0;
}

 

 

D. Ceil Divisions

문제: codeforces.com/contest/1469/problem/D

• 예: n=200000 (가능한 최댓값)
  • 1,2,3,...,5,...,22,...,448,...,200000
  • 이런 식으로 n부터 제곱근에 ceil function 취한 것들의 위치를 squareRootLocation이라는 벡터에 넣어두자.
    • 큰 값부터 내림차순으로 벡터에 값 추가됨 
    • 예:
      • squareRootLocation[0] = 200000
      • squareRootLocation[1] = 448
  • 그리고 나머지 값들은 가장 큰 값으로 나눔으로써 모두 1로 만들어 준다.
    • 예: ceil(199999/200000) => 1
  • 그 후, 큰 값부터 제곱근으로 2번씩 나눠줌으로써 1을 만들어 준다.
    • 예: ceil(200000/448) = 447 -> ceil(447/448) = 1
  • 이렇게 하면, 기존의 2만 2로 남고, 나머지는 모두 1이 된다.
  • 최댓값인 200000에서 이와 같은 연산이 (n+5)번 이하로 수행하므로 가능한 모든 n에서 조건에 부합한 답을 출력할 수 있음을 보장할 수 있다.
    • 증명:
      • squareRootLocation 벡터의 사이즈를 x라고 하자. -> 위의 예의 경우 x=6
      • 맨 처음 제곱근들을 외의 값들을 1로 만들 때, 연산의 횟수-> n-x-1(원래 1은 건드리지 않으므로)
      • 그 후, 큰 제곱근들을 1로 만들 때, 연산의 횟수 -> (x-1)*2 (원래의 2는 그대로 2로 유지)
      • 즉, 총 연산 횟수는 n+x-3
      • n 값이 작을수록 x 값은 상대적으로 작을 수밖에 없다.

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>

using namespace std;

typedef pair<int, int> P;

int tc,n;
vector<int> squareRootLocation;
vector<P> answer;
void findOperationPair() {
    squareRootLocation.clear();
    squareRootLocation.push_back(n);
    answer.clear();

    // 1,2와 제곱근들을 제외하고 나머지 1로 만들기
    int squareRoot = ceil(pow(n, 0.5)), curP =n;

    for (int i = n - 1; i > 2; i-- ) {
        if (squareRoot == i) {
            squareRootLocation.push_back(i);
            squareRoot = ceil(pow(squareRoot, 0.5));
            curP = i;
        }
        else {
            answer.push_back({ i,curP });
        }
    }
    squareRootLocation.push_back(2);

    // 제곱근들 큰 수부터 1로 만들기 -> 예: 16/4 = 4 -> 4/4 =1
    int len = squareRootLocation.size();
    for (int i = 0; i<len-1; i++) {
        answer.push_back({ squareRootLocation[i],squareRootLocation[i + 1] });
        answer.push_back({ squareRootLocation[i],squareRootLocation[i + 1] });
    }
}

void printAnswer() {
    cout << answer.size() << '\n';

    for (P p : answer) {
        cout << p.first << " " << p.second << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> tc;

    while (tc--) {
        cin >> n;
        findOperationPair();
        printAnswer();
    }

    return 0;
}

 

 

E. A Bit Similar

문제: codeforces.com/contest/1469/problem/E

• 문제 설명:
  • n, k가 먼저 입력으로 들어오고
  • 2진수 string(길이: n)가 입력으로 들어온다.
  • 이 string을 길이 k개의 substring으로 나누고, 모든 substring과 한 비트 이상 겹치는(beautiful) 문자열(길이: k)을 찾는 문제이다.
    • beautiful = a bit similar가 있는 문자열  = 동일한 자리가 같은 문자인 것[$a_i$=$b_i$]  
    • 예: 10001 (k=3) -> 100 / 000 / 001
    • 위의 경우, 000이 정답이 된다.
  • 위 조건을 만족하는 문자열 중, 사전 순으로 가장 앞선 것을 찾아서 출력한다.
    • 없으면 Say "NO"
• 문제 풀이:
  • 모든 substring의 1의 보수들을 가능한 리스트에서 제거한 후, 남은 값 중 가장 작은 값을 출력한다.
    • 1의 보수: 비트를 반대로 바꾼 것
      • 예: 01110 -> 10001
  • substring을 구할 때, substr 함수를 사용하게 되면 매번 O(substr 길이)만큼의 시간이 들기 때문에, 오래 걸린다.
    • 위 문제를 해결하기 위해, 이진수 문자열을 정수로 변환하여 계산할 것이다.
    • 문자열의 맨 앞, k만큼을 먼저 정수로 변환한다 -> 첫 번째 substring (cur이라고 부르자)
    • 다음 substring을 구할 때는, 이 cur을 $2^{k-1}$로 나눈 나머지만 취해 앞 문자열을 버리고, 이 값에 2배 + 다음 문자열(0 or 1)을 더해준다.
    • k가 최대 $10^6$인데...?
      
      • substring의 개수는 (n-k+1 ≒ n)이다. 즉, 모든 문자열을 다 고려할 필요 없이 n개를 표현할 수 있는 문자열 길이만 보면 된다.
      • 즉, 이진수(길이: x)가 나타낼 수 있는 문자열의 개수 => $2^n$
      • $10^6$≤$2^x$ 이면 되므로 x는 대략 20정도이다.
      • 결과적으로, substring의 뒷부분 20자리만 보면 된다.
• 92번째 testcase에서 wrong answer가 나온다 ㅠㅠ 다음에 다시 풀어서 수정하겠습니다....

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>

using namespace std;

int tc,n,k;
string seq;
set<int> impossibleValGroup;
string forTest;

string decToBin(int res) {
    string answer = "";

    while (res > 0) {
        if (res % 2) answer += '1';
        else answer += '0';
        res /= 2;
    }
    while (answer.size() < k) answer += '0';

    reverse(answer.begin(), answer.end());
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> tc;

    while (tc--) {
        cin >> n >> k;
        cin >> seq;

        impossibleValGroup.clear();

        int len = min(k, 20);

        int cur = 0;
        for (int i = k-len; i < k; i++) {
            cur = cur * 2 + (seq[i] - '0');
        }

        int maxV = pow(2, len) - 1;
        int impossibleValue = maxV - cur; // cur에 1의 보수 취한 것 
        impossibleValGroup.insert(impossibleValue);

        int powV = pow(2, len - 1);
        for (int i = k; i < seq.size(); i++) {
            cur = (cur % powV) * 2 + (seq[i] - '0');
            impossibleValue = maxV - cur; // cur에 1의 보수 취한 것
            impossibleValGroup.insert(impossibleValue);
        }

        if (impossibleValGroup.size() == pow(2, k)) cout << "NO\n";
        else {
            for (int i = 0; i <= maxV; i++) {
                if (impossibleValGroup.find(i) == impossibleValGroup.end()) {
                    cout << "YES\n" << decToBin(i) << '\n';
                    break;
                }
            }
        }
    }

    return 0;
}