서론
2026년 11월 14일에 개최된 2026 ICPC Asia Seoul Regional Contest(한국 대학생 프로그래밍 경시대회) 비공식 풀이입니다.
이 글에서 설명한 풀이 외에도 문제를 해결하는 여러 방법이 존재할 수 있습니다. 제가 생각하는 난이도 순서대로 설명합니다.
K. Stepping Numbers
$10^{15}$ 이하인 모든 stepping number를 구한 뒤, 그중 $n$번째 수를 출력하면 됩니다. stepping number 는 총 $161\,913$개 존재하므로 제한 시간 안에 해결할 수 있습니다.
1 | |
D. Circuit X
upper layer의 pin에 붙은 번호를 왼쪽부터 차례대로 $A_1, A_2, \cdots, A_n$, lower layer의 pin에 붙은 번호를 $B_1, B_2, \cdots, B_n$이라고 합시다. 또한, 어떤 수 $x$가 $A$에서 등장하는 위치를 $A^{-1}_x$, $B$에서 등장하는 위치를 $B^{-1}_x$라고 합시다.
만약 어떤 두 수 $x, y$가 $A^{-1}_x < A^{-1}_y$ 와 $B^{-1}_x < B^{-1}_y$ 를 만족한다면, middle layer의 pin을 적당히 정해서 $x$와 $y$ 사이의 비용이 $0$이 되게 할 수도, $a+b$가 되게 할 수도 있습니다. 반대로 $A^{-1}_x < A^{-1}_y$ 이면서 $B^{-1}_x > B^{-1}_y$ 라면 $x$와 $y$ 사이의 비용은 $a$ 또는 $b$가 됩니다.
편의를 위해 $A_i = i$가 되도록 수를 다시 배정합시다. 즉, 입력으로 $A = (1, 3, 5, 2, 4)$, $B = (4, 1, 2, 3, 5)$로 주어졌을 때, 이를 $A = (1, 2, 3, 4, 5)$와 $B = (5, 1, 4, 2, 3)$으로 변환합시다. 문제의 답은 $B$의 inversion 개수를 이용해 결정할 수 있게 됩니다.
구체적으로, $B$의 inversion의 개수를 $I$라고 합시다. inversion을 이루는 $I$개의 정수 쌍은 $a$ 또는 $b$ 만큼 정답에 기여하고, inversion을 이루지 않는 ${n \choose 2} - I$개의 정수 쌍은 $0$ 또는 $a+b$ 만큼 정답에 기여합니다. 따라서 문제의 정답은 $I \cdot \min(a,b) + ({n \choose 2}-I) \cdot \min(0, a+b)$입니다.
1 | |
G. Glowing Devices
모든 장치를 장치가 켜지는 순서대로 나열합시다. 강제로 켜는 장치($t_i=0$으로 바꾼 장치)가 맨 앞에 오고, 남은 장치는 $t_i$의 오름차순으로 배열될 것입니다. 임곗값이 $t_i$인 장치는 자기 자신 앞에 $t_i$개 이상의 장치가 있어야 하므로, 뒤에서 $n-t_i$번째 또는 그보다 뒤에 위치해야 합니다. 이 점을 생각하면 모든 장치가 켜지는 것과 모든 $1 \le x \le n-1$에 대해 $t_i\ge x$인 강제로 켜지 않은 장치가 $n-x$개 이하인 것은 필요 충분 조건이라는 것을 알 수 있습니다.
임곗값 $t_i$가 큰 장치부터 차례대로 보면서, 강제로 켜지 않을 장치의 목록 $L$을 관리할 것입니다. 임곗값이 $t_i$이고, 강제로 켜는 비용이 $w_i$인 장치를 보는 상황을 생각합시다.
만약 $L$의 크기가 $n-t_i$보다 작다면, 일단 현재까지는 $i$번째 장치를 강제로 켤 필요가 없습니다. 따라서 $i$번째 장치도 $L$에 삽입합니다. 반대로, $L$의 크기가 $n-t_i$보다 크다면, $i$번째 장치를 강제로 켜거나, 강제로 켜지 않기로 했던 장치 중 하나는 강제로 켜야 합니다. 따라서 $L$에 있는 장치 중 가장 비용이 저렴한 장치의 비용 $w_j$가 $w_i$보다 싸면 $j$번째 장치 대신 $i$번째 장치를 $L$에 넣고, $w_i$가 더 싸면 $i$번째 장치를 강제로 켜면 됩니다.
이러한 그리디 전략을 효율적으로 구현하기 위해서는 (1) $L$에서 가장 비용이 작은 장치를 구하는 연산, (2) 가장 비용이 작은 장치를 제거하는 연산, (3) 장치를 $L$에 삽입하는 연산을 빠르게 수행할 수 있는 자료구조를 사용해야 합니다. 우선순위 큐를 사용하면 각 연산을 $O(\log n)$ 시간에 수행할 수 있습니다.
각 장치는 최대 한 번 우선순위 큐에 삽입하고 삭제하므로, 전체 시간 복잡도는 $O(n \log n)$입니다.
1 | |
다른 접근 방식으로도 같은 결론을 얻을 수 있습니다.
$d_i = n - t_i$라고 정의하면, 모든 $y$에 대해 $d_i \le y$인 강제로 켜지 않은 장치가 $y$개 이하가 되도록 만드는 문제로 바꿀 수 있습니다. 강제로 켜는 장치의 비용을 최소화하는 것은 강제로 켜지 않는 장치의 비용을 최대화하는 것과 같습니다. 따라서 마감 기한이 $d_i$이고 보상이 $w_i$인 작업 중 일부를 선택하여 처리하는 단위 작업 스케줄링 문제로 생각할 수 있습니다.
이러한 문제는 다음과 같이 우선순위 큐를 이용해 그리디하게 처리할 수 있습니다.
- 마감 기한이 가까운 작업부터 처리, 강제로 켜지 않을 장치의 목록을 우선순위 큐로 관리
- 만약 지금까지 선택한 장치가 $d_i$개 미만이라면 해당 장치 선택
- 만약 지금까지 수행한 장치가 $d_i$개라면, 일단 $i$번째 장치를 선택한 뒤 가장 가중치가 작은 장치를 버림
이는 위 코드에서 정렬 방향과 if(Q.size() > N - threshold)를 if(Q.size() > d[i])로 바꾼 것을 제외하면 모두 동일합니다. 이와 관련된 내용은 이 슬라이드의 52-54페이지에서도 확인할 수 있으므로, 관심이 있다면 읽어보시는 것을 추천합니다.
E. Drones
이차원 평면에 단순 다각형이 있습니다. 점 $p=(x, y)$가 주어질 때마다 점이 (1) 다각형의 내부 또는 경계 위에 있는지, (2) 다각형의 경계와 $d$ 이하만큼 떨어진 외부에 있는지, (3) 다각형의 경계와 $d$ 초과로 떨어져 있는지 판별해야 합니다.
이 문제를 해결하기 위해서는 아래 두 가지를 구현해야 합니다.
- 다각형 내부 판별
- 선분 - 점 거리 계산
다각형의 내부 판별은 계산 기하를 공부할 때 꼭 배우고 넘어가는 내용으로, 이 슬라이드의 23-26페이지에서 확인할 수 있습니다.
점 $p_1$과 $p_2$를 잇는 선분 $L$과 점 $p$ 사이의 거리를 계산할 때는 아래와 같이 두 가지 경우로 나눠서 계산해야 합니다.
- $L$에서 $p$와 가장 가까운 점이 $L$의 내부에 있는 경우
- $L$에서 $p$와 가장 가까운 점이 $p_1$ 또는 $p_2$인 경우
(1) 은 $p$에서 $L$을 연장한 직선에 내린 수선의 발이 $L$ 내부에 있다는 것과 동치입니다. 이는 각 $\angle p_2p_1p$와 각 $\angle p_1p_2p$가 모두 $90^\circ$ 이내인지 확인하면 되므로, 벡터의 내적을 이용해 판별할 수 있습니다.
이후 거리 계산은 $\frac{\vert ax_1+by_1+c \vert}{\sqrt{a^2+b^2}}$ 공식을 이용하는 것을 생각해 볼 수 있겠지만, 실수 오차 때문에 이 공식으로 문제를 해결하기는 어렵습니다. 대신, 정수 연산만 이용해 $\frac{2 \cdot \triangle pp_1p_2}{\vert\vert p_1-p_2 \vert\vert} \le d$ 인지 판별할 수 있습니다. 계산 과정에서 좌표의 네제곱 스케일의 정수를 다루게 되지만, 좌표는 모두 $10^4$ 이하이므로 64비트 정수를 이용해 계산할 수 있습니다.
(2) 는 단순히 두 점 사이의 거리를 계산하는 것으로 확인할 수 있습니다.
double 타입을 이용해 거리를 계산/비교하면 문제를 해결할 수 없고, long double 타입을 이용하면 거리를 구하는 방법에 따라 문제를 해결할 수도 있습니다. long double을 사용하더라도 나눗셈을 할 때 제수(divisor)에 sqrt가 들어가면 오차가 커지므로, 최대한 정수만 이용해 계산한 뒤 마지막에 두 정수의 나눗셈만 실수 타입으로 처리하는 등의 디테일이 필요합니다.
1 | |
B. Boss Raid Log
아래와 같이 두 배열을 정의합시다.
- $L_j:=$ $p_1, p_2, \cdots, p_j$만 고려했을 때, $s$에서 $p_j$가 등장할 수 있는 첫 위치
- $R_j:=$ $p_j, p_{j+1}, \cdots, p_n$만 고려했을 때, $s$에서 $p_j$가 등장할 수 있는 마지막 위치
$L_j$는 $L_{j-1}+d$ 이상인 위치 중 $s_i = p_j$를 만족하는 가장 작은 $i$ 이므로, 앞에서부터 그리디하게 구할 수 있습니다. 비슷하게 $R_j$는 $R_{j+1}-d$ 이하인 위치 중 $s_i = p_j$를 만족하는 가장 큰 $i$ 이므로, 뒤에서부터 그리디하게 구할 수 있습니다.
$p_j$가 $s$에서 등장하는 위치 $t_j$를 고정하면, 앞에 있는 $t_1, \cdots, t_{j-1}$과 뒤에 있는 $t_{j+1}, \cdots, t_m$은 독립적으로 결정할 수 있습니다. 따라서, $s_i = p_j$인 $i$가 어떤 성공적인 공격의 $t_j$가 되기 위한 필요 충분 조건은 $L_{j-1} + d \le i \le R_{j+1} - d$입니다. 이러한 구간을 $[s_j, e_j]$ 라고 합시다.
이제, $s$의 모든 위치 $1 \le i \le n$가 어떤 성공적인 공격의 일부가 될 수 있는지 판별해야 합니다. 이는 각 $i$마다 $s_i = p_j$ 이고 $s_j \le i \le e_j$인 $j$가 존재하는지 확인하면 됩니다. 따라서 $p_j$가 같은 $j$끼리 구간 $[s_j, e_j]$를 순서대로 저장해 두면, 이분 탐색을 이용해 어떤 $i$가 성공적인 공격의 일부가 될 수 있는지 확인할 수 있습니다.
전체 시간 복잡도는 $O((n+m) \log n)$ 입니다. 모든 이분 탐색에서 쿼리 위치가 $n$ 이하고 단조 증가한다는 것을 이용하면 $O(n+m)$ 시간에 해결할 수도 있습니다.
1 | |
J. Safe
설명의 편의를 위해 $n=\vert X\vert, m=\vert Y\vert$ 라고 하겠습니다.
문자열 $Y$를 2개 이상의 구간으로 나눠서, 모든 구간의 비용을 $L$ 이하로 만들 수 있는지 판별하는 결정 문제를 해결합시다. $Y$를 전부 한 글자씩 쪼개면 $n-1$번의 삭제와 $1$번의 대체 연산을 수행해 구간을 완성할 수 있습니다. 따라서 파라메트릭 탐색 범위의 상한은 $9n$ 이고, 결정 문제를 $O(\log n)$번 해결하면 전체 문제를 해결할 수 있습니다.
어떤 비용 표 $c$가 주어졌을 때, 문자열 $A$를 $B$로 바꾸는 최소 비용은 일반적인 edit distance 문제와 같이 DP를 이용해 $O(\vert A \vert \vert B \vert)$ 시간에 계산할 수 있습니다. 비용이 삼각 부등식을 만족하므로 한 글자를 여러 번 수정하거나, 삽입한 글자를 수정하는 등의 중복 연산을 고려하지 않아도 됩니다.
하지만 edit distance DP를 구간의 시작점마다 따로 돌리면 너무 느리므로, DP를 조금 변형해야 합니다. 먼저 설명의 편의를 위해 $Y$를 2개 이상의 구간으로 나눠야 한다는 조건을 없앤 버전의 문제를 생각해 봅시다.
$Y$의 앞쪽은 구간의 비용이 $L$ 이하가 되도록 잘 쪼갰고, $X[1\ldots i]$가 현재 구간 $Y[\ldots j]$와 같아지도록 만드는 최소 비용을 $D(j, i)$라고 정의합시다. $D(j, i)$에 저장되어 있는 비용은 문자열 전체가 아닌, 현재 구간만의 비용이라는 것에 주의해야 합니다.
만약 $Y$의 $j$번째 글자까지 처리했을 때 $D(j, n) \le L$ 이라면 $X$를 현재 구간으로 만드는 비용이 $L$ 이하임을 의미합니다. 따라서 이 위치에서 문자열을 분할해 $Y[j+1]$ 부터 새로운 구간을 시작할 수 있습니다. 그러면 $D(j, i)$에 $X$를 빈 문자열을 만드는 비용을 저장해야 하므로, $D(j, i) \leftarrow Del(i) = \sum_{k=1}^i C[X[k]][0]$ 으로 갱신해야 합니다.
이후 $D(m, n) \le L$인지 확인하면 판정 문제를 해결할 수 있습니다.
이제 다시 $Y$를 2개 이상의 구간으로 분리해야 하는 원래의 문제로 돌아옵시다. 아직 한 번도 분할하지 않은 상태와, 한 번 이상 분할한 상태를 따로 표현하기 위해 DP 테이블을 2개 관리해야 합니다.
- $D_1(j, i):=$ $X[1\ldots i]$를 $Y[1\ldots j]$로 바꾸는 최소 비용
- $D_2(j,i):=$ $Y$의 앞부분은 이미 비용이 $L$ 이하가 되도록 나눴고, $X[1\ldots i]$가 그 뒤에서 시작한 현재 구간 $Y[\ldots j]$와 같아지도록 만드는 최소 비용
점화식 계산은 크게 다르지 않습니다. 구간을 분할하는 조건이 $\min(D_1(j,n), D_2(j,n)) \le L$이 된 것과, 구간을 분할할 때 $D_2(j, i) \leftarrow \min(D_2(j,i), Del(i))$와 같이 $D_2$ 테이블만 갱신해야 한다는 것만 주의하면 됩니다. 이후 $D_2(m,n) \le L$인지 확인하면 판정 문제를 해결할 수 있습니다.
이러한 계산을 모든 $k$개의 비용 테이블에 대해 수행해야 하므로, 결정 문제를 푸는 데 $O(nmk)$ 만큼의 연산이 필요합니다. 따라서 전체 시간 복잡도는 $O(nmk \log n)$입니다.
1 | |
I. Potion Shop
이런 문제는 lose position의 조건을 추측한 뒤, lose position이 아닌 상태에서 항상 lose position을 만들 수 있고, lose position에서는 항상 lose position이 아닌 상태로 이동할 수밖에 없음을 보이는 방식으로 푸는 것이 일반적입니다.
먼저 두 번째 연산을 봅시다. 1개 이상 $p-1$개 이하의 돌을 아무 더미에서나 가져갈 수 있습니다. 즉, 두 번째 연산을 이용하면 돌 개수의 합을 $p$로 나눈 나머지를 원하는 수로 바꿀 수 있으므로, lose position을 구성하는 요소에 $\sum A_i \pmod p$를 넣을 수 있습니다.
두 번째 연산으로 $A_i \text{mod}\ p$를 자유롭게 수정할 수 있으므로, 첫 번째 연산에서는 $A_i$를 $p$로 나눈 몫만 생각해도 됩니다. 그러면 첫 번째 연산은 일반적인 님 게임과 같은 연산이 되므로, lose position을 구성하는 요소에 $\bigoplus \lfloor A_i/p \rfloor$를 넣을 수 있습니다.
여기까지 알아낸 lose position의 조건은 $\sum A_i \equiv 0 \pmod p$, $\bigoplus \lfloor A_i/p \rfloor = 0$ 입니다. 만약 둘 중 하나 이상의 조건을 만족하지 않는다면, 한 번의 연산으로 두 조건을 모두 만족하도록 만들 수 있음을 증명할 수 있습니다. 반대로, 두 조건을 모두 만족하는 상태에서는 어떤 연산을 하더라도 둘 중 하나는 깨지게 됩니다.
덧셈과 XOR 연산 모두 역연산이 존재하므로 필승 조건을 알아냈다면 쿼리를 처리하는 것은 간단합니다.
1 | |
M. Workbench
누적 합 배열 $F_i = f_1 + f_2 + \cdots + f_i$와 $S_i = s_1 + s_2 + \cdots + s_i$ 를 정의합시다. 아래 점화식을 $O(n^2)$보다 빠르게 계산해야 합니다.
$D(i) = \min_{0\le j < i,\ S_{i-1}-S_j\le m} \lbrace D(j) + \max(bF_i-bF_j, as_i+as_j) \rbrace$
$cost(j+1, i) = \max(bF_i-bF_j, as_i+as_j)$ 를 쪼개야 최적화를 할 수 있어 보입니다.
$bF_i-bF_j \ge as_i+as_j$ 를 적당히 정리하면 $bF_j+as_j \le bF_i-as_i$ 가 됩니다. $X_i = bF_i+as_i$, $Y_i = bF_i-as_i$ 라고 정의하면, $X_j \le Y_i$ 일 때는 $cost(j+1, i) = bF_i-bF_j$ 이고, $X_j > Y_i$ 일 때는 $cost(j+1, i) = as_i+as_j$ 가 됨을 알 수 있습니다.
이제 식은 아래와 같이 두 가지 경우로 나눠서 쓸 수 있습니다.
- $0 \le j < i$, $S_{i-1}-S_j \le m$ 이고 $X_j \le Y_i$ 면 $D(i) = bF_i + \min D(j) - bF_j$
- $0 \le j < i$, $S_{i-1}-S_j \le m$ 이고 $X_j > Y_i$ 면 $D(i) = as_i + \min D(j) + as_j$
$s_i \ge 1$ 이므로 $S_{i-1} < S_i$가 성립하고, $i$가 증가함에 따라 $S_{i-1}-S_j \le m$을 만족하는 $j$의 최솟값도 단조 증가합니다. 따라서 세그먼트 트리로 구간의 최솟값을 관리하면서, 더이상 사용되지 않는 $j$를 트리에서 삭제하는 방식을 생각해 볼 수 있습니다.
원소를 삭제하는 연산을 지원하기 위해서는, 세그먼트 트리의 리프 노드에서 std::multiset 과 같은 자료구조를 관리해야 합니다. 모든 정점에서 multiset을 관리할 필요 없이 리프에서만 관리해도 괜찮으므로, 시간 복잡도는 $O(n \log n)$ 를 유지할 수 있습니다.
1 | |
A. Baduk Solitaire
빈칸은 무시해도 됩니다. 주어진 문자열에서 .을 모두 지운 뒤 연결해서 하나의 문자열을 만듭시다. 이후 같은 색의 돌이 연속한 구간을 하나의 덩어리로 압축하고, 각 덩어리의 크기를 왼쪽부터 차례대로 $A_1, A_2, \cdots, A_k$라고 합시다. 만약 돌을 모두 제거하는 방법이 존재한다면, 각 덩어리를 쪼개지 않고 온전하게 제거하는 경우만 고려하더라도 항상 모든 돌을 제거할 수 있음을 증명할 수 있습니다.
구간 $[l, r]$ 내부의 덩어리만 지워서 구간 전체를 크기가 2 이상인 하나의 덩어리로 만들 수 있다면, 이 구간을 “좋은 구간”이라고 부릅시다. 마지막에 남는 덩어리에는 $A_l$과 $A_r$이 모두 포함되므로, 좋은 구간의 길이는 항상 홀수입니다.
모든 돌을 지울 수 있다는 것은 $A$를 여러 개의 좋은 구간으로 분할할 수 있다는 것과 동치입니다. 이때, 좋은 구간 3개를 이어 붙인 구간도 좋은 구간입니다. [BW..WB][WB..BW][BW..WB] 형태의 배열이 있을 때, 각 구간을 하나의 덩어리로 합치면 [B][W][B] 꼴이 되고, 가운데에 있는 [W]를 지우면 하나로 합쳐지기 때문입니다. 따라서 $A$를 3개 이상의 구간으로 나누는 경우는 고려할 필요가 없습니다. $k$가 홀수일 때는 배열 전체가 좋은 구간인지 판별하고, $k$가 짝수일 때는 $A_1, A_2, \cdots, A_i$와 $A_{i+1}, A_{i+2}, \cdots, A_k$가 각각 좋은 구간이 되도록 하는 홀수 $i$가 존재하는지 판별하면 됩니다.
이제 $k$가 홀수인 경우, 즉 $k = 2t+1$인 경우에 배열 전체가 좋은 구간인지 판별하는 방법을 알아봅시다.
만약 가운데에 있는 덩어리의 크기가 2 이상이라면($A_{t+1}\ge 2$) 구간 전체를 하나의 덩어리로 만들 수 있습니다. 반대로 $A_{t+1} < 2$ 라면 다른 곳에서 시작해야 합니다. 일반성을 잃지 않고 $p < t+1$ 이고 $A_p \ge 2$ 인 곳에서 시작한다고 합시다.
$A_p$를 중심으로 $x(\le p)$번 제거하면 $A_{p-x}, \cdots, A_{p+x}$가 하나의 덩어리로 합쳐지면서 덩어리 개수가 $2x$개 감소합니다. 따라서 새로운 배열의 가운데에 오는 덩어리는 원래 배열의 $A_{t+1+x}$가 됩니다. 즉, $p < t+1$ 인 $A_p$ 에서 시작하면, 배열의 가운데에 올 원소를 오른쪽으로 최대 $p-1$칸 이동시킬 수 있고, $p > t+1$인 $A_p$에서 시작하면 가운데에 올 원소를 왼쪽으로 $2t+1-p$칸 옮길 수 있습니다. 따라서 만약 크기가 1인 덩어리가 $t$개 이상 연속해서 놓여있다면, 어떻게 하더라도 가운데에 크기가 2 이상인 덩어리가 오도록 만들 수 없습니다.
정리하면, 길이가 $k=2t+1$인 배열 $A$가 좋은 구간일 필요충분조건은 $A_{t+1} \ge 2$ 거나, 크기가 1인 덩어리로만 구성된 가장 긴 구간의 길이가 $t$ 미만인 것입니다. 이 조건은 $O(n)$ 시간에 판정할 수 있습니다.
$k$가 짝수일 때는 모든 prefix와 suffix에 대해 위에서 알아낸 조건을 충족하는지 미리 계산해 두면, $O(n)$ 시간에 판별할 수 있습니다.
따라서 전체 시간 복잡도는 $O(n)$입니다.
1 | |
L. Summoning Triangle
비교적 단순하지만 상수 최적화가 필요한 $O(n^3 \log k)$ 풀이와 다소 복잡한 $O(n^3)$ 풀이가 있습니다. 이 글에서는 $O(n^3 \log k)$ 풀이를 설명합니다.
어떤 두 점 $A, B$을 잇는 선분을 한 변으로 하고, 왼쪽에 있는 점(CCW(A, B, p) > 0)을 나머지 한 꼭짓점으로 하는 삼각형을 모두 탐색할 것입니다. 선분 $\overline{AB}$를 선택하는 방법이 $O(n^2)$가지이므로, 해당 선분을 한 변으로 하는 삼각형을 $O(n \log k)$에 모두 보는 것이 목표입니다.
선분 $\overline{AB}$ 왼쪽에 있는 어떤 점 $q$가 삼각형 $ABp$ 안에 포함되기 위해서는 아래 세 가지 조건을 만족해야 합니다.
- $CCW(A,B,q) > 0$
- $CCW(B,p,q) > 0$
- $CCW(p,A,q) > 0$ 또는 $CCW(A,p,q) < 0$
선분 $\overline{AB}$의 왼쪽에 있는 점만 신경 쓸 것이므로 (1) 은 생각하지 않아도 됩니다. 각 $\angle BAp$의 크기가 증가하는 순서대로 점을 확인하면, 먼저 확인하는 점 $q$와 나중에 확인하는 점 $p$에 대해 $CCW(A, p, q) < 0$가 항상 성립합니다. 각도 정렬을 이용해 (3) 조건도 없앨 수 있으므로, 남은 조건은 (2) 뿐입니다.
지금까지 확인한 점들을 적절한 자료구조로 관리해서, 삼각형 $ABp$에 각 색깔마다 정확히 하나의 점만 포함되는지 확인할 수 있어야 합니다. 이를 위해 각 색깔 $c$마다, 지금까지 본 점들 중 각 $\angle ABq$가 가장 작은 점 $q_{c,1}$과 두 번째로 작은 점 $q_{c,2}$를 관리합니다. 삼각형 $ABp$가 올바른 삼각형이 되기 위해서는, 모든 $q_{c,1}$은 삼각형 내부에, 모든 $q_{c,2}$는 삼각형 외부에 있어야 합니다.
이를 효율적으로 판별하기 위해서는 모든 $q_{c,1}$ 중 각 $\angle ABq_{c,1}$이 가장 큰 점과, 모든 $q_{c,2}$ 중 각 $\angle ABq_{c,2}$가 가장 작은 점을 빠르게 구할 수 있어야 합니다. 후자는 새로운 점 $q_{c,2}$가 나타날 때마다 각의 최솟값이 단조 감소하므로 각이 가장 작은 점 하나만 관리해도 됩니다. 하지만 $q_{c,1}$은 점이 집합에서 빠질 수도 있으므로 각의 최댓값이 단조 증가한다는 보장이 없습니다. 그러므로 std::set 등의 자료구조를 이용해 점을 관리해야 합니다.
따라서 점 $p$를 확인할 때마다, 삼각형 $ABp$가 올바른 삼각형인지 판별하기 위해 BBST에서 가장 큰 값을 구한 뒤 상수 번의 CCW 연산을 수행해야 하고, 이후 자료구조를 업데이트하기 위해 BBST에 원소 삽입/삭제 연산을 각각 최대 1번씩 해야 합니다.
BBST의 크기는 $k$ 이하이므로 점마다 $O(\log k)$ 만큼의 연산이 필요합니다. 선분 $\overline{AB}$가 고정되었을 때 $O(n \log k)$ 시간에 삼각형을 모두 볼 수 있으므로, 구현에 따라 전체 시간 복잡도는 $O(n^3 \log k)$ 또는 $O(n^3 \log n)$이 됩니다. 각 삼각형을 세 번씩 세었으므로 답을 출력할 때는 3으로 나눠서 출력해야 합니다.
실제로 코드로 구현할 때는 $A, B, p$도 삼각형 내부로 취급해야 하므로 약간의 처리가 필요합니다. 또한, $O(n^3 \log k)$ 풀이로 문제를 해결하기에는 시간 제한이 다소 빡빡합니다. 제 코드에는 아래와 같은 최적화가 포함되어 있습니다.
- BBST 대신 우선순위 큐 2개를 이용
- 각도 정렬은 $O(n^2)$번이 아닌 $O(n)$번만 수행한 뒤, 투 포인터를 이용해 선분 $\overline{AB}$ 왼쪽에 있는 점을 뽑음
- 선분 $\overline{AB}$ 에 대해 문제를 해결할 때, $B = (0, 0)$이 되도록 만들어서 CCW 계산해서 뺄셈 횟수를 5번에서 1번으로 줄임
또는 bitset을 이용한 $O(n^4 / w)$ 풀이도 가능합니다.
2021년 예선 L번, 2022년 본선 C번 과 비슷한 유형의 각도 정렬 스위핑 문제입니다.
1 | |
F. Erin Needs Cake
쿼리 횟수 제한에서 이분 탐색은 쉽게 떠올릴 수 있습니다. 이분 탐색을 하기 위해서는, 모든 prefix가 구멍 없는 단순 다각형이 되도록 삼각형의 순서를 잘 정해야 합니다. 설명의 편의를 위해 삼각형의 꼭짓점 순서가 반시계 방향이 되도록 정렬하고 생각합시다.
다각형의 중심(?)에서 시작해서 하나씩 확장해 나가며 prefix를 구하는 것은 어려워 보이니, 반대로 삼각형을 하나씩 떼어내는 식으로 접근해 봅시다. outer face를 제외한 dual graph의 관점에서 생각해 보면, outer face와 인접하면서 단절점(articulation point)이 아닌 정점을 제거하는 것이라고 생각할 수 있습니다.
조금 더 쉬운 버전인 interior vertex가 없는 문제를 먼저 해결해 봅시다. dual graph의 관점에서는 사이클이 없는 트리 형태에서 문제를 푸는 것이라고 생각할 수 있습니다. 이 경우에는 매번 리프 정점을 떼어내는 것으로 쉽게 해결할 수 있습니다. 기하의 관점에서는 두 변이 외부와 접한 삼각형이라고 생각할 수 있습니다.
다시 interior vertex가 있는 원래 문제로 넘어옵시다. 이 경우에는 차수가 1인 정점(2개 이상의 변이 외부와 인접한 삼각형)이 존재하지 않을 수 있습니다. 하지만 한 변이 외부와 인접하고, 마주 보는 꼭짓점이 interior vertex인 삼각형이 하나 이상 존재함을 증명할 수 있고, 그 삼각형을 떼어내면 됩니다.
삼각형의 제거 순서를 효율적으로 구하기 위해 아래 정보를 관리할 것입니다.
B[v][e]: 삼각형 $v$의 $e$번째 꼭짓점 ($0 \le e < 3$). 반시계 방향으로 정렬G[v][e]: 삼각형 $v$와 변 $e$를 공유하는 삼각형의 번호 ($0 \le e < 3$). 변 $e$는B[v][e]와B[v][(e+1)%3]연결OutPoint[p]: 점 $p$가 외부와 접하면 1, 접하지 않으면 0OutEdge[v]: 외부와 접한 삼각형 $v$의 변 개수Del[v]: 삼각형 $v$를 제거했으면 1, 제거하지 않았으면 0
OutEdge[v]가 1 이상인 삼각형은 잠재적으로 제거 후보가 될 수 있습니다. BFS와 비슷한 방식으로 후보를 큐에서 관리하면서, 만약 큐에서 꺼낸 삼각형 $v$를 제거할 수 있다면 제거하고, $v$를 제거함으로 인해 OutEdge 값이 증가한 삼각형을 다시 큐에 넣는 식으로 구현합니다. OutEdge값은 최대 3이므로 각 삼각형은 최대 3번 큐에 들어가고, 따라서 위의 BFS는 $O(n)$ 시간 안에 종료됩니다.
이제 남은 것은 쿼리로 보낼 점들의 순서를 정하는 것입니다. 쿼리에 보낼 삼각형을 모두 구했더라도 합집합의 경계를 따는 것은 또다른 일입니다.
삼각형 $v$가 뒤에서 $Pos[v]$번째에 제거됐고, 마지막으로 제거된 $m$개의 삼각형을 쿼리로 보내는 상황을 생각합시다. $Pos[v] \le m$ 이고 $Pos[G[v][e]] > m$ 이라면 $v$의 $e$번째 변은 쿼리에 포함되어야 합니다. 따라서 $B[v][e]$ 다음에는 $B[v][e+1\pmod 3]$이 와야 한다고 표시해 둡시다.
모든 필요한 꼭짓점에 대해 위와 같이 “다음 꼭짓점”을 구해놓으면, 처음으로 시작할 꼭짓점 하나만 알고 있어도 모든 꼭짓점을 순서대로 복원할 수 있습니다. 따라서 $k$번째 쿼리에서 사용할 점들의 목록과 순서를 $O(n)$ 시간에 구할 수 있습니다.
따라서 전체 시간 복잡도는 $O(n \log n)$입니다.
1 | |
C. Chemistry Experiment
포함 배제를 사용합니다. $1, 2, \cdots, m (\le k)$번 물질만 사용할 수 있고, 각 물질을 1개 이상 사용해야 한다는 제한이 없는 문제의 답을 $f(n, m)$이라고 정의합시다.
0과 1로 이루어진 이진 수열 중, 1로만 구성된 maximal 구간이 정확히 $r$개인 길이가 $n$인 수열의 개수는 $n+1 \choose 2r$입니다. 이후 $r$개의 구간에 $m$가지 종류의 수를 할당하면 되므로, $f(n, m) = \sum_{r=0}^{\lfloor (n+1)/2 \rfloor} {n+1\choose 2r}\cdot m^r$ 입니다.
$f(n, m)$의 점화식을 얻기 위해 짝수 항의 합 $A_n = \sum_r {n\choose 2r}m^r$과 홀수 항의 합 $B_n=\sum_r {n\choose 2r+1}m^r$을 정의합시다. ${n\choose r}={n-1\choose r}+{n-1\choose r-1}$ 이므로:
- $A_n = \sum_r {n-1\choose 2r}m^r + \sum_r {n-1\choose 2r-1}m^r = A_{n-1} + m\sum_r {n-1\choose 2(r-1)+1}m^{r-1}=A_{n-1}+mB_{n-1}$
- $B_n = \sum_r {n-1\choose 2r+1}m^r + \sum_r {n-1\choose 2r}m^r = A_{n-1}+B_{n-1}$
$A_n$가 선형 점화식일 것이라고 믿고 Berlekamp-Massey 알고리즘을 돌리면 $A_n=2A_{n-1}+(m-1)A_{n-2}$를 얻을 수 있습니다. 또는, 아래와 같이 식을 직접 전개해서 같은 결과를 얻을 수도 있습니다.
식을 한 칸씩 밀면:
- $A_{n-1}=A_{n-2}+mB_{n-2}$; 따라서 $mB_{n-2}=A_{n-1}-A_{n-2}$
- $B_{n-1}=A_{n-2}+B_{n-2}$
이를 대입하면:
- $A_n = A_{n-1} + mB_{n-1}$
- $A_n = A_{n-1} + m(A_{n-2} + B_{n-2})$
- $A_n = A_{n-1} + mA_{n-2} + mB_{n-2}$
- $A_n = A_{n-1} + mA_{n-2} + A_{n-1} - A_{n-2}$
- $A_n = 2A_{n-1} + (m-1)A_{n-2}$
$f(n,m)=A_{n+1}$이므로, $f(0,m)=1$, $f(1,m)=m+1$ 이고, $n \ge 2$ 이면 $f(n,m)=2f(n-1,m)+(m-1)f(n-2,m)$이 성립함을 알 수 있습니다.
위 점화식은 선형 점화식이므로, 아래와 같이 행렬을 이용하면 $f(n, m)$을 매번 $O(\log n)$ 시간에 계산할 수 있습니다.
$\begin{pmatrix}2&m-1\1&0\end{pmatrix}\begin{pmatrix}f(n-1,m)\f(n-2,m)\end{pmatrix}=\begin{pmatrix}f(n,m)\f(n-1,m)\end{pmatrix}$
$\begin{pmatrix}2&m-1\1&0\end{pmatrix}^{n-1}\begin{pmatrix}m+1\1\end{pmatrix}=\begin{pmatrix}f(n,m)\f(n-1,m)\end{pmatrix}$
원래 문제에서는 $k$개의 물질이 모두 한 번 이상 등장해야 하므로, 포함 배제의 원리를 이용하면 문제의 답을 $\sum_{m=0}^k (-1)^{k-m}\cdot{k\choose m}\cdot f(n, m)$ 으로 계산할 수 있습니다. $f(n, m)$은 $O(\log n)$ 시간에 계산할 수 있고, 이항 계수는 $O(k+\log p)$ 시간의 전처리 후에 매번 $O(1)$ 시간에 계산할 수 있습니다.
따라서 전체 시간 복잡도는 $O(k \log n)$ 입니다.
1 | |
H. Last Jump
연산을 어떻게 하더라도 $X$는 항상 $T$의 부분 문자열입니다. 또한, $T$에서 문자열 $X$가 처음으로 끝나는 위치를 $firstpos(X)$라고 정의하면, 항상 $i = firstpos(X)$가 됨을 증명할 수 있습니다.
문자열의 모든 부분 문자열을 표현하는 자료구조인 suffix automaton을 이용합니다. 플레이어가 $X$ 뒤에 $c$를 붙이는 것은 $X$를 나타내는 state에서 간선 $c$를 따라서 이동하는 것이라고 생각할 수 있습니다. 이때 $firstpos(Xc) = firstpos(X)+1$ 이면 일반 이동이고, $firstpos(Xc) > firstpos(X)+1$ 이면 점프입니다.
suffix automaton 은 정점이 $O(n)$개인 DAG 이므로 아래와 같은 DP를 이용해 문제를 해결할 수 있습니다:
- $D(v, 0):=$ 마지막에 내가 점프했고 현재 정점 $v$에 있을 때, 내가 이길 수 있으면 1, 이길 수 없으면 0
- $D(v, 1):=$ 마지막에 상대방이 점프했고 현재 정점 $v$에 있을 때, 내가 이길 수 있으면 1, 이길 수 없으면 0
만약 $v$에서 나가는 간선이 없다면($firstpos(v)=n$ 이면) $D(v,0)=1$, $D(v,1)=0$ 입니다. 그 외의 경우에는 일반적인 게임 이론 DP 문제와 같이 계산하면 되고, 아무도 점프하지 않는다면 선공의 승리이므로 문제의 정답은 $D(root, 0)$이 됩니다.
suffix automaton을 구축하고 각 state의 firstpos 값을 계산하는 것은 모두 $O(n\sigma)$ 시간에 수행할 수 있고, DP 계산 또한 $O(n\sigma)$ 시간에 할 수 있습니다. 따라서 전체 시간 복잡도는 $O(n\sigma)$ 입니다.
1 | |