[Educational Codeforces #107] A~D번 풀이

결과

내가 실제로 참여한 8번째 CF 대회이다$.$ Div2 대회에서는 4솔 이상을 한 적도 없고 그 정도 실력이 안된다고 생각했었는데, 이번 Round에서 4솔을 했다..!

이전 7개 대회의 성적

 

이번 대회의 성적이 좋았던 이유는 물론 D번을 푼 것도 있겠지만, B, C번을 (특히 B번을) 빠르게 풀었다.
만약 B, C번에서 10분정도 더 썼더라면 D번을 풀 수 없었을 것이다.

Dashboard - Educational Codeforces Round 107 (Rated for Div. 2) - Codeforces

A. Review Site

처음에 지문을 제대로 읽지 않아 서버가 2개라는 사실을 모르고 문제를 풀어 틀렸다.

서버가 2개이므로 숫자가 1, 3일 때 무조건 +1을 하면 된다.

---

B. GCD Length

세 정수를 입력받는데, 각각 $a = x$의 길이, $b = y$의 길이, $c = gcd(x, y)$의 길이이다.

먼저, $x = 10^{a-1}$, $y = 10^{b-1}$로 맞춰놓으면, $gcd(10^{a-1}, 10^{b-1}) = 10^{min(a-1, b-1)}$ 가 성립한다.

여기서 $c \leq min(a, b)$ 이므로, $y$ 에 $10^{c-1}$ 를 더하면, 즉
$x = 10^{a-1}$, $y = 10^{b-1}+10^{c-1}$ 로 맞추면 $gcd(x, y) = 10^{c-1}$ 이므로 항상 성립한다.

---

C. Yet Another Card Deck

array의 크기는 $n = 3\times10^5$, query의 개수는 $q = 3\times10^5$ 이므로 naive하게 구현하면 $O(nq)$가 되어 시간 초과가 발생한다.

색깔의 개수가 $50$ 이하라는 점을 이용해 각 색깔에서 가장 앞에 있는 카드의 위치만 저장해도 된다는 점을 깨달았다.

그리고 각 쿼리가 진행될 때 $50$개의 위치를 바꾼다. 쿼리에 해당하는 색깔의 위치를 1로 바꾸고, 앞으로 이동하기 전 카드의 위치보다 앞에 있는 위치들을 모두 1 더해준다.

이 때 시간복잡도는 $O(50q)$이므로 충분히 통과된다.

---

D. Min Cost String

$cost$의 정의는 길이가 $n$인 문자열에서 길이가 2인 연속된 부분 문자열 2개를 잡았을 때 같은 것들의 개수이다. 입력은 문자열 길이 $n$, 사용할 수 있는 알파벳 개수 $k$이다.

$n$일 때 길이가 2인 연속된 부분 문자열의 개수는 $n-1$개이다. $k$개의 알파벳을 사용할 때 만들 수 있는 길이가 2인 문자열의 개수는 $k^2$개이다.

즉, $n-1 \leq k^2$이라면 $cost = 0$ 이 되는 문자열을 만들 수 있다.

소스코드 보기

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

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

    int n, k;
    cin >> n >> k;
    int have[k][k];
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) have[i][j]=0;
    }
    string a; a.push_back('a');
    int cycle = k*k;

    while (a.length() != n) {
        int first = a.back()-'a';
        int tag = 0;
        for (int j = 0; j < k; j++) {
            if (have[first][j] == (a.length()-1)/cycle) {
                a.push_back(j+'a');
                have[first][j]++;
                tag = 1;
                break;
            }
        }
        if (tag == 0) {
            a.pop_back();
            int r = a.back()-'a';
            have[r][first]--;
            a.push_back(first+'a'+1);
            have[r][first+1]++;
        }
    }
    cout << a;
}

 

코드 설명
$have[m][n]$: 첫 번째 문자가 $'a'+m$이고, 두 번째 문자가 $'a'+n$인 문자열의 개수를 저장하는 배열이다.
만약 $have[m][n]$가 $p \geq 2$이면 $cost$에 $ {}_{p}{C}_2 $가 더해진다.
즉, 모든 $have[m][n]$가 골고루 분포되는 것이 $cost$를 최소화시키는 방법이다.
예를 들어, $n = ak^2+1$일 때, 모든 $have[m][n]$를 $a$로 만들어야 $cost$가 최소이다.
이런 문자열이 만들어지게끔 백트래킹(?) 비슷한 방식으로 탐색하면 된다.

이 때 시간복잡도는 $O(nk^2)$이다.