Codeforces Round #737 (Div. 2) A부터 C까지 업솔빙

Codeforces Round #737 (Div. 2) A부터 C까지 업솔빙

사실 코드포스에서 A번 문제가 5분 넘을때 까지 안풀리면 그 대회는 참가하지 않는 것이 RATING에 이로울 정도로 A번 문제를 쉽게 풀 수 있는지 없는지가 중요하다. 이번 대회는 A번 문제를 생각보다 빠르게 풀어서 기분이 좋았다. 하지만 바로 B번부터 막혀서 기분이 안좋았지만 나머지 B, C번 문제가 좋아서 업솔빙을 한다. 이번 대회에서 배운 것은

1. 경로 압축 방법과 value-index pair 배열의 활용
2. 이항계수의 성질 복습 및 dp
3. 제발 정렬하는 것도 생각해보자.

A. Ezzat and Two Subsequences (*800)

접기/펼치기

문제 설명
배열 1개가 주어지고 이 배열을 두 subsequences $a$, $b$로 나누는 것이 목표이다. 이때 각 배열에 최소 원소 1개 이상이 있어야 한다. 그리고 이 배열의 평균 $f(a)$, $f(b)$ 의 합인 $f(a)+f(b)$ 의 최대값을 구해야 한다.

이때 subsequence 는 한 배열에서 무작위 원소를 제거해서 얻을 수 있는 수열이다. 즉 배열의 원소는 연속할 필요가 없다.

문제 해설
이 문제는 두가지 방법으로 접근할 수 있다.

1. naive하게 접근하는 방법: 작은 것은 작은 것끼리, 큰 것은 큰 것끼리 모아서 평균을 구하면 전체 평균이 크기 때문에 배열을 정렬 한 다음에 처음부터 끝까지 배열을 두개로 쪼개서 얻은 모든 값 중에서 최대값을 구한다. 즉 총 배열의 원소가 10개라면 $(1,9),(2,8),...(8,2),(9,1)$ 이런식으로 배열의 원소를 index 0부터 차례대로 평균을 구한다.
2. 가장 큰 원소를 a라고 하고, 나머지 배열을 b라고 한다. 1번 접근법과 비슷하지만 좀 더 직관적인 방법이다. 가장 큰 원소를 나누지 않아서 최대한 큰 값을 보존하고 나머지 값들을 평균내서 구하는 방법이다. 이 사실을 문제에 나오는 example에서 조금만 해본다면 답이 이거일까? 라고 생각이 들면서 바로 시도해볼 수 있다. 사실 그냥 때려 맞추는 문제가 codeforce A번에 자주 나온다. 이거 증명하는 과정은 솔직히 이해 안된다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        long long sum = 0, mx = -1e10;
        for(int i = 0; i < n; i++){
            long long num; cin >> num;
            sum += num;
            mx = max(mx, num);
        }
        cout.precision(10);
        cout << fixed << 1.0 * (sum - mx) / (n - 1) + mx * 1.0 << "\n";
    }
    return 0;
}

B. Moamen and k-subarrays (*1100)

접기/펼치기

문제 설명
서로 다른 $n$개 정수가 있는 배열이 있는데, 다음 연산을 순서대로 해서 만든 배열이 오름차순 이 되는지 판별하는 문제이다.

1. 배열을 $k$개 빈 원소가 없는 subarray 로 분할한다.
2. 이 subarray 를 임의 순서대로 재배열 한다.
3. 재배열한 subarray 를 합친다.

subarray 와 subsequence 의 차이점은 subsequecne는 주어진 배열에서 임의의 원소를 선택해서 만들었다면 subarray는 반드시 주어진 배열에 있는 원소를 연속해서 선택해야 한다는 점이다. 주어진 배열의 원소를 연속해서 선택했는지 여부가 subarray와 subsequence의 차이점이다.

문제 해설
난이도 800, 900, 1000, 1100, 1200문제를 안정적으로 실수없이 반드시 푸는게 일단 내 목표이다. 이 문제는 내 목표의 장애물중 하나.
문제를 풀면서 느낀점은 자꾸 문제에서 요구하는 연산을 무조건 순서대로 처리하려고 하는 것이다. 이 연산도 중요하지만 결국은 이 문제에서 중요한 점은 배열을 나누었을 때 오름차순으로 만들 수 있는가? 인데 나는 문제를 풀때마다 $k$개 배열을 나누어야 한다는 것에 갇혀서 문제를 못 푸는 것 같았다. 조급해하지 말고 넓은 시야를 가져야한다. 이 시야는 뭐, 코드포스 풀다보면 생기겠다는 낙관적인 생각으로 계속해야 안지칠 것 같다.

이 배열이 오름차순으로 재배열 할 수 있게 하려면 기본적으로 모든 수가 오름차순으로 정렬되어 있다면 자동으로 가능할 것이다. 이 배열이 내림차순으로 되어있는 구간이 있다면 그 구간은 반드시 둘로 쪼개야 해야 재배열을 할 때 오름차순으로 만들 수 있기 때문이다.

그렇다면 무작정 내림차순인 구간만 찾아서 개수를 세면 답이 나오는가? 내가 여기까지 밖에 생각을 못했다. 연속하는 두 원소가 오름차순이어도 다른 index의 원소에서 그 구간에 사이에 있는 원소가 존재하다면 그 구간은 또 둘로 나누어야 한다. 왜냐하면 사이에 있는 원소가 다른 곳에 있기 때문에 그 원소가 그 구간에 가운데에 반드시 있어야 전체 배열이 오름차순이 될 수 있기 때문이다.

이런 문제를 풀기 위해서 원소의 값과 index를 동시에 가지고 있는 배열을 만든 다음 그 배열을 값을 기준으로 정렬한다. 그렇다면 오름차순으로 이미 되어 있는 구간이라면 정렬된 배열을 처음부터 확인할 때 index가 오름차순으로 되어있을 것이다. 이것만 확인하면 안된다. 그 구간 사이에 원소가 없으려면 index 배열을 $idx$라고 할 때, $idx[i]+1=idx[i+1]$ 을 만족해야 이 구간 사이에 원소가 없고, 한 subarray로 묶어도 오름차순에는 영향이 없다는 것이 된다. 다시 말하면 저 조건을 만족하지 못하면 그 구간은 둘로 쪼개야 한다. 이렇게 구한 쪼개야 하는 횟수를 $k$개라고 하면 총 나오는 subarray의 개수는 $k+1$ 개 이고 이 값을 주어진 문제 값과 비교해서 문제 값보다 크면 "no", 작거나 같으면 "yes"를 출력하면 된다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        vector<pair<int, int>> v;
        for(int i = 0; i < n; i++){
            int num; cin >> num;
            v.push_back({num, i});
        }
        sort(v.begin(), v.end());
        int cnt = 0;
        for(int i = 0; i < n - 1; i++){
            if(v[i].second + 1 != v[i + 1].second) cnt++;
        }
        cout << (cnt < k ? "Yes" : "No") << "\n";
    }
    return 0;
}

C. Moamen and XOR (*1700)

접기/펼치기

문제 설명
각 원소의 값이 모두 $2^k$ 보다 작은 $n$개 양수로 이루어진 배열 $a$가 주어진다.

다음 조건을 만족하는 배열의 개수를 구하시오.

• $a_1$ & $a_2$ & $a_3$ & $...$ & $a_n$ $\ge a_1\oplus a_2\oplus a_3\oplus ...\oplus a_n$

결과 값이 매우 크므로 값을 $({10}^9+7)$ 로 나눈 나머지 값을 출력한다.

문제 해설
보자마자 때려친 문제이지만 계속 업솔빙 하면 풀 수 있을 것이라 믿으며 계속 공부한다.
이 문제는 dp와 비트마스크를 결합한 문제이다. 일단 문제에서 $2^k$보다 작은 원소로 이루어진 이라는 표현을 보자마자 비트로 장난치는 문제라는 것을 직감했다.

배열 $a$는 모든 원소가 $2^k$보다 작은 값으로 이루어진다. $2^k$보다 작은 수는 비트 자릿수가 $k$개로 이루어진다. 예시로 $2^3=8$ 보다 작은 수는 $000$ 부터 $111$ 까지로 표현할 수 있다. 그러면 원소 $n$개를 차례대로 아래 방향으로 나열하고 각 원소를 비트 표현으로 바꾸면 $n\times k$ 형태의 행렬이 만들어 진다. 그리고 각 행렬의 열부분 비트를 각각 계산해서 답을 구한다.

& 연산자는 모든 비트의 값이 $1$이어야 $1$을 출력하고 나머지 경우는 모두 $0$을 출력한다. 그리고 $\oplus$ 연산자는 $1$의 개수가 짝수이면 $0$, $1$의 개수가 홀수이면 $1$을 출력한다는 특징을 가지고 이 특징을 이번 문제에서 사용한다. 비트로 수를 비교할 때, MSB값이 한쪽이 1이고, 다른 한쪽이 0이면 MSB가 0인 수가 MSB값이 1인 수 보다 무조건 작다는 것을 알아야 한다.

$\oplus$ 가 홀, 짝에 따라서 값의 경향성이 달라지기 때문에 $n$의 개수가 홀수인지, 짝수인지 경우를 나눠보자.

1. $n$이 짝수일 경우.

   • 만약 첫번째 열의 모든 값이 1이면 & 연산의 값은 1이다. 하지만 $\oplus$연산은 1이 짝수개 있으므로 값이 0이다. 즉 무조건 조건을 만족하기 때문에 뒤에 있는 비트는 볼 필요가 없다. 총 배열의 열은 $k$개 이므로 $n\times (k-1)$ 개 비트가 가질 수 있는 모든 경우의 수는 $2^{n(k-1)}$ 개이고, 이 값을 빠르게 구하기 위해서 빠른 거듭제곱 알고리즘을 미리 구현해 둔다.

   • 만약 첫번째 열의 모든 값이 1이 아니라면 & 연산의 값은 0이므로 다음 비트를 비교할 수 있는 기회를 얻기 위해서는 $\oplus$ 연산의 값이 0이 되어야 한다. 이때 $n$이 짝수개인 상태에서 짝수개의 원소의 비트가 1이 되어야 하기 때문에 그 경우의 수는 $nC0+nC2+...+nC(n-1)+nCn$ 이다. 이때 이항계수의 총 합은 성질에 의해 $2^{n-1}$ 개 이고, $nCn$ 경우는 한 열의 모든 비트가 $1$인 경우이므로 이미 위에서 계산했다. 따라서 1을 빼준다. 첫번째 열에서 얻을 수 있는 경우의 수는 $2^{n-1}-1$개 이고 나머지 열 $k-1$의 가장 맨 앞에 있는 열을 토대로 구한 경우의 수와 곱하면 최종 답이다. 여기서 $k-1$일 때 구해야 하는 경우의 수를 빠르게 구하기 위해서 우리는 다이나믹 프로그래밍 기법을 사용한다.

   • 우리는 $dp[k]$를 다음과 같이 정의한다. LSB부터 $k$번째 열까지 확인했을 때, 얻을 수 있는 경우의 수. 이때 $dp[0]=1$ 이다. 왜냐하면 $0$번째 열은 각 원소의 값이 $1$보다 작은 경우를 의미하고, 그 경우에는 모든 원소가 0인 경우 한가지 밖에 없기 때문이다.

   • 앞서 정의한 dp를 사용해서 $n$이 짝수인 경우 점화식을 다시 구하면 다음과 같다.
     $dp(k)=2^{n(k-1)}+(2^{n-1}-1)dp(k-1)$

2. $n$이 홀수인 경우.

   • 만약 첫번째 열의 모든 값이 1이라면 & 연산의 값은 1이지만 $\oplus$ 연산의 값은 1이 홀수개 있으므로 값이 $1$이다. 즉 다음 $k-1$개 열의 경우의 수를 더해야 한다.

   • 만약 첫번째 열의 모든 값이 1이 아니라면 $\oplus$ 의 값이 0이 되어야 하고, $n$은 홀수이므로 짝수개를 선택하려면 $nC0+nC2+...nC(n-3)+nC(n-1)$ 값을 구해야하고, 이 값도 마찬가지로 이항계수의 성질에 따라 $2^{n-1}$이다. 그리고 다음 $k-1$열의 경우의 수를 곱하고 마지막에 더하면 된다.

   • 앞서 정의한 dp를 사용해서 $n$이 홀수인 경우 점화식을 다시 구하면 다음과 같다.
     $dp(k)=(2^{n-1}+1)dp(k-1)$

$dp(k)$값을 구하면 그것이 답이다. $n$과 $k$의 범위가 ${10}^5$이므로 그냥 대충 곱하면 TLE가 나기 때문에 반드시 빠른 거듭제곱 알고리즘을 사용해서 풀어야 한다. 나는 Bottom-up 방식으로 풀었다.

정답 코드

#include <iostream>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;

ll poww(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

ll dp[200001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    dp[0] = 1;
    while(t--){
        ll n, k; cin >> n >> k;
        ll base = poww(2LL, n - 1);
        for(int i = 1; i <= k; i++){
            if(n & 1) dp[i] = (dp[i - 1] * (base + 1)) % mod;
            else dp[i] = (poww(2LL, n * (i - 1)) + (base - 1) * dp[i - 1]) % mod;
        }
        cout << dp[k] << "\n";
    }
    return 0;
}