Codeforces Round #672 (Div. 2) A~C1번 풀이

얼마 전 Codeforces Round #672 (Div. 2)에 참가했습니다. 

처음으로 문제를 3개나 풀어서 행복했습니다.

그래서 대회 중 풀었던 A번, B번, C1번의 풀이를 써 보려 합니다.

A번 - Cubes Sorting

문제

Problem - A - Codeforces

문제 설명

$N$개의 정육면체가 한 줄로 놓여 있을 때, 부피가 큰 순으로 정렬한다고 합니다.

단, 두 인접한 정육면체를 교환하는 작업만 할 수 있습니다.

각 정육면체의 부피가 주어질 때,

정렬을 위해 필요한 최소 교환 횟수가 $\frac{N\times (N-1)}{2}$회 미만이라면 YES, 아니면 NO를 출력하는 문제입니다.

풀이

두 인접한 원소만 교환하여 정렬하는 알고리즘으로는 버블 정렬이 있습니다.

버블 정렬의 최대 교환 횟수는$\frac{N\times (N-1)}{2}$입니다. 오름차순으로 정렬할 때, $\frac{N\times (N-1)}{2}$번 교환해야 하는 최악의 경우는

인접한 두 원소를 비교하였을 때 항상 앞 원소가 뒤 원소보다 큰 경우입니다.

따라서 정육면체가 내림차순으로 정렬되어 있고 부피가 같은 정육면체가 하나도 없다면 NO를 출력해야 하는 최악의 경우이며,

아니라면 YES를 출력하면 됩니다.

코드

#include <cstdio>
#include <algorithm>
 
using namespace std;
int arr[100005]; 
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        bool ans = false;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &arr[i]);
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] <= arr[i + 1]) {
                ans = true;
                break;
            }
        }
        if (ans)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

B번 - Rock and Lever

문제

Problem - B - Codeforces

문제 설명

비트 연산에 대한 문제입니다.

$a_1, a_2, ... , a_N$까지 N개의 자연수가 주어집니다. 

이 중에서 두 수 $a_i, a_j$를 골랐을 때, 두 수를 and연산한 값이 xor연산한 값보다 큰 경우가 몇 가지인지 구하는 문제입니다.

같은 쌍이 두 번 체크되는 것을 막기 위해 $i < j$라는 조건이 있습니다.

풀이

두 수를 이진수로 바꾸면 $a_i = 00010010, a_j = 00001011$과 같은 형태가 됩니다.

여기서 고려해야 할 비트의 위치는 두 수 중 1이 있는 가장 왼쪽의 자리입니다. 

위 예시에서 $a_i$는 왼쪽에서 네 번째 자리에, $a_j$는 왼쪽에서 다섯 번째 자리가 가장 왼쪽 1이므로

둘 중 더 왼쪽인 네 번째 자리의 비트를 고려하면 됩니다. 

 

$a_i$의 해당 비트와 $a_j$의 해당 비트가 모두 1이라면 and연산의 결과는 1, xor연산의 결과는 0이 됩니다.

하지만 위 예시처럼 두 비트 중 하나는 1, 하나는 0이라면 and연산의 결과는 0, xor연산의 결과는 1이 됩니다.

따라서 두 비트가 모두 1인 경우에는 and연산의 결과가, 아니라면 xor연산의 결과가 더 커집니다.

 

우리가 찾아야 하는 and연산의 결과를 자세히 보겠습니다.

두 비트가 모두 1이라는 것은 0110, 0101처럼 두 수의 가장 왼쪽 1의 위치가 같다는 것을 의미합니다.

따라서 and연산이 더 큰 경우의 가짓수는 가장 왼쪽 1의 위치가 같은 쌍의 개수와 같습니다.

 

입력되는 수는 $10^9$보다 작으므로, 확실히 $2^{31}$보다 작습니다. 즉 비트의 수는 31개입니다.

1번째 비트, 2번째 비트, ... 31번째 비트에 대해 해당 비트가 가장 왼쪽 1인 수의 개수를 센 뒤

가장 왼쪽 1의 위치가 같은 수들에 대해 서로 다른 수 두 개를 뽑을 수 있는 경우의 수를 세어 더해주면 됩니다.

코드

arr[i]는 i번째 비트가 가장 왼쪽 1인 수의 개수입니다.

정답이 int범위를 넘어갈 수 있으니 long long을 사용해야 합니다.

#include <cstdio>
#include <algorithm>
 
using namespace std;
int main() {
    long long int t, n, now, arr[32], cnt, s, ans;
    scanf("%lld", &t);
    while (t--) {
        for (int i = 0; i < 32; i++)
            arr[i] = 0;
        scanf("%lld", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &now);
            cnt = 0;
            while (now) {
                now /= 2;
                cnt++;
            }
            arr[cnt]++;
        }
        s = 0;
        ans = 0;
        now = 0;
        while (s < n) {
            if (arr[now])
                ans += arr[now] * (arr[now] - 1) / 2;
            s += arr[now++];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C1번 - Pokémon Army (easy version)

문제

Problem - C1 - Codeforces

문제 설명

$n$개의 포켓몬은 각각 $a_1, a_2, ... , a_n$만큼의 힘이 있습니다.

이 중 k개($1\leq k\leq n$)의 포켓몬을 선택하였습니다. 

선택된 포켓몬을 원래 순서대로 나열하였을 때 포켓몬들은 $a_1 - a_2 + a_3 - ...$만큼의 힘이 있다고 합니다.

이때 포켓몬들의 힘의 최댓값을 구하는 문제입니다.

풀이

DP로 풀었습니다.

$a_1, a_2, ... , a_n$을 앞에서부터 순차적으로 탐색합니다.

$a_i$를 보고 있다면 $a_i$를 선택하거나 $a_{i+1}$으로 넘어갈 수 있습니다.

$a_i\sim a_n$ 구간에서 더할 차례일 때 만들 수 있는 최대 힘을 $dp[i][0]$으로, 

뺄 차례일 때 만들 수 있는 최대 힘을 $dp[i][1]$으로 정의하겠습니다.

 

$a_i$를 보고 있고 더할 차례일 때 $dp[i][0]$은 $a_i$를 선택할 때의 최대 힘과 $a_{i+1}$으로 넘어갈 때의 최대 힘 중 큰 값이 됩니다.

즉, $dp[i][0] = max(dp[i+1][1]+a_i, dp[i+1][0])$입니다.

 

같은 방식으로 $dp[i][1] = max(dp[i+1][0]-a_i, dp[i+1][1])$입니다.

 

전체 집합에서의 최대 힘은 $dp[0][0]$이므로

$dp[0][0]$부터 $dp[n][0]$ 또는 $dp[n][1]$까지 재귀적으로 탐색하면 답을 구할 수 있습니다.

 

$i = n$일 때는 더할 차례라면 $a_i$값을 더하고, 뺄 차례라면 $a_i$를 빼지 말아야 합니다.

따라서 $dp[n][0] = a_i, dp[n][1] = 0$입니다. 이는 곧 재귀함수의 종료 조건이 됩니다.

코드

#include <cstdio>
#define SIZE 300005
long long dp[SIZE][2], a[SIZE];
long long max(long long a, long long b) {
    if (a > b)
        return a;
    else
        return b;
}
long long srch(int i, int op) {
    if (dp[i][op] != -1)
        return dp[i][op];
    if (op == 0)
        dp[i][0] = max(srch(i + 1, 1) + a[i], srch(i + 1, 0));
    else
        dp[i][1] = max(srch(i + 1, 0) - a[i], srch(i + 1, 1));
    return dp[i][op];
}
using namespace std;
int main() {
    int t, n, q;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &q);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
            dp[i][0] = dp[i][1] = -1;
        }
        dp[n - 1][0] = a[n - 1];
        dp[n - 1][1] = 0;
        printf("%lld\n", srch(0, 0));
    }
    return 0;
}