180324 동아리 연습 문제 풀이

A. 쉬운 정렬

C++에 내장되어 있는 정렬 함수를 사용한다. 다음 소스를 참고하면 된다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, a[304];
 
int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
 
    sort(a, a+n);
    for (int i=0; i<n; i++) printf("%d ", a[i]); puts("");
}

B. 음반

A번에서 배웠던 것을 이용해, 각 음반의 가격을 오름차순으로 정렬한다. 그러면, 가격이 낮은 음반부터 선택하면 항상 가장 많은 개수의 음반을 선택할 수 있다는 것을 알 수 있다. 그래서, 가격이 낮은 음반부터 차례대로 돌면서 가격이 $k$ 이하가 되는 한에서 계속 합해 나간다.

C. Lower Bound

이진 탐색을 이용해 해결한다.

#include <stdio.h>
 
int n, q, a[100004];
 
int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
 
    scanf("%d", &q);
    for (int i=0; i<q; i++) {
        int x, ans;
        scanf("%d", &x);
 
        /// Binary search 이진탐색
        int l = -1 , r = n;
        /// 불변 조건: a[l] < x 이고, a[r] >= x
        /// 초기에 a[-1]은 굉장히 작은 수, a[n]은 굉장히 큰 수라 가정.
        while (l+1<r) {
            int m = (l + r) / 2;
 
            if (a[m] >= x) /// 오른쪽 절반을 들어낸다.
                r = m;
            else /// 왼쪽 절반을 들어낸다.
                l = m;
        }
        ans = r;
        if (ans == n) printf("-1\n");
        else printf("%d\n", a[ans]);
    }
}

이 때 중요한 것은 불변 조건이다. $l$과 $r$이 이진 탐색을 하는 범위의 양 끝을 맡고 있는데, 이 때 배열의 $l$번째 원소는 우리가 찾는 $x$ 미만이고, $r$번째 원소는 우리가 찾는 $x$ 이상이다. 배열을 "$x$ 미만인 부분"과 "$x$ 이상인 부분"으로 양쪽으로 나눌 때에, $l$은 왼쪽 부분에, $r$은 오른쪽 부분에 존재한다. 구현을 할 때 헷갈린다면, 그냥 위에 있는 코드를 외우는 것도 괜찮다.

D. 예산

한국정보올림피아드 기출문제이다. 이진 탐색을 C와 동일하게 진행한다. 다만, 조건을 C와 같이 "크기가 $x$ 이상이다"로 하지 않고, "최대 예산을 $x$로 설정했을 때에 가능하다"로 바꾸어서 이진 탐색을 돌리면 된다. C번 코드와 다른 점은 기껏해야 21번 줄의 조건문의 조건이다. 이 때에, 이진 탐색의 탐색 범위를 나타내는 두 변수 $l$, $r$은 다음 불변 조건을 만족한다: 최대 예산이 $l$일 때에는, 넘치지 않게 배정할 수 있다. 최대 예산이 $r$일 때에는, 넘치지 않게 배정할 수 없다.

이를 다른 말로 parametric search(파라매트릭 서치)라고 한다. 파라매트릭 서치를 쓰지 않고 풀 수 있는 풀이도 있으니 생각해 보자.

E. 선택

$N$개의 원소(간식) 중에서 몇 개를 고르는 과정이다. 전체집합 $S$, 첫번째 사람이 고른 간식의 집합 $S_1$, 두번째 사람이 고른 간식의 집합 $S_2$의 세 개의 집합이 $S \supseteq S_1 \supseteq S_2$를 만족하게 만들어지게 된다. 이 때, 각 원소는 $S - S_1$, $S_1 - S_2$, $S_2$ 셋 중 하나의 집합에 들어갈 수 있다. 각 원소가 어떤 집합에 들어가는지는 완전히 독립적이므로, $3^N$가지 가짓수는 있다. 단, $S_2 \neq \emptyset$이므로, $S_2$를 제외한 두 집합에만 원소를 집어넣는 $2^N$가지 가짓수는 제외해야 한다. 따라서 $3^N - 2^N$를 10억 7로 나눈 나머지를 출력하면 정답이 된다.

주의: $3^N$을 구하는 과정 중 $100000007 \times 3$이 int 범위인 21억을 넘어 문제가 될 수도 있다.

F. 셔플

이 링크를 참조하여 풀면 된다. 중요한 것은, shuffle_a 함수는 "균등하지 않게" 순열을 섞는다는 것이다. shuffle_su에서 원소를 섞을 때에는 한 번 앞으로 이동한 원소는 다시는 앞으로 이동해올 수 없기 때문에(하지만 뒤로 이동하는 것은 몇 번이든 가능하다) 작은 원소가 뒤로 가고, 큰 원소는 앞으로 가는 경향이 강하다.

쉬운 풀이는 a[i] >= i인 $i$의 개수를 세는 것이다. shuffle_a는 균등하지 않기 때문에, 470개 정도의 $i$만이 이 조건을 만족하게 된다. shuffle_b은 균등하기 때문에, 평균적으로는 정확히 500개가 나오게 된다. 485 정도의 수를 기준으로 분류하면 해결할 수 있다.

보다 어렵지만 정확한 풀이는 베이즈의 정리를 활용한다. 그 풀이는 위 링크에 있다.

G. XOR Magic

각 수를 이진수로 생각하자. 그리고 어떤 이진수 $x$의 MSB를 이 이진수의 "켜져있는 가장 높은 비트"로 정의하자. 예를 들면 $6 = 110_{(2)}$는 MSB가 2($2^2$의 자리를 나타내는 비트)번째 비트이고, $1 = 1_{(2)}$는 MSB가 0번째 비트이다.

먼저, 집합의 각 원소의 MSB가 다를 때에는, 가장 큰 수를 손쉽게 만들 수 있다. $a_1 > \cdots > a_n$이 서로 다른 MSB를 가지고 있다고 하자.

1. $a_1$을 선택해서 얻을 수 있는 MSB는 다른 수를 선택해서는 얻을 수 없다. 따라서 $a_1$는 무조건 선택해야 한다.

2-1. $a_1$을 선택한 후 $a_2$의 MSB가 켜지지 않았다고 하자. 그러면, 같은 논리로 $a_2$도 무조건 선택해야 한다.

2-2. $a_1$을 선택한 후 $a_2$의 MSB가 켜졌다고 하자. 그러면, $a_2$를 선택하면 굳이 켜져 있던 MSB를 끄는 것이 되므로 선택하지 않는 것이 유리하다.

위 과정을 계속 반복하면, 각 원소의 MSB가 다른 경우에는 무조건 최대의 XOR 결과를 만들 수 있다. 하지만, 같은 MSB를 가진 원소가 여러 개 있으면 어떻게 선택해야 할 지는 알 수 없다. 그래서, 같은 MSB를 가지는 수들을 하나로 만들 필요가 존재한다.

서로 다른 MSB를 가지는 수들은 최대 60개 존재할 수 있으므로(수의 범위가 $2^{60}$ 미만이므로), 길이 60의 배열 $A$을 만든다. $A$의 $i$번째 원소는 비어있거나, MSB가 $i$번째 비트인 수(즉, $2^i \le x < 2^{i+1}$인 수)여야 한다. 이제 하나씩 수를 추가해 나가면서 이들 중 60개만 살릴 수 있다.

1. 새로운 수 $x$가 들어갈 수 있는 배열의 인덱스는 단 하나 존재한다. 그것을 $i$번째 인덱스라고 하자.

2-1. $a[i]$가 비어있다면, 그냥 $a[i] = x$로 채우면 된다.

2-2. $a[i]$가 비어있지 않다면, 단순히 2-1처럼 채우면 안 된다. 기존에 $a[i]$에 있던 원소도 고려해야 하기 때문. 이 때, $x$를 배열에 집어넣는 것과 $a[i] \operatorname{xor} x$를 배열에 집어넣는 것은 동등한 효과를 가진다. 따라서 $x$를 $a[i]$와 xor 연산을 한다. 이 때, 양쪽의 MSB가 같으므로 양쪽의 MSB에 해당하는 비트는 1이기에, xor한 결과의 그 비트는 0이 된다. 따라서 $a[i] \operatorname{xor} x$의 MSB는 $x$의 그것보다 작다. 따라서 연산한 결과를 $y$라고 하고, 다시 $y$를 집어넣기 위해 1번의 과정부터 반복한다. $y=0$이라는 것은 이미 있는 수들의 선형결합으로 나타낼 수 있다는 것이므로 이 수는 없어도 됨을 뜻한다. 이 때는 새로운 수를 넣지 않아도 된다.

해답 소스는 생각보다 간단하게 나오며, 다음과 같다.

#include <stdio.h>
using namespace std;
 
typedef long long lint;
 
lint mul2[66], a[66];
 
int main() {
    mul2[0] = 1;
    for (int i=1; i<60; i++) mul2[i] = mul2[i-1] * 2;
 
    int n;
    scanf("%d", &n);
 
    for (int i=0; i<n; i++) {
        lint x;
        scanf("%lld", &x);
        int j = 59;
        for (; 0<=j; j--) if (x < mul2[j] * 2) break;
        for (; 0<=j; j--) if (mul2[j] <= x) {
            if (a[j]) x ^= a[j];
            else break;
        }
 
        if (j>=0) a[j] = x;
    }
 
    lint ans = 0;
    for (int i=59; 0<=i; i--) if (ans < (ans ^ a[i])) ans ^= a[i];
 
    printf("%lld\n", ans);
}