일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- Manacher's algorithm
- 그래프
- 컨벡스 헐
- convex hull
- 세그먼트 트리
- BAPC 2018
- 기하
- codeforces
- 8192
- 2794
- 볼록 껍질
- JOI
- acmicpc.net
- 백준 온라인 저지
- JOI 2018
- IOI 2013
- POI Solution
- 코드포스
- 구현
- boj
- Z 알고리즘
- BAPC
- Divide and conquer optimization
- Z algorithm
- Manacher 알고리즘
- ICPC 연습
- DP
- 기하 알고리즘
- 14179
- Implementation
- Today
- Total
프로그래밍 연습장
180324 동아리 연습 문제 풀이 본문
A. 쉬운 정렬
C++에 내장되어 있는 정렬 함수를 사용한다. 다음 소스를 참고하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | #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(""); } | cs |
B. 음반
A번에서 배웠던 것을 이용해, 각 음반의 가격을 오름차순으로 정렬한다. 그러면, 가격이 낮은 음반부터 선택하면 항상 가장 많은 개수의 음반을 선택할 수 있다는 것을 알 수 있다. 그래서, 가격이 낮은 음반부터 차례대로 돌면서 가격이 $k$ 이하가 되는 한에서 계속 합해 나간다.
C. Lower Bound
이진 탐색을 이용해 해결한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #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]); } } | cs |
이 때 중요한 것은 불변 조건이다. $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$이라는 것은 이미 있는 수들의 선형결합으로 나타낼 수 있다는 것이므로 이 수는 없어도 됨을 뜻한다. 이 때는 새로운 수를 넣지 않아도 된다.
해답 소스는 생각보다 간단하게 나오며, 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #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); } | cs |
'문제 해결' 카테고리의 다른 글
180428 동아리 연습 문제 풀이 (1) | 2018.04.28 |
---|---|
180421 동아리 연습 문제 풀이 (1) | 2018.04.21 |
Polish Problems (11-15) (0) | 2018.03.14 |
Polish Problems (6-10) (0) | 2018.03.06 |
Polish Problems (1~5) (0) | 2018.03.02 |