2022 고려대학교 프로그래밍 경시대회 (KCPC mini) Open Contest

2022 고려대학교 프로그래밍 경시대회 (KCPC mini) - Open Contest

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 비빔밥

 

끝

끝