[Codeforces Round #714] A, B, C번 풀이

Dashboard - Divide by Zero 2021 and Codeforces Round #714 (Div. 2) - Codeforces

A~C번 풀이

A. Array and Peaks

$2k \geq n$ 이면 -1을 출력한다.

아니라면, 1부터 n까지 오름차순으로 저장된 배열에서 $k$번 swap 해준다.

ex) 1 2 3 4 5 에서 $k=2$ 이면 1 (3 2) (5 4)

---

B. AND Sequences

이 문제의 포인트는 $n$개의 숫자들이 양 끝에 올 수 있는 숫자인지를 판단하는 것이다. (cango[] 배열)

$n$개 중 오른쪽 끝이 0인 비트가 하나라도 있을 때, 1인 비트의 숫자들은 양 끝으로 올 수 없다.

그렇게 2로 나눠가면서 모든 숫자가 0이 될 때까지 탐색한 다음,

양 끝으로 올 수 있는 숫자들의 개수를 센다. ($m$개)

만약 $m = 0, 1$일 경우 답은 0이다.

$m \geq 2$ 이면 $m(m-1)\times(n-2)!$ 를 $10^9+7$로 나눈 나머지가 답이 된다.

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

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

    int tc; cin >> tc;
    for (int k = 0; k < tc; k++) {
        int n; cin >> n;
        int arr[n]; bool cango[n];
        for (int i = 0; i < n; i++) {cin >> arr[i]; cango[i]=true;}

        while (true) {
            int one = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i]%2 == 1) one++;
            }
            if (one != n) {
                for (int i = 0; i < n; i++) {
                    if(arr[i]%2 == 1) {
                        cango[i]=false;
                    }
                }
            }
            for (int i = 0; i < n; i++) arr[i]=arr[i]/2;
            int z = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] == 0) z++;
            }
            if (z == n) break;
        }
        long long m = 0;
        for (int i = 0; i < n; i++) {
            if (cango[i] == true) m++;
        }
        long long ans = 1;
        ans = (m*(m-1))%1000000007;
        for (long long i = 1; i <= n-2; i++) {
            ans = (ans * i)%1000000007;
        }
        if (m < 2) cout << "0" << '\n';
        else cout << ans << '\n';
    }
}

---

C. Add One

처음에 단순 DP로 풀다가 3번째 TC에서 시간초과가 났다.

시간복잡도는 $O(10\times TC\times M)$ 가 되고, $TC, M$ 은 최대 $2\times10^5$ 이므로 시간초과가 나올 수 밖에 없다.

종료 직전에 시간복잡도를 줄이는 아이디어가 생각나서 풀려고 했으나, 구현이 끝나기 직전에 종료되어서 제출을 못했다.

아래는 종료 후 마저 구현해 AC를 받은 코드이다.

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

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

    int** num = new int* [200012];
    for (int i = 0; i < 200012; i++) num[i] = new int[10];
    num[0][0]=1;
    for (int i = 1; i <= 9; i++) num[0][i]=0;
    for (int i = 1; i < 200012; i++) {
        num[i][0]=num[i-1][9];
        num[i][1]=(num[i-1][0]+num[i-1][9])%1000000007;
        for (int q = 2; q <= 9; q++) num[i][q]=num[i-1][q-1];
    }

    int tc; cin >> tc;
    for (int i = 0; i < tc; i++) {
        int n, m;
        cin >> n >> m;
        int numcount[10];
        for (int i = 0; i < 10; i++)numcount[i]=0;
        while (n != 0) {
            numcount[n%10]++;
            n/=10;
        }
        long long ans = 0;
        for (int i = 0; i < 10; i++) {
            int tmpcnt = m+i;
            if (tmpcnt >= 0) {
                for (int j = 0; j < 10; j++) {
                    long long a = num[tmpcnt][j]; long long b = numcount[i];
                    ans = (ans + a*b)%1000000007;
                }
            }
        }
        cout << ans << '\n';
    }
}

tc를 입력받기 전 num 배열을 만든다. $num[m][k]$ 의 뜻은 $n = 0$이고, $m$번 연산했을 때 $k$의 개수이다.

입력받은 $m$은 $2\times10^5$ 이하 이므로, $+12$를 해서 저장하였다.

그 후 $tc$들에서 0~9의 개수를 저장하고, $num$배열의 값을 참고해 답을 구한다.

이 때의 시간복잡도는 $O(10\times M_{max}+TC\times 100)$ 이므로 충분히 통과가 된다.

<추가>

C번과 비슷한 문제를 백준에서 봤었다. www.acmicpc.net/problem/12850

이 문제 태그에 '분할정복을 활용한 거듭제곱' 이라고 되어있는데, 이 C번 문제도 비슷한 방법을 이용해 구할 수 있을 것이라고 생각한다.