Codeforces Round #737 (Div. 2) 후기 및 풀이

https://codeforces.com/contest/1557

Dashboard - Codeforces Round #737 (Div. 2) - Codeforces

처음으로 써보는 코드포스 후기입니다.

사진을 보시면 아시겟지만 일단 망쳤어요.

쓸데없는 변명을 하자면 암흑기가 온 것 같습니다...

 

어쨌든, 대회 때 푼 거랑 업솔빙해서 푼 거 합쳐서 3솔을 햇구요, 푼 문제의 풀이를 올려보려 합니다.

 

---

A. Ezzat and Two Subsequences

사용한 알고리즘: 정렬, 누적합

 

풀이

입력받은 배열을 정렬하고 각 \(i\)번째와 \(i - 1\)번째 사이를 갈라 두 구간으로 나눠본 다음 두 구간합의 평균의 합중 최대값을 구하면 됩니다. \((1 < i \leq N)\)

왜 굳이굳이 따로 누적합 배열을 만들었는지 모르겠네요ㅋㅋ

 

시간복잡도: \(O(N \log N)\)

 

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

    cout << fixed << setprecision(9);
    cerr << fixed << setprecision(9);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<double> arr(N), a(N), b(N);
        for (auto &i : arr) cin >> i;
        double ans = -1.0e18;

        sort(all(arr));
        
        a[0] = arr[0], b[N - 1] = arr[N - 1];
        for (int i = 1; i < N; ++i)
            a[i] = a[i - 1] + arr[i];
        for (int i = N - 2; i >= 0; --i)
            b[i] = b[i + 1] + arr[i];

        for (int i = 1; i < N; ++i) {
            double aa = a[i - 1] / i, bb = b[i] / (N - i);
            ans = max(ans, aa + bb);
        }

        cout << ans << '\n';
    }

    return 0;
}

 

---

B. Moamen and k-subarrays

사용한 알고리즘: 정렬, 그리디, 좌표 압축, 이분탐색

 

풀이

배열을 완벽하게 정렬해야 되기 때문에 \(a_i > a_{i + 1}\)인 부분이 존재해선 안됩니다. 그러므로, \(a_i > a_{i + 1}\)인 부분이 나올 때마다 카운팅하는 식으로 문제를 해결해 나갈 수 있습니다.

하지만, 저 부분만 찾는다고 문제가 해결되진 않습니다. \(a_i < a_{i + 1}\)인 부분도 두 수 사이의 수가 배열 내에 존재할 수 있기 때문에 그 수가 있는지도 판별할 수 있어야 합니다.

먼저, 배열 내에 존재하는 수를 중복 없이 정렬해 놓은 상태의 배열을 하나 만듭니다. 이 배열은 좌표 압축을 할 때의 \(sort\)와 \(unique\)로 만들 수 있습니다. 그다음, 이분탐색으로 \(a_i\)의 위치와 \(a_{i + 1}\)의 위치를 구합니다. 만약, \(a_i\)의 위치가 (\(a_{i + 1}\)의 위치 - 1)이라면 두 수 사이의 수는 존재하지 않으므로, 한 배열 안에 넣을 수 있습니다. 그렇지 않다면, 두 수 사이를 갈라야 하므로, 카운팅을 해줍니다.

이 작업을 진행하면서 카운팅 해준 것은 갈라야 할 부분의 개수이므로, \(1\)을 더한 값이 \(K\) 이하라면 "YES", 아니라면 "NO"를 출력해주면 됩니다.

 

시간복잡도: \(O(N \log N)\)

 

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

    int T; cin >> T;
    while (T--) {
        int N, K; cin >> N >> K;
        vector<int> arr(N), v;
        for (auto &i : arr) cin >> i;

        v = arr;
        sort(all(v)), v.erase(unique(all(v)), v.end());

        int cnt = 1;
        for (int i = 0; i < N - 1; ++i) {
            int pos = lower_bound(all(v), arr[i]) - v.begin();
            if (arr[i] == arr[i + 1]) continue;
            if (arr[i] > arr[i + 1] || v[pos + 1] != arr[i + 1]) cnt++;
        }

        if (cnt <= K) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

 

---

C. Moamen and XOR

사용한 알고리즘: 비트마스킹, 조합론, DP

 

풀이

여러가지 규칙을 찾아야 하는 꽤 까다로운 조합론 문제였습니다.

각 자리의 최종 비트가 \(\&\)인 경우는 그 자리의 모든 비트가 \(1\)일 때이고, 최종 비트가 \(\oplus\)인 경우는 그 자리의 비트 중 \(1\)인 비트의 개수가 홀수개일 때입니다. 그러므로, 문제의 조건을 만족하는 경우는 모든 비트가 \(1\) 또는 \(0\)이거나, \(1\)인 비트의 개수가 짝수개일 때입니다.

\(N\)개의 비트 중 \(1\)인 비트의 개수가 짝수개가 되도록(\(0\) 포함) 비트를 구성하는 경우의 수를 조합론 공식을 사용해 구해보면 \(2^{N-1}\)개임을 알 수 있습니다.

하지만, 위 경우만 따진다고 문제가 해결되진 않습니다. 전 비트까지가 어떻게 구성되었고, 어느 쪽이 더 큰가 등 여러 가지를 보면서 경우의 수를 구할 필요가 있습니다.

따라서, \(dp\)를 이용해 각 자리마다 비트를 구성하는 경우의 수를 누적해나가는 방식으로 문제를 풀 수 있습니다.

\(dp\)배열은 다음과 같이 정의합니다:

 

• \(dp_i:\) \(i\)번째 자리까지 고려했을 때, 조건을 만족하도록 \(i\)번째 비트까지 구성하는 경우의 수.

또한, \(dp_i\)를 \(dp_{i,0}\)과 \(dp_{i,1}\), 이렇게 \(2\)가지 경우로 나누어 처리해보겠습니다:

 

1. \(\&\)연산을 쓴 쪽이 \(\oplus\)연산을 쓴 쪽보다 크거나 같을 때의 경우의 수.
2. \(\&\)연산을 쓴 쪽이 \(\oplus\)연산을 쓴 쪽보다 작을 때의 경우의 수.

\(1\)번 경우부터 생각해보겠습니다.

제일 첫자리의 비트는 아까 구한 \(2^{N-1}\)값을 넣으면 됩니다.

두 번째 비트부터는, 전 비트까지 고려했을 때 \(\&\)연산을 쓴 쪽이 \(\oplus\)연산을 쓴 쪽보다 크거나 같을 경우에 똑같은 조건으로 현 자리의 비트를 구성하는 경우를 구합니다. 그러면, 위의 \(1,2\)번 경우 중 똑같이 \(1\)번 경우에 해당하므로 조건을 만족합니다.

 

\(2\)번 경우는 조금 복잡합니다.

제일 첫자리 비트는 \(N\)개의 비트 중 \(1\)인 비트가 홀수개가 되도록 구성하는 경우의 수인데 구해보면 \(1\)번 경우와 똑같이 \(2^{N-1}\)이 되므로, \(1\)번 경우와 똑같은 값을 넣으면 됩니다.

두 번째 비트부터의 경우, 잘 생각해보면 위의 \(1\)번 경우든 \(2\)번 경우든 현 자리의 비트를 구성했을 경우 무조건 \(2\)번 경우가 되므로, 두 경우 다 고려하면 됩니다.

또, 몇 가지 경우가 더 있는데, \(1\)번 경우는 크거나 같을 때이고, \(2\)번 경우는 그냥 작을 때입니다. 즉 \(2\)번 경우에 같은 경우는 없습니다. 그러므로, 전 자리의 \(2\)번 경우에서 이번 자리의 비트를 두 연산을 한 값이 같게 비트를 구성하는 경우를 고려해도 여전히 \(2\)번 경우가 됩니다. 따라서 전 자리가 \(2\)번 경우일 때, 두 연산을 한 값이 같도록 비트를 구성하는 경우를 추가시켜줍니다.

 

잘 생각해보면, \(\&\)연산을 쓴 쪽이 \(\oplus\)연산을 쓴 쪽보다 크도록 하려면 모든 비트가 \(1\)이면서 그 개수가 짝수개여야 합니다. 즉, \(N\)이 짝수개일 때의 한 경우를 빼면 \(1\)번 경우의 나머지들은 모두 두 수가 같을 때의 경우입니다. 두 수가 같게 구성하는 경우의 수는 이렇게 구해주면 됩니다.

 

이정도면 된듯 하지만 고려해야될게 또 있습니다! ㄴㅇㄱ

\(N\)이 홀수냐 짝수냐에 따라 경우의 수가 조금씩 다릅니다.

아까 \(1\)번 경우가 되도록 처음 자리에 비트를 구성하는 경우의 수와 \(2\)번 경우의 경우의 수가 \(2^{N-1}\)이라고 했습니다. 그런데, 여기서 \(N\)이 홀수일 경우, \(2\)번 경우에 비트 전체를 \(1\)로 구성하는 경우가 생기게 되는데, 이러면 두 수가 \(1, 1\)로 같아지므로, \(1\)을 빼준 값을 저장해야 합니다. 반면, \(1\)번 경우는 전체를 \(1\)로 구성하는 경우가 조건은 만족하지만 짝수개를 고르는 경우가 아니므로 제외됩니다. 따라서 \(1\)번 경우에는 \(1\)을 더해줘야 합니다. \(2\)번째 비트부터 사용되는 경우의 수들은 방금 정한 처음 경우의 수 그대로 사용해야 합니다.

 

점화식은 다음과 같이 세울 수 있습니다:

$$dp_{i, 0} = \begin{cases}
2^{N-1}dp_{i - 1, 0} + dp_{i - 1, 1}, & \text{ if }\ N \mod 2 = 0 \\ 
(2^{N-1}+1)dp_{i - 1, 0}, & \text{ otherwise }
\end{cases}$$

$$dp_{i, 1} = \begin{cases}
2^{N-1}(dp_{i-1,0}+dp_{i-1,1})+(2^{N-1}-1)dp_{i-1,1}, & \text{ if }\ N \mod 2=0\\ 
(2^{N-1}-1)(dp_{i-1,0}+dp_{i-1,1})+2^{N-1}dp_{i-1,1}, & \text{ otherwise }
\end{cases}$$

 

구하고자 하는 것은 \(1\)번 경우이므로, \(dp_{K,0}\)을 출력해주면 됩니다.

 

시간복잡도: \(O(N + K)\)

 

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

    const int MOD = (int)1e9 + 7;
    int T; cin >> T;
    while (T--) {
        int N, K; cin >> N >> K;
        if (!K) { cout << "1\n"; continue; }
        ll odd_cnt = 1, even_cnt;
        for (int i = 0; i < N - 1; ++i)
            odd_cnt = (odd_cnt * 2) % MOD;
        even_cnt = odd_cnt;
        if (N % 2) odd_cnt--, even_cnt++;

        odd_cnt %= MOD, even_cnt %= MOD;

        vector<vector<ll>> dp(K, vector<ll>(2));
        dp[0][0] = even_cnt, dp[0][1] = odd_cnt;
        for (int i = 1; i < K; ++i) {
            dp[i][0] = (dp[i - 1][0] * even_cnt) % MOD;
            dp[i][1] = ((((dp[i - 1][0] + dp[i - 1][1]) % MOD * odd_cnt) % MOD) + (dp[i - 1][1] * (even_cnt - 1)) % MOD) % MOD;
            if (N % 2 == 0) dp[i][0] = (dp[i][0] + dp[i - 1][1]) % MOD;
            else dp[i][1] += dp[i - 1][1];
        }

        cout << dp[K - 1][0] << '\n';
    }

    return 0;
}

 

---

마무리

처음 써보는 코드포스 후기지만 이렇게 길어질 줄은 몰랐네요;;

물론, \(3\)문제라서 길이도 \(3\)배쯤 늘어난다고 생각하면 그렇게 긴 건 아니군요;;