POI 2012/2013 (~Platinum) 풀이 및 후기

Wed Oct 04 2023

solved.ac 기준 플래티넘 아래쪽 문제들을 랜플디처럼 돌았다. 순서는 백준 문제 번호 순이다. (사실 그게 대회에서의 문제 순서지만)

Taxis

관찰 1. 이분 탐색이 가능하고, $k$개의 택시를 타야 한다면 연료가 가장 많은 $k$개를 고르는 게 이득이다.

관찰 2. 연료가 많은 택시부터 타서 최대한 오른쪽으로 이동해야 한다. 왜냐하면 차고지가 목적지보다 더 가까운 시점에는 택시가 승객을 태우러 갔다가 오는 과정 2번이 필요하기 때문이다. 예제에서 27로 이동 후 30으로 이동하면 최대 15 위치에 놓일 수 있는데, 30을 먼저 타고 27로 이동하면 18로 이동할 수 있음을 확인해보자. 그러므로 exchange argument로 설명해도 된다.

Take-out

문제를 잘못 해석해서 거의 두 시간이 사라졌다. 양 끝에서만 b나 c를 제거할 수 있다고 생각했는데, 밑에 있는 그림을 보니 그게 아니라는 걸 깨달았다. 사실 문제를 읽으면서 그림을 같이 보긴 했는데, 그 그림을 보고 지문을 다시 읽었는데도 맞는 해석을 못 했다. 예제 출력이 너무 강력해서 긴가민가했다. 양 끝에서만 빼는 게 아니라면 사실 문제는 쉽다. $k=1$이면 괄호 문자열과 비슷한 꼴이고, 얼마 전 개최된 SNUPC 2023의 문자열 만들기과도 결이 비슷하다. 그러므로 임의의 조건을 만족하는 문자열은 전부 해가 있을 것으로 추정할 수 있다. 문자들을 순서대로 스택에 담는데, b를 $1$, c를 $-k$로 치환하여 넣고, 스택의 마지막 $k+1$개 숫자의 합이 0인지 늘 체크하고 있으면 된다. stack을 기반으로 하므로 prefix sum은 dynamic하게 $O(1)$에 관리가 가능하다.

해가 존재한다는 조건을 활용하면 이 풀이의 정당성에 대한 증명이 가능하다. 마지막 operation은 항상 초기 상태에서 인접해있는 $k+1$개의 문자를 제거하는 것이다. 이것을 초기 상태에서 제거한 $n-k-1$ 길이의 문자열을 생각하면, 여기서 시행할 수 있는 operation들은 제거된 문자와 완전히 독립적이다. 그러므로 귀납법을 적용하면, 스택에서 늘 맨 위의 $k+1$개를 보는 것만으로 모든 해를 찾을 수 있음을 알 수 있다.

Triumphal arch

상황이 재밌는 문제다.

관찰 1. 이분 탐색이 가능하다. Parameter를 $k$라고 하자.

관찰 2. 왕이 어디로 움직이더라도 $k$개씩 정점을 덮어서 항상 왕이 덮인 정점만 밟게 하는 게임이라고 생각하자. 즉 왕이 어떤 도시로 직진하는 상황만 고려하면 된다. 그러므로 왕이 어떤 subtree에 도착하면, 그 외부는 고려할 필요가 없어진다. 중간에 경로를 바꾸는 건 항상 왕에게 손해.

관찰 3. 정점은 원하는 대로 미리 덮어둘 수 있으므로, 왕이 subtree 내부에 도착했을 때 고려해야 하는 유일한 인자는 그 subtree에서 이미 덮여 있는 정점의 수이다.

관찰 4. 반대로 어떤 subtree 입장에서, 왕이 들어오는 시점에 $l$개의 정점이 이미 덮여있다고 하자. 왕이 덮인 정점만 방문하기 위한 $l$ 또한 이분 탐색이 가능한 구조이다.

실제로 이분 탐색을 하겠다는 의미는 아니고, 이제 저 값을 dp로 관리하면 된다. $dp[u]$를 subtree $u$에 진입할 시점에 필요한 덮인 정점의 최소 개수라고 하자. 그러면 $u$는 이번 턴에 $k$개를 추가로 덮으면서, 모든 children이 요구하는 개수만큼 각 subtree를 덮고 children들도 덮어놔야 한다. 따라서 $$ dp[u] \geq \sum_{v \in child(u)} dp[v] + \vert child(u) \vert - k $$가 성립한다. 정의 상 항상 $dp[u] \geq 0$임에 유의하라.

Tales of seafaring

이제는 너무 웰노운이 되어버린 유형이다. 만약 $s$에서 $t$로 $d$번에 걸쳐 이동이 가능하다면, $d+2, d+4, \cdots$번에 걸쳐서도 이동이 가능하다. 그러므로 bfs를 돌면서 어떤 정점까지의 '최단 홀수 거리', '최단 짝수 거리'를 구하면 된다. $n$이 작아서 모든 출발점에 대해서 일일이 bfs를 돌릴 수 있다. 유의사항은 2가지로, online으로 처리하려면 메모리 제한 때문에 int 대신 short형을 써야 한다는 점이고, 크기가 1인 component는 $d+2$가 가능하다는 논리가 성립하지 않음에 주의. 실제로 이것 때문에 제대로 맞왜틀 지옥에 빠졌었다.

Tower Defense Game

POI스러운 문제인 것 같다. NP-hard의 변형을 재밌게 포장해서 물어보는데, 요즘은 어떤 주류 대회에서도 이러지는 않는 것 같으나... 그냥 흥미롭다. 요약하면 Minimum dominating set의 cardinality가 $OPT$일 때, dominate의 정의를 범위 2만큼으로 바꿔서 생각할 때 $OPT$ 이하의 dominating set을 찾으라는 문제이다. 나는 이 문제를 풀면서 거의 생각이 정지해 있었다. 그런데 원래의 dominate의 정의에 집중하면 매우 쉽게 풀린다. 내가 아무 정점 $x$를 골랐을 때, 이웃한 정점 중 최소 하나는 minimum dominating set에 포함되어 있어야 한다. 이를 $y$라고 하자. 이 때 우리가 찾으려는 dominating set $A$에 $x$를 넣으면, 원래의 dominating set에서 $y$와 $y$에 이웃한 정점들 - 즉 $y$가 커버하고 있었던 정점들 - 을 이제는 범위가 2로 늘어났으므로 $x$가 전부 커버하게 된다. 따라서 아무 정점이나 고르고, 범위 2 이내의 정점을 그래프에서 제거하는 작업을 반복하기만 해도 바로 답이 된다! 즉 누군가 데이터를 뚫겠다고 코드를 짜면 그게 정해인 문제라고 할 수 있겠다.

난 이 문제의 데이터를 어떻게 만든 건지 궁금하다. Dominating set은 내가 아는 한 constant ratio approximation도 없는 걸로 알고 있는데, 아마 optimum을 따로 증명할 수 있는 특수한 형태의 그래프들을 넣어놨을 것 같다. 애초에 데이터가 강하다고 의미가 있긴 한 건지 싶은 문제이긴 하지만.

Bytecomputer

내가 이런 문제 유형에 꽤 약하다는 걸 다시금 깨달았다. 코포하면서 늘 느끼고 있긴 한데, 연습할 방법을 잘 모르겠다. if else를 열심히 더 넣어서 결국 자력솔 비슷한 걸 하긴 했는데, 최소한 확신이 생기는 정도의 풀이를 뽑지는 못 했다. 아래는 정해를 정리한 것이다.

초기 상태를 $\hat{x}_1, \hat{x}_2, \cdots, \hat{x}_n$로 따로 표기하겠다.

관찰 1. 최종 상태는 음수들의 연속, $0$들의 연속, 양수들의 연속 3가지로 쪼개서 볼 수 있다.

이제 각각의 블록이 만들어지는 방법을 분석하자. 우선 $\hat{x}_1 = x_1$이므로, 음수 블록이 존재한다면 무조건 $x_1 = -1$이다. 음수 블록 내부에 $\hat{x}_i = 0$인 $i$가 존재하면 최소 한 번은 값을 감소시켜야 하고, $\hat{x}_i = 1$이었다면 두 번 $-1$이 더해지거나, 아니면 $x_{i-1}$이 $-2$ 이하의 값을 가지게 된 후 $x_i$가 최소 한 번 감소되어야 한다. 이 때 $\hat{x}_1 = -1$로 변하지 않아야 하므로, 후자의 경우라면 $x_{i-1}$은 다시 $-1$ 이상으로 증가해야 한다. 따라서 음수 블록 내부에 있는 $0$과 $1$의 존재는 각각 1, 2회의 시행을 최소로 필요로 한다. 이 때 왼쪽부터 오른쪽으로 가면서 계속 $-1$을 옆 원소에 더하는 시행이 존재하므로, 음수 블록의 최적해는 가설을 만족한다.

양수 블록은 비슷하게 $x_n$에 먼저 주목한다. $x_n$은 커지면 커질 수록 이득이므로, $x_n$을 변화하는 operation은 전부 값을 증가시킨다고 보아도 되고, operation의 순서를 바꿔 $x_{n-1}$이 최대인 시점 직후에 진행된다고 봐도 다른 operation에 영향을 주지 않는다. 최종 상태에서 양수 블록의 길이가 2 이상이라고 하자. 다음과 같이 최적해에 성질을 하나 더 부여할 수 있다. 만약 $x_{n-1}$의 값을 감소시키는 시행이 존재한다면, 감소시키는 모든 시행을 제거하고 대신 $x_n$ += $x_{n-1}$ 시행을 하나 끼워넣는다. 그러므로 시행의 길이가 최소한 길어지지는 않는다. 바뀐 시행에서 $x_n$이 $k+1$번 바뀌고, 모든 시행이 $x_{n-1}$의 값이 $M$으로 최대인 상황에서 일어났다고 하자. 엄밀히 말하면 $x_{n-1}$은 더 이상 값이 감소하지 않으므로, 시행을 끝마치면 $x_{n-1} = M \geq \hat{x}_{n-1}$이 된다.

$k = 0$이면 조작을 가하기 전 시행은 $\hat{x}_n = x_n$을 만족시켰을 것이므로, $x_n = 1$. 따라서 $x_n \geq 1+M > x_{n-1}$.
$k > 0$이면 $x_n = (k+1)M + \hat{x}_n \geq 2M-1 \geq M \geq \hat{x}_{n-1}$.

마지막으로 $0$ 블록에 대해 생각해보자. $x_z, x_{z+1}, \cdots, x_{z+l} \,$이 $0$ 블록이 된다고 하자. $\hat{x}_z = -1$이었으면 음수 블록으로 $x_z$를 편입시켜도 operation을 추가로 진행할 필요가 없으므로, $\hat{x}_z \geq 0$으로 두자. 만약 어떤 $k < l$에 대해 $\hat{x}_{z+k+1} \neq 0$이고, $\hat{x}_z$부터 $\hat{x}_{z+k}$까지는 모두 $0$이었다고 하자. 그러면 $x_{z+k+1}$을 변화시키기 위해서는 $x_{z+k}$의 값이 양수나 음수로 바뀌었다가 다시 $0$으로 돌아갔어야 하므로 최소 2번 시행이 필요하다. 이를 반복적으로 적용하면 최소 $2k+\hat{x}_z+1$번 시행이 필요하다. 그런데 음수 블록이 앞에 있었으면 $x_{z+k+1}$까지 $0$으로 바꿔버리는 게 $k+\hat{x}_z+1$번만 시행을 필요로 하므로, $k \geq 1$일 때는 항상 더 이득이다. 그러므로 $0$ 블록은 초기 상태부터 $0$이었어야 하거나, $k=0$일 때 $\hat{x}_z=1$인 위치만이 $0$ 블록이 될 수 있다.

음수 블록의 존재성 및 최적해는 $\hat{x}_1$에만 의존하고, $0$ 블록 또한 조건을 전부 파악했다. 따라서 양수 블록의 시작 지점에 대한 성질만 확인하면 된다. 양수 블록의 시작점 $x_j$가 $\hat{x}_j < 1$이었다고 가정하면, $x_{j-1} > 0$인 시점이 존재했었어야 한다. 그리고 언젠가는 $x_{j-1}$이 $0$ 이하로 감소했어야 하는데, 양수 블록의 논리를 다시 가져오면 $x_{j-1}$이 최댓값을 찍고 다시 감소하게 놔두는 대신 $x_j$를 증가시키는 연산 1번으로 대치해도 문제가 없다. 따라서 양수 블록의 시작점의 초기 상태를 1로 가정할 수 있다. 양수 블록의 위치가 결정되면, 블록 내의 원소를 non-decreasing하게 바꾸는 작업은 음수 블록과 동일.

결론은 $0$ 블록의 위치를 결정하고, 양수 블록의 시작 위치가 $1$인지 확인하면 prefix sum 등을 미리 계산해두어서 $0$ 블록의 후보군마다 $O(1)$ 시간에 계산이 가능하다. 초기 상태에서 연속한 $0$ 그룹은 아무리 많아야 $n$개일 것이므로, 앞에 $1$이 있느냐 마느냐를 생각하면 $0$ 블록의 후보군은 최대 $2n$개이다. 모든 증명이 끝난 후에야 따라나오는 결과 중 하나로는, 결국 최종 상태의 모든 수도 $-1, 0, 1$로만 구성되는 최적해가 존재한다는 것이다. 나는 이걸 먼저 추정했고, $\hat{x}_1 = x_1$이라는 사실로부터 case work를 진행해서 풀었다. $x_n$ 위치에서 경계 조건을 활용할 생각을 했어야 쉽게 풀었을 것 같다.

Colorful Chain

만들어야 하는 체인의 길이가 고정이므로, $O(n)$개의 체인만 보면 된다. Two pointer 느낌으로 접근하는 게 편하다. 어떤 시점에 내가 보고 있는 체인이 있을 텐데, $P_i$를 현재 체인에 $c_i$ 색깔이 정확히 $l_i$개 있으면 1, 아니면 0이라고 하자. (즉 Iversion bracket) 그러면 체인이 nice인 것은 모든 $P_i$의 합이 $m$인 것과 동치이다. Two pointer로 체인을 관리한다면 체인에서 새로운 색깔을 하나 넣거나 하나 빼는 작업만 이루어지므로, $P_i$의 변화가 최대 $O(1)$번 일어난다. 이를 잘 추적해주면 ok.

Laser

레이저가 원점에서부터 나오므로, 원점에 대해서 radial하게 선분들을 projection한다고 생각하면, 결국 선분의 위치가 주는 정보는 선분을 원점에서 바라보는 시야각에 대한 정보뿐이다. 다시 말하면 어떤 선분은 $[\theta_1, \theta_2]$의 시야각을 가진다. $(0 < \theta_1 \leq \theta_2 < \frac{\pi}{2})$ 그러므로 이 문제는 이제 선분들이 일직선 상에 주어져 있을 때의 상황으로 바뀐다. 레이저는 이제 $y$축에 평행한 방향으로, 어떤 $x$좌표에서 쏘아지게 되는 것이다. 레이저를 쏘는 순서는 상관이 없으므로, $x$좌표가 증가하는 방향으로 순서대로 쏜다고 하자. 좌표압축을 해 두면 선분들의 양 끝점은 모두 정수인 상태라고 하자.

즉 dp를 쓰기 적절한 꼴이므로, $dp[i][j] = $레이저를 $i$번 쐈고, 마지막으로 쏜 레이저의 $x$좌표가 $j$이하일 때 맞춘 선분 개수의 최댓값으로 정의하자. 우선 $j$가 정수여도 괜찮다는 보장은 아직 없다. 이런 문제는 보통 선분의 양 끝 점들에만 레이저를 쏴도 괜찮은 것이 보통인데, 이 문제는 그게 불가능하다. 어떤 선분의 끝점과 다른 선분의 시작점의 좌표가 같을 때 그러한 케이스가 발생한다. 다음의 예제는 최적해로 $x=7$을 포함한다.

예제

그러므로 선분의 양 끝점들을 짝수 좌표로만 압축하면, 홀수 좌표까지 dp에서 고려하는 것으로 문제가 해결될 수 있다. 이제 어떤 $x$좌표에서 레이저를 쐈을 때, 맞추게 되는 선분들의 개수 $c[x]$와 그 선분들 중 시작 지점의 최솟값들을 $s[x]$로 두면, dp 식을 다음과 같이 쓸 수 있다. $$ dp[i][x] = max(dp[i][x-1], dp[i-1][s[x]-1] + c[x]) $$

$c[x]$와 $s[x]$를 미리 전부 계산해두면 dp식은 $O(nk)$ 시간에 풀 수 있다. 나는 구간의 $(count, min)$를 관리하는 세그먼트 트리를 만들어서 $[a, b]$ 선분이 들어오면 $[a, b]$ 구간 업데이트를 해주는 방식을 썼다. 업데이트 이후 모든 칸에 대해 한 번씩 쿼리를 날리면 ok.