2022 고려대학교 프로그래밍 경시대회 (KCPC mini) Open Contest
2022 고려대학교 프로그래밍 경시대회 (KCPC mini) - Open Contest
www.acmicpc.net
A - 금공강 사수
완전 탐색
00:08 AC
B - 참살이길
정렬 + 수학
00:17 WA
정렬 코드를 빼먹었다.
00:18 RTE
신호등이 없는 경우를 고려하지 않았다.
00:19 AC
C - 읽씹 멈춰!
2진수로 생각하면 된다.
00:24 WA
예제만 잘 나오는 완전히 잘못된 코드였다.
00:28 WA
s 대신 1을 사용하였다.
예제 데이터의 s도 1이어서 예제는 잘 나왔다.
00:31 WA
overflow가 발생하였다.
__int128 타입을 사용하여 해결하였다.
00:33 AC
__int128 타입을 사용하는 대신 다음과 같이 비교하면 overflow를 방지할 수 있다.
s * N <= t 대신 s <= t / N
D - 아 또 XOR이야?
다음과 같은 solve 함수를 정의하자.
ll solve(ll x) {
return 0 이상 x 미만의 정수 중 조건을 만족하는 수의 개수
}
답은 solve(B + 1) - solve(A)가 된다.
solve 함수의 구현 방법을 살펴 보자.
x를 비트 단위로 보면 되는데 값이 1인 비트만 고려하면 된다.
예를 들어 x = 21 = 10101(2)이라고 하자.
값이 1인 비트를 기준으로 구간 [0, 21)을 다음과 같이 분할할 수 있다.
[0, 16), [16, 20), [20, 21)
분할된 구간을 살펴 보면 상위 비트는 고정되어 있고 하위 n 비트만 변화하는 것을 확인할 수 있다.
하위 n 비트는 고려 대상이 아니므로 상위 비트 중 켜져 있는 것의 개수에만 집중하면 된다.
구체적으로는 다음과 같이 계산할 수 있다.
ll y = x & -x;
x -= y;
int cnt = __builtin_popcountll((N & ~(y - 1)) ^ x);
int n = __builtin_ctzll(y);
이제 하위 n 비트 중 (K - cnt)개의 비트를 켜는 경우의 수를 구하면 되는데 이는 조합으로 구할 수 있다.
01:05 AC
E - 산유국
누적 합 + Segment Tree
01:11 AC
G - 순찰 경로
다음과 같은 2차원 배열을 정의하자.
A[i] = 깊이가 i인 정점들의 목록
이는 임의의 정점에서 dfs를 돌려서 구할 수 있다.
다음과 같은 사실을 관찰할 수 있다.
- 깊이가 i인 정점 중 임의의 두 정점을 잇는 도로는 항상 존재한다.
- 2 이상의 k에 대하여 깊이가 각각 i와 (i + k)인 임의의 두 정점을 잇는 도로는 항상 존재한다.
이를 이용하여 경로를 구성할 수 있다.
차수가 (N - 1)인 정점이 있다면 답은 -1이 된다.
그렇지 않다면 다음과 같이 경로를 구성할 수 있다.
- A[1]의 크기가 1인 경우 깊이가 1, 3, 5, ... 인 정점을 방문한 후 깊이가 0, 2, 4, ... 인 정점을 방문한다.
- 그렇지 않다면 깊이가 0, 2, 4, ... 인 정점을 방문한 후 깊이가 1, 3, 5, ... 인 정점을 방문한다.
02:31 WA
다음과 같은 코너 케이스가 존재한다.
4
1 2
1 3
2 4
위의 입력에서 순찰 경로는 1 - 4 - 2 - 3과 같이 구성되며 문제의 조건을 위반한다.
이러한 경우 A[1]의 크기는 2 이상이므로 적절히 예외 처리를 하면 반드시 경로를 구성할 수 있다.
02:38 WA
구현 방법에 경미한 오류가 있었다.
02:51 AC
더 간단한 풀이가 존재한다.
dfs를 임의의 리프에서 시작하도록 하자.
이렇게 하면 A[1]의 크기는 1이 되며 트리의 높이는 3 이상이 된다.
따라서 항상 깊이가 1, 3, 5, ... 인 정점을 방문한 후 깊이가 0, 2, 4, ... 인 정점을 방문하도록 하면 된다.
위의 코너 케이스와 같은 예외 처리도 필요하지 않다.
F - 단조증가 수열과 OR
01:37 WA 01:46 WA 02:10 WA
여러 그리디 풀이를 시도하였고 실패하였다.
에디토리얼은 무슨 말인지 모르겠다.
아래에서 소개하는 풀이도 그리디인데 엄밀하게 증명하지는 않았다.
배열 B의 초깃값을 다음과 같이 정의하자.
B[i] = A[i - 1] & A[i];
초기에 켜진 비트 외의 다른 비트는 켜질 수 없다.
따라서 일부 비트를 적절히 꺼서 배열 B가 단조 증가하도록 만들어야 한다.
이를 위해서는 다음과 같은 관찰이 필요하다.
- B[i]에서 k번 비트를 끄려면 B[i - 1]과 B[i + 1]의 k번 비트가 켜져 있어야 한다.
마지막 수부터 역순으로 검사하자.
B[i]가 B[i + 1]보다 크다면 B[i]의 일부 비트를 꺼야 한다.
B[i]에만 켜져 있고 B[i + 1]에서는 꺼져 있는 비트 중 최상위 비트를 k번 비트라고 하자.
k번 비트는 끌 수 없으므로 k번 비트의 상위 비트를 꺼야 한다.
이때 상위 비트 중 B[i]와 B[i + 1] 그리고 B[i - 1] 모두에서 켜져 있는 비트를 끄면 된다.
그러한 비트가 여러 개 있다면 가장 하위 비트를 끄면 된다.
모든 수에 대하여 위의 과정을 마친 후 문제의 조건을 만족하는지 확인해주자.
03:23 AC
I - 알록달록 트리 (not solved)
i번 정점을 특정 색으로 칠하는 경우의 수 A[i]는 다음과 같이 구할 수 있다.
for j = L[i]; j <= R[i]; ++j
A[i] += j * (K - 1)! / (K - j)! * S(d, j);
여기서 d는 i번 정점의 자식의 개수이며 S(n, k)는 제2종 스털링 수를 의미한다.
각 정점을 칠하는 것은 독립적이므로 모든 정점에 대하여 위의 값을 구한 후 곱해주면 된다.
마지막으로 1번 정점은 K개의 색 중 임의의 색으로 칠하면 되므로 추가적으로 K를 곱해주면 된다.
이 문제의 핵심은 제2종 스털링 수를 빠르게 구하는 것이다.
식이 복잡하기 때문에 일반적인 방법으로는 구하기 어렵고 FFT를 사용해야 한다.
그리고 계산 결과가 매우 커질 수 있기 때문에 NTT를 사용해야 한다.
H - 화살표 수집가 (not solved)
2023/08/23 업솔빙하였다.
각도 정렬 + two pointer + offline query + fenwick tree 비빔밥
끝
끝