문제 목록
12일 동안 푼 60문제 중 12문제를 골라서 풀이를 작성합니다.
BOJ 16243 Teoreticar
이분 그래프 $G=(L\cup R,E)$가 주어진다. 최소 간선 채색 수를 $OPT$라고 할 때, $2^{\lceil \log_2 OPT\rceil}$개 이하의 색을 이용해 간선을 색칠하는 문제
$L,R \leq 100\,000;$ $M\leq500\,000$
그래프의 간선 채색 수는 차수의 최댓값보다 작을 수 없고, 이분 그래프에서는 홀의 결혼 정리를 이용하면 항상 차수의 최댓값 만큼의 색으로 간선을 칠할 수 있음을 보일 수 있습니다. 즉, $OPT = \max \text{deg}(v)$입니다.
문제 제한에서 $\log_2 OPT$ 같은 게 보이니 분할 정복을 생각해 봅시다. 구체적으로, 모든 간선의 색을 구하기 위해 깊이가 최대 $\lceil \log_2 OPT \rceil$인 분할 정복을 하면서, 매번 간선 집합을 크기가 절반 두 개의 집합으로 분할한 다음 두 집합을 서로 다른 색으로 칠할 것입니다. 깊이가 $d$인 분할 정복 과정에서 한쪽 집합은 $2^d$를 나타내는 비트를 끄고 다른 집합은 $2^d$를 나타내는 비트를 켜는 것이라고 생각해도 됩니다.
같은 정점을 공유하는 간선이 없도록 간선 집합을 분할해야 하는데, 이건 그래프의 오일러 투어를 구한 다음 홀수 번째 간선과 짝수 번째 간선으로 나누면 쉽게 처리할 수 있습니다. 오일러 투어는 간선 개수에 비례하는 시간에 구할 수 있으므로 시간 복잡도는 $T(M)=2T(M/2)+O(M)=O(M \log M)$이 됩니다.
BOJ 16242 Strah
.과#으로 구성된 $N\times M$ 크기의 격자가 주어진다. 격자의 각 칸마다, 그 점을 포함하면서.으로만 구성된 직사각형의 개수를 모두 더한 값을 구하는 문제
$N,M \leq 2\,000$
각 점을 포함하는 직사각형의 개수를 세는 것은 결국 만들 수 있는 모든 직사각형의 넓이를 더하는 것과 같습니다. 직사각형의 넓이로 보는 편이 히스토그램과 같은 전형적인 테크닉을 적용하기 편하므로 넓이의 합을 구하는 문제라고 생각합시다. 이 문제는 스택을 사용해서 해결할 수도 있지만, 정리해야 할 게 많은 것 같아서 시간 복잡도에 $\log M$이 붙는 대신 식 정리가 조금 더 간단해 보이는 분할 정복을 사용했습니다.
문제를 본격적으로 풀기에 앞서, $A(i,j)$에서 출발해 #을 만나지 않고 올라갈 수 있는 최대 길이를 $H(i, j)$라고 정의합시다. 간단한 점화식을 이용해 $O(NM)$ 시간에 모두 계산할 수 있습니다.
이제 직사각형의 밑변이 될 행을 고정한 다음, 각 행에 대해 $O(M \log M)$에 해결할 것입니다. $m$번째 막대를 조금이라도 포함하는 모든 직사각형의 넓이를 구하는 방식으로 진행합니다. $l$번째 막대부터 $r$번째 막대만 고려했을 때, $m = \lfloor (l+r)/2 \rfloor$번째 막대를 지나는 모든 직사각형의 넓이를 $O(r-l)$ 시간에 구할 수 있다면 각 행을 $O(M \log M)$에 처리할 수 있습니다.
직사각형의 왼쪽 변의 위치 $s$와 오른쪽 변의 위치 $e$ ($l \leq s \leq m \leq e \leq r$)를 선택해서 만들 수 있는 직사각형의 최대 높이 $f(s,e)$를 생각해 봅시다. $f(s, e) = \min\left{H(i,s),H(i,s+1),\cdots,H(e)\right}$이므로 $[l,r]$ 구간에서 나올 수 있는 서로 다른 $f(s,e)$의 값은 최대 $O(r-l)$가지입니다. 그 높이를 각각 $h_1<h_2<\cdots$ 이라고 하고, $f(s,e) = h_k$를 만족하는 가장 큰 구간을 $[s_i,e_i]$라고 합시다. $s_i \leq s_{i+1} \leq e_{i+1} \leq e_i$를 만족한다는 것은 쉽게 알 수 있습니다. $s_i$와 $e_i$는 투 포인터를 이용해 $O(r-l)$ 시간에 구할 수 있습니다.
이제, 높이가 작은 것부터 차례대로 처리합시다. 즉, $m$번째 막대를 지나면서 높이가 $(h_{i-1}, h_i]$인 직사각형의 넓이의 합을 구할 것이고, 다음과 같은 식을 계산하면 됩니다.
\[\displaystyle \sum_{h=h_{i-1}}^{h_i}\sum_{x=s_i}^{m}\sum_{y=m}^{e_i} h(y-x+1)\]이 식은 열심히 전개하면 $S(h_{i-1},h_i) \times \left{ L(s_i,m)S(m,e_i) + L(m,e_i)S(s_i,m) + L(s_i,m)L(m,e_i) \right}$가 되고, 이는 상수 시간에 계산할 수 있습니다. (단, $L(a,b)=b-a+1,S(a,b)=(a+b)(b-a+1)/2$)
따라서 $m$을 지나는 모든 직사각형의 넓이의 합을 $O(r-l)$ 시간에 해결할 수 있고, 각 행을 $O(M \log M)$ 시간에 처리할 수 있으므로 전체 문제를 $O(NM \log M)$ 시간에 해결할 수 있습니다.
BOJ 24276 Circle
원의 둘레를 따라 $N$개의 정점이 있고, 정점들은 시계 방향으로 $1$부터 $N$까지의 번호가 매겨져 있다. $M$개의 간선이 주어지는데, 간선은 정점을 제외한 곳에서 교차하지 않는다. 최소 개수의 색으로 그래프의 정점을 칠하는 문제
$2 \leq N \leq 5\times 10^5;$ $1 \leq M \leq 5\times 10^5$
색깔은 얼마나 많이 필요할까요? 일단 간선이 서로 교차하지 않는 평면 그래프이므로 4개 이하의 색으로 칠할 수 있음은 쉽게 알 수 있습니다. 조금 더 생각해 보면, 문제의 조건을 충족한 채로 간선을 더이상 추가하지 못하는 상황인 그래프는 볼록 다각형의 삼각분할 형태일 것이고, 바깥에 있는 삼각형부터 하나씩 떼어낸다고 생각하면 3개의 색으로 칠할 수 있다는 것을 알 수 있습니다.
실제로 3개의 색으로 칠하는 방법도 이러한 관점에서 생각하는 것이 편합니다. 삼각형을 하나씩 떼어낸다는 것은 차수가 2인 점을 녹여서 두 간선을 병합하는 것이라고 생각할 수 있습니다. 따라서 위상 정렬과 비슷하게 degree가 2인 정점을 하나씩 제거한 다음, 제거된 순서의 역순으로 색칠할 수 있는 가장 작은 번호의 색으로 색칠하면 됩니다.
2개의 색으로 칠할 수 있는 이분 그래프만 예외처리하면 어렵지 않게 문제를 해결할 수 있습니다.
사실 문제에서 주어지는 그래프는 outer planar graph이므로 treewidth가 2 이하이기 때문에 항상 3개 이하의 색으로 칠할 수 있음을 바로 보일 수도 있습니다. 삼각형을 떼어내는 것은 chordal graph의 perfect elimination ordering을 구하는 것, degree가 2인 정점을 녹이는 것은 treewidth가 2인 그래프의 tree decomposition을 구하는 것과 비슷한 느낌이라서 그래프 관련해서 다양한 개념을 공부했다면 자연스럽게 떠올릴 수 있는데… 푼 사람이 많은 걸 보면 몰라도 전혀 상관 없는 것 같습니다.
BOJ 11776 NEKAMELEONI
$1\ldots K$ 범위의 원소로 구성된 배열 $A[1\ldots N]$이 주어진다. 배열의 값을 변경하는 쿼리가 주어질 때마다 $1\ldots K$를 모두 포함하는 가장 작은 구간의 크기를 구하는 문제
$N,Q\leq 100\,000;$ $K \leq 50$
$K$가 50 이하로 매우 작다는 것에 주목합시다. 구간 합의 최댓값을 관리하는 세그먼트 트리처럼 구간에 대한 정보를 적당히 저장해서 문제를 해결할 수 있습니다.
세그먼트 트리의 각 정점에서는 (1) 정점이 담당하는 구간에서의 최소 길이, (2) 구간의 앞에서부터 원소를 누적했을 때 집합의 크기가 증가하는 위치와 그 집합, (3) 뒤에서부터 누적했을 때 집합의 크기가 증가하는 위치와 그 집합, 이렇게 세 가지 정보를 저장합니다. 원소의 종류는 $K$가지밖에 없으므로 2와 3의 크기는 공집합을 포함해서 최대 $K+1$입니다.
두 정점의 값을 합치는 것은 대충 구현하면 $O(K^2)$에 구현할 수 있고, 투 포인터를 이용하면 $O(K)$에 구현할 수 있습니다. 따라서 전체 문제를 $O(NK+KQ\log N)$에 해결할 수 있습니다.
BOJ 16904 집합과 쿼리
집합에 양의 정수를 추가하는 쿼리와 제거하는 쿼리가 주어진다. 쿼리를 수행할 때마다 모든 원소를 XOR한 값이 최대인 부분 집합을 찾는 문제
$N \leq 500\,000;$ $1 \leq x \leq 2\times 10^9;$ 오프라인 가능
오프라인 동적 연결성과 같은 방식으로 분할 정복을 이용해 해결할 수 있습니다. basis의 크기는 30 이하이므로 굳이 롤백 연산을 구현할 필요 없이, 단순히 재귀 호출할 때 basis 배열을 call by value 방식으로 넘겨도 충분합니다. 따라서 원소가 삭제되는 상황에서 xor basis를 관리할 필요는 없고, 원소가 추가되는 상황만 고려해도 문제를 해결할 수 있습니다.
코드: http://boj.kr/5f07eaa12e89438e9d2fdfd45d62da58
BOJ 13946 Bipartite Blanket
정점에 가중치가 있는 이분 그래프 $G=(L\cup R,E)$가 주어진다. 가중치의 합이 $T$ 이상이면서 완전 매칭이 존재하는 정점 집합 $V\subseteq L\cup R$의 개수를 구하는 문제
$L,R\leq 20;$ $T \leq 4\times 10^8$
두 정점 집합 $A\subset L,B\subset R$가 주어졌을 때, $A$의 모든 정점을 포함하는 매칭이 존재할 필요 충분 조건은 모든 $a\subset A$에 대해 $\vert a\vert \leq \vert N(a)\vert$입니다(홀의 결혼 정리). 이 정리를 이용하면, 완전 매칭이 존재할 정점 집합 $V$는 홀의 정리에서 제시한 조건을 만족하는 $A\subset L$과 $B\subset R$의 합집합입니다. 조건을 만족하는 $A, B$는 $O(n2^n+m2^m)$ 시간에 구할 수 있습니다. 가중치의 합이 $T$ 이상인 쌍은 정렬한 다음 투 포인터를 이용해 쉽게 찾을 수 있습니다.
BOJ 8177 Ice Skates
발 사이즈가 $r$인 사람은 크기가 $r$ 이상 $r+D$ 이하인 스케이트화를 신을 수 있다. 크기가 $1, 2, \cdots, N$인 스케이트화가 각각 $K$개씩 있을 때, 사람이 추가/제거되는 쿼리가 $Q$번 주어질 때마다모든 사람이 스케이트화를 신을 수 있는지 판별하는 문제
$D < N \leq 200\,000;$ $M \leq 500\,000;$ $K\leq 10^9$
홀의 정리를 사용하면 될 것처럼 생겼습니다. 발 사이즈가 $i$인 사람의 수를 $C_i$라고 하면, 모든 $1 \leq l \leq r \leq N-D$에 대해 $A_l+A_{l+1}+\cdots A+r \leq K(r-l+1+D)$를 만족하는지 확인하면 됩니다. 식을 변형하면 $\sum_{i=l}^r A_i-K \leq KD$가 되고, 이는 $A_i-K$의 부분 합의 최댓값이 $K\times D$보다 작은지 확인하는 것과 같습니다. 따라서 부분 합의 최댓값을 관리하는 세그먼트 트리, 흔히 금광 세그라고 부르는 자료구조를 이용하면 $O(N+Q\log N)$ 시간에 문제를 해결할 수 있습니다.
BOJ 4223 Mummy Madness
당신과 $N$명의 미라들은 격자 위에서 턴을 주고 받으며 술래잡기를 한다. 당신이 먼저 턴을 갖는데, 인접한 8개의 칸 중 하나로 이동하거나 가만히 있을 수 있다. 그 다음에 $N$명의 미라가 모두 이동하는데, 미라는 단순히 당신과 유클리드 거리가 최소가 되는 인접한 사각형으로 이동한다. 최선을 다해 미라를 피해다닌다고 할 때, 몇 턴이 지난 후에 미라에게 잡히게 되는지 구하는 문제
$N \leq 10^5;$ $-10^6 \leq x_i,y_i \leq 10^6$
각 개체가 $k$턴 동안 이동할 수 있는 범위는 한 변의 길이가 $2k+1$인 정사각형이라고 생각할 수 있습니다. 로봇은 항상 가까워지는 방향으로 움직이기 때문에 최선을 다한다고 생각할 수 있고, 따라서 플레이어가 미라의 이동 가능 범위로 들어가면 무조건 $k$턴 안에 잡히게 됩니다.
따라서 $k$턴 안에 잡히는지 확인하는 결정 문제를 해결하는 파라메트릭 서치를 생각할 수 있습니다. 결정 문제의 파라미터로 $k$가 주어지면, 각 미라를 중심으로 하는 한 변의 길이가 $2k+1$인 정사각형들의 합집합이 플레이어를 중심으로 하는 정사각형을 모두 커버하는지 확인하면 됩니다. 이러한 결정 문제는 미라의 이동 범위와 플레이어의 이동 범위의 교집합인 직사각형의 합집합의 넓이가 $(2k+1)^2$인지 확인하는 것으로 해결할 수 있고, 직사각형 합집합의 넓이를 구하는 것은 $O(N \log N)$에 할 수 있음이 잘 알려져 있습니다.
결정 문제를 $O(N \log N)$ 시간에 해결할 수 있으므로 전체 문제를 $O(N \log N \log X)$에 해결할 수 있습니다.
BOJ 17512 Gosu 2
서로 다른 두 정점 사이에 정확히 한 개의 간선이 존재하는 방향 그래프(토너먼트 그래프)가 주어진다. 모든 $i < j$에 대해, $S_i$에서 $S_j$로 가는 간선이 있는 정점들의 나열 $S_1, S_2, \cdots, S_{1 + \lfloor \log_2 N \rfloor}$를 구하는 문제
$N \leq 512$
편의상 $K = 1 + \lfloor \log_2 N \rfloor$라고 합시다. $S_1$은 체인에 속한 모든 정점 $S_2, S_3, \cdots, S_K$로 가는 간선이 있어야 합니다. 마찬가지로 $S_2$는 $S_1$을 제외한 모든 정점 $S_3,\cdots, S_K$로 가는 간선이 있어야 하고, $S_3$은 $S_1,S_2$를 제외한 모든 정점으로 가는 간선이 있어야 합니다. 앞에 있는 정점부터 차례대로 하나씩 구해 봅시다.
out-degree가 가장 큰 정점을 생각해 보면, 이 정점의 out-degree는 항상 $(N-1)/2$ 이상이라는 것을 알 수 있습니다. 그러한 정점을 $S_1$으로 둔 다음, $S_1$에서 바로 갈 수 없는 정점을 제거합시다. 그래프에는 $N/2$ 이상의 정점이 남아있는 상태입니다.
이제 다시 out-degree가 가장 큰 정점 $S_2$를 선택합시다. 이 정점의 out-degree는 $N/4$ 이상이고, $S_1$에서 갈 수 없는 정점을 모두 제거했기 때문에 $S_2$에서 한 번에 갈 수 있는 정점은 $S_1$에서도 한 번에 갈 수 있습니다. 따라서 그 정점을 $S_2$로 둘 수 있습니다.
이런 식으로 체인의 앞에서부터 정점을 하나씩 확정짓고 필요없는 정점을 제거하더라도, 절반 이상의 정점은 살아남기 때문에 $1+\lfloor \log_2 N\rfloor$개의 정점을 찾을 수 있습니다.
BOJ 20608 Dynamic Convex Hull
사차 함수 $f_i(x)=(x-a_i)^4+b$를 추가하는 쿼리, 함수 $f_i$를 삭제하는 쿼리, $x$가 주어지면 $\max f_i(x)$를 구하는 쿼리까지, 총 3가지 쿼리를 오프라인으로 처리하는 문제
$Q \leq 2\times 10^5;$ $1 \leq a,x \leq 5\times 10^4;$ $1 \leq b \leq 10^{18}$
주어지는 모든 함수는 $y=x^4$를 평행이동시킨 것이므로 서로 다른 두 함수 간의 교점은 최대 1개만 존재합니다. 따라서 리차오 트리에서 가장 마지막에 삽입된 함수를 제거하는 기능을 구현한 다음, 오프라인 동적 연결성 문제처럼 분할정복을 하면 $O(Q \log Q \log X)$ 정도에 문제를 해결할 수 있습니다.
BOJ 4815 Wealthy Family
정점에 가중치가 있는 rooted tree가 주어진다. 조상-자손 관계인 정점들이 선택되지 않도록 정확히 $K$개의 정점을 선택할 때, 가능한 가중치 합의 최댓값을 구하는 문제
$N \leq 150\,000;$ $K \leq 300;$ $A_i \leq 1\,000$
간단한 트리 DP 문제입니다. $D(v, k) := $ $v$를 루트로 하는 서브 트리에서 정점을 $k$개 선택했을 때의 가중치 최댓값이라고 정의하면, 크기가 $S_a,S_b$인 두 트리의 DP 값을 합치는데 $O(\min\left{S_a,K\right} \times \min\left{S_b,K\right})$ 만큼의 시간이 걸려서 전체 시간 복잡도는 $O(NK^2)$이 되어서 시간 초과를 받을 것 같지만… 사실은 $O(NK)$라서 문제를 풀 수 있습니다. KOI 19 고등부 3번 검은 돌 문제와 비슷한 원리로 시간 복잡도가 보장됩니다.
BOJ 12456 모닝커피 (Large)
수행하는데 1초가 걸리는 작업이 $N$가지 있다. $i$번째 작업은 최대 $c_i$번 할 수 있으며 한 번 수행할 때마다 $s_i$ 만큼의 돈을 얻을 수 있고, $t_i$초 이후에는 수행할 수 없다. $K$초 동안 작업을 수행하려고 할 때, 얻을 수 있는 최대 이득을 구하는 문제
$N \leq 100;$ $1 \leq c_i,t_i \leq K \leq 10^{12};$ $1 \leq s_i \leq 1000$
마감 시간이 있는 단위 시간 작업 스케줄링 문제는 매트로이드 구조이므로 가중치가 큰 작업부터 최대한 많이 수행하는 방식의 그리디를 이용해 문제를 해결할 수 있습니다. 같은 작업이 최대 $10^{12}$개 존재하므로 각 작업을 수행할 구간을 관리해야 하며, 작업의 종류는 최대 100가지로 많지 않기 때문에 효율적으로 구현할 필요는 없습니다.