1차 2번(통신망), 2차 1번(총 쏘기), 2차 4번(가로등)은 아직 풀이가 준비되지 않았습니다.
풀이가 준비되지 않은 세 문제는 모두 Petrozavodsk Programming Camp Winter 2022에 사용되었으며, 영어로 된 만점 풀이는 캠프 에디토리얼에서 확인할 수 있습니다. 통신망은 Critical Vertex, 총 쏘기는 Two Bullets, 가로등은 Streetlights입니다.
1-1. 카드 뒤집기 게임 (백준 22026)
Subtask 3. $M \leq N \leq 1\,000$ (100점)
$0\cdots M-1$번째 행과 $0\cdots M-1$번째 열을 모두 카드에 그려진 패턴과 동일하게 만드는 방법은 유일합니다. 그러므로 $0\cdots M-1$번째 행과 열을 그리디하게 뒤집어서 카드에 그려진 패턴대로 만든 다음, 전체 격자의 카드와 패턴이 동일한지 확인하면 됩니다.
시간 복잡도는 $O(NM)$입니다.
1-2. 통신망 (백준 22027)
풀이 준비 중
1-3. 렉 (백준 22028)
Subtask 2. $M = 0$ (16점)
각 직사각형 $[x_1,x_2]\times[y_1,y_2]$에 대해 $(x_1,y_1), (x_2+1,y_2+1)$에 1을 더하고 $(x_2+1,y_1), (x_1,y_2+1)$에 -1을 더한 뒤 2차원 누적합을 구하면, $(x,y)$의 정답이 $(x,y)$에 저장됩니다. $x$좌표 순서대로 스위핑하면서 펜윅 트리를 이용해 $y$축의 누적합을 관리하면 $O((N+Q) \log X)$에 문제를 해결할 수 있습니다.
Subtask 4. 상하좌우 이동 (29점)
직사각형이 위로 이동하는 것만 생각해 봅시다. 구체적으로, $[x_1,x_2]\times[y_1,y_2]$가 $y$좌표가 증가하는 방향으로 $d$만큼 이동하는 상황을 가정하겠습니다.
Subtask 2처럼 2차원 누적합의 관점에서 생각하면, 위로 올라가는 것은 $(x_1,y_1+1\cdots y_1+d)$와 $(x_2+1,y_2+2\cdots y_2+d+1)$에 1을 더하고, $(x_2+1,y_1+1\cdots y_1+d)$와 $(x_1, y_2+2\cdots y_2+d+1)$에 -1을 더하는 것과 동일합니다. Subtask 2와 마찬가지로 $x$좌표 순서대로 스위핑을 하면서 $y$축의 누적합을 관리할 것입니다.
구간 $[s,e]$에 1을 더하고 누적합을 구하는 것은 $s, s+1, \cdots, e$에 $1, 2, \cdots, e-s+1$을 더하고, $e+1$ 이상인 지점에는 $e-s+1$을 더하는 것이라고 생각할 수 있습니다. 즉, 구간에 일차 함수를 더하는 것과 특정 값을 더하는 것으로 나눠서 생각할 수 있습니다. 펜윅 트리 2개를 이용해 할 수 있습니다.
아래로 이동하는 것은 뒤집어서 처리하면 되고, 좌우로 이동하는 것은 $x, y$좌표를 바꿔서 처리하면 됩니다. $O((N+M+Q)\log X)$에 해결할 수 있습니다.
Subtask 6. (100점)
$y=x$ 직선에 평행하게 이동하는 상황에서 $[1,Q_x]\times [1,Q_y]$ 영역의 합을 구하는 것은, 해당 영역에 포함되는 기울기가 1인 일차 함수들의 길이를 모두 더한 것이라고 생각할 수 있습니다. $x-y > Q_x-Q_y \textit{ and } x \leq Q_x$인 삼각형 영역(오른쪽 아래)과 $ x-y \leq Q_x-Q_y \textit{ and } y \leq Q_y$인 삼각형 영역(왼쪽 위)으로 나눠서 생각합시다.
$(x,y)$를 $(y-x,x)$로 변환하면 원래 오른쪽 아래 영역에 있던 점이 모두 점 $Q$의 왼쪽 아래로 이동합니다. 마찬가지로 $(x,y)$를 $(x-y,y)$로 변환하면 왼쪽 위 영역에 있던 점이 모두 점 $Q$의 왼쪽 아래로 이동합니다. 각각 $y-x$와 $x-y$ 순서대로 스위핑하면 Subtask 4와 동일한 방법으로 처리할 수 있습니다.
좌표 변환 과정은 아래 텍스트에서 I에 주목해보세요.
1 | |
$y=-x$ 직선에 평행하게 이동하는 것도 비슷하게 처리할 수 있습니다. $x+y \leq Q_x+Q_y \textit{ and }y\leq Q_y$인 사다리꼴 영역에서 $x+y\leq Q_x+Q_y \textit{ and } x > Q_x$인 삼각형 영역을 빼면 됩니다.
$(x,y)$를 $(x+y,y)$로 변환하면 사다리꼴 영역에 있던 점이 모두 점 $Q$의 왼쪽 아래로 이동하고, $(x+y,-x)$로 변환하면 삼각형 영역에 있던 점이 모두 $Q$의 왼쪽 아래로 이동합니다. 각각 $x+y$ 순서대로 스위핑하면 Subtask 4와 동일한 방법으로 처리할 수 있습니다.
좌표 변환 과정은 아래 텍스트에서 13에 주목해보세요.
1 | |
전체 시간 복잡도는 $O((N+M+Q)\log N)$입니다.
1-4. 철도 (백준 22029)
Subtask 2. $K = 1$ (17점)
트리에 간선을 하나 추가하면 사이클이 정확히 한 개 존재하는 그래프가 됩니다. 이렇게 만들어진 사이클과 추가된 가짜 간선을 빠르게 찾을 수 있어야 합니다.
사이클의 크기가 작을수록 고려해야 할 경우의 수가 적어지니까, 거리가 2인 두 정점을 가짜 간선으로 연결해서 크기가 3인 사이클을 만들어 봅시다. 가짜 간선으로 연결되지 않은 정점을 표시하면, 사이클에 속한 정점 중 표시되지 않은 두 정점을 연결한 간선이 가짜 간선입니다.
$N \leq 200$이므로 인접 행렬을 만든 다음 $O(N^3)$에 크기 3 사이클을 찾아도 충분합니다.
Subtask 4. 지름 $\leq N/2$ (46점)
정점 하나를 표시하는 것은 그 정점을 루트로 잡는 것이라고 생각할 수 있습니다. 트리에서 루트가 고정되어 있다면 DFS/BFS와 같은 그래프 순회를 통해 정점들의 순서를 붙일 수 있습니다.
특히 BFS를 이용하면 루트에서 각 정점 $v$까지 가는 거리 $D(v)$를 구할 수 있고, 일반적인 그래프에서 BFS 스패닝 트리에 속한 간선 $(u, v)$는 $\vert D(u) - D(v) \vert = 1$을 만족합니다. 즉, 아무 정점을 루트로 잡아서 BFS를 한 다음, 루트까지의 거리가 같은 정점들을 가짜 간선으로 연결하면 됩니다.
이 풀이를 제출하면 100점을 받아야 할 것 같지만 46점이 나옵니다. 왜 그런지는 Subtask 5 풀이에서 살펴봅시다.
Subtask 5. $N \leq 500$ (100점)
트리가 선형이고 루트를 끝에 있는 정점으로 잡으면 거리가 같은 정점이 존재하지 않기 때문에 문제를 해결할 수 없습니다. 반대로 말하면, 거리가 같은 정점쌍이 $\lfloor N/2\rfloor-1$개 이상 존재하도록 만드는 루트를 찾으면 됩니다.
여기까지 왔다면 다들 알겠지만 트리의 깊이를 $N/2$ 이하로 만들면 되고, 이는 지름의 중점이나 센트로이드를 루트로 잡으면 됩니다. 트리의 지름을 찾는 것과 센트로이드를 찾는 것 모두 선형 시간에 할 수 있기 때문에 $O(N)$에 문제를 해결할 수 있습니다.
사실 $N$의 크기가 작아서 모든 정점에 대해 시도해서 가짜 간선을 $K$개 만들 수 있는지 확인해도 됩니다.
2-1. 총 쏘기 (백준 22030)
풀이 준비 중
2-2. 회의실 (백준 22031)
Subtask 2. $K = 1$ (17점)
Interval Graph가 주어졌을 때, 선분을 몇 개 제거해서 모든 컴포넌트의 크기가 $K$ 이하가 되도록 만드는 문제입니다. 이때 제거하는 선분의 가중치의 합을 최소화해야 합니다.
$K = 1$이면 가중치가 있는 회의실 배정 문제이고, 끝점 기준으로 정렬한 뒤 DP를 하면 $O(N\log N)$에 해결할 수 있습니다. 회의실 배정 문제를 푼 다음, 전체 가중치 합에서 뺀 값을 출력하면 됩니다.
Subtask 4. $N \leq 250$ (53점)
끝점이 $i$ 이하인 선분들만 사용해서 만들 수 있는 가중치의 최댓값을 $D(i)$라고 정의합시다. 좌표 압축을 이용해 $i$의 범위를 $2N$으로 만들 수 있습니다.
끝점이 $i$ 이하인 선분들만 사용하는 것은 $j < i$인 $j$에 대해 $D(j)$를 구한 뒤, $(j, i]$ 구간에 완전히 포함되는 선분을 최대 $K$개 선책하는 것이라고 생각할 수 있습니다. 그러므로 $C(a,b)$를 $[a,b]$ 구간에 완전히 포함되는 최대 $K$개의 선분의 가중치 합이라고 정의하면 $D(i) = \max D_j + C(j+1,i)$입니다.
$C$ 배열은 $O(N^3)$에 모두 만들 수 있고 점화식은 $O(N^2)$에 계산할 수 있으므로 전체 시간 복잡도는 $O(N^3)$입니다.
Subtask 5. $N \leq 2\,500$ (150점)
점화식을 계산하는 것 자체는 이미 $O(N^2)$으로 충분히 빠르기 때문에, $C$를 전처리하는 과정을 최적화해야 합니다. $i$를 고정하고 $j$를 증가시키면서 $C(i, j)$를 구할 때, 선분이 추가되는 상황에서 가장 큰 $K$개를 관리하는 것은 최소 힙을 이용해 수행할 수 있습니다. 즉, $C(i,\ast)$를 계산할 때 $O(N \log N)$이 걸리므로 $C$ 배열 전체를 모두 전처리하는 것은 $O(N^2 \log N)$ 시간에 할 수 있습니다.
점화식은 $O(N^2)$에 계산할 수 있으므로 전체 시간 복잡도는 $O(N^2 \log N)$입니다.
2-3. 원숭이 (백준 22032)
Subtask 2. $M \leq 5\,000$ (53점)
원숭이가 잡을 수 있는 손잡이 쌍 $(x, y)$를 오름차순으로 정렬하면, 원숭이가 이동하는 경로는 정렬된 배열에서 인덱스가 증가하는 형태로 나타납니다. 그러므로 P 배열을 정렬합시다.
$D(i)$를 $i$번째 순서쌍까지 도달했을 때 먹을 수 있는 바나나의 최대 개수라고 정의하면, $j < i$이면서 $x_j = x_i$인 $j$에 대해 $D(i) \leftarrow D(j) + B_{y_i}$이고, $y_j = y_i$인 $j$에 대해 $D(i) \leftarrow D(j) + A_{x_i}$입니다. 점화식을 $O(N^2)$에 계산할 수 있습니다.
Subtask 3. $N,M \leq 500\,000$ (150점)
Subtask 2에서 세운 점화식을 $O(N^2)$보다 빠르게 계산해야 합니다.
$i$번째 순서쌍까지 고려했을 때, 마지막에 잡은 기둥 A의 손잡이가 $x$이면서 먹을 수 있는 바나나의 최대 개수를 $L(i,x)$, 마지막에 잡은 기둥 B의 손잡이가 $y$이면서 먹을 수 있는 바나나의 최대 개수를 $R(i,y)$라고 정의합시다.
점화식은 $D(i) = \max\lbrace A_x + B_y, L(i-1,x)+B_y, A_x+R(i-1,y) \rbrace$, $L(i,x)\leftarrow L(i-1,x)+D(i)$, $R(i,y) \leftarrow R(i-1,y)+D(i)$입니다.
$L(i-1,\ast)$에서 $L(i,\ast)$로 전이할 때 값이 바뀌는 위치는 $x_i$ 밖에 없으므로 메모리를 $O(N)$만 사용할 수 있습니다. 마찬가지로 $R$ 배열도 메모리를 $O(N)$만 사용해서 표현할 수 있습니다.
P 배열을 정렬하는데 $O(M \log M)$이 걸리고, $D, L, R$ 배열을 계산하는 것은 $O(N)$이 걸리므로, 전체 시간 복잡도는 $O(N+M\log M)$입니다.
2-4. 가로등 (백준 22033)
풀이 준비 중