Algorithmic Engagements 2021. Koszulki

수열을 역순으로 정렬한 후 값이 $a_k$ 이상인 수를 출력하면 됩니다.

POI 2019/2020. Najmniejsza wspólna wielokrotność

최소공배수가 $R - L$ 에 대해 지수적으로 커져서 탐색해야 할 쌍이 많지 않다는 사실을 사용합니다.

$R - L = 1$ 인 경우, 최소공배수는 그냥 두 수의 곱입니다. $X(X+1) = M$ 을 만족하는 $X$ 가 존재한다면, $X, X + 1$ 을 출력하면 됩니다. 이 경우는 따로 처리합니다. 이차 방정식을 풀거나 이분 탐색을 하시면 됩니다.

$R - L \geq 2$ 인 경우, 최소공배수는 적어도 $L(L+1)(L+2) / 2$ 이상입니다. 고로, $L \leq 2 \times 10^6$ 을 만족합니다. $1 \le L \le 2\times 10^6$ 인 모든 $L$ 에 대해, $lcm(L, L + 1, \ldots, R)$ 이 $10^{18}$ 이하일 때까지 $R$ 을 증가시키면서 답이 되는 모든 쌍을 전처리해둘 수 있습니다. 이렇게 구한 쌍들은 std::map 등에 저장한 후, 쿼리가 들어올때마다 출력해 주면 됩니다.

시간 복잡도를 정확히 예측하기는 어렵지만, $L \log L$ 정도일 거라고 생각할 수 있습니다. 결국 전처리를 하는 부분이 오래 걸리니, 직접 짜 보고 확인해 보시면 됩니다. 실제로 짜 보면 1초 정도에 전처리가 완료됩니다.

계산하는 과정에서 $x \times y$ 가 long long을 넘어갈 수 있음에 유의하는 게 좋습니다. __int128 을 쓰거나, 아니면 if((double) x * y > 2e18) return 2e18 같은 식으로 overflow check를 하면 됩니다.

PA 2021. Autostrada

당연하게도, 앞에 차가 없다면 항상 $v_0$ 의 속도로 달리고, 그렇지 않을 때는 앞의 차의 속도를 맞춰서 달리는 것이 최적입니다.

여러 방법으로 해결할 수 있는 문제이지만, 이런 관찰을 하면 유용합니다: 만약 현재 속도가 $v_0$ 일 때 2차선으로 갈 수 있는 기회가 있다면, 무조건 2차선으로 가는 것이 이득입니다. 이유는 단순하게, 1차선이나 3차선에서 $v_0$ 으로 달리고 있는데, 만약 2차선에 차가 없다면 2차선으로 가지 않을 이유가 없기 때문입니다. 2차선에 차를 끼고 $v_0$ 의 속도로 다른 차선에서 달리는 것은 2차선의 어떤 차를 추월하는 것과 동일합니다. 고로 이것은 답의 형태가 다음과 같은 canonical form 으로 표현될 수 있음을 뜻합니다:

무조건 2차선으로 달림
만약 앞에 차가 있으면 1차선이나 3차선을 사용하여 추월하고, 추월이 끝나면 다시 2차선으로 돌아옴

2차선에서 $v_0$ 의 속도로 달리는 것을 상상하는 건 쉬우니, 결국 특정 시점에서 1차선이나 3차선을 사용하여 현재 2차선에 있는 $1$ 개 이상의 차들을 추월할 수 있는지, 있다면 그 차들을 추월하는 데 드는 시간이 얼마인지를 계산하는 문제라고 볼 수 있습니다. 두 옵션 중, 시간이 적은 옵션을 택하면 되기 때문입니다.

2차선에서 1차선을 사용하여 추월할 때는, 차선 변경이 가능해지는 순간이 오는 즉시 차선을 변경하고 달리는 게 이득입니다. 1차선에서는 무조건 2차선보다 빨리 달릴 수 있고, 차선 변경을 늦게 해서 얻는 이득이 없기 때문입니다. 차선을 변경한 이후에는, 앞에 차가 없을 때는 $v_0$ 으로, 차가 보일 때는 $v_1$ 로 달리다가 자리가 나면 다시 2차선으로 오면 됩니다. 현재 지난 시간과 2차선 상 위치를 통해서 1차선 상 차들의 분포를 알 수 있습니다. 적절한 전처리로 차선 변경이 가능해지는 순간과, 그 때 앞에 있는 차를 알아내면, 이제 다시 돌아오기까지 필요한 시간은 계산할 수 있습니다.

2차선에서 3차선을 사용하여 추월할 때는 무조건 차가 보이지 않아야 합니다. 차가 보이는 순간 2차선 차를 추월할 수 없기 때문입니다. 고로 3차선에서 적당한 시간에 끼어든 후, $v_0$ 으로 질주하고, 시간이 되면 바로 돌아올 수 있어야 합니다. 식을 계산해 보면, 현재 2차선에 $n$ 개의 차들이 붙어 있을 때, 3차선의 빈 공간이 $\frac{(n + 1)(v_0 - v_3)}{v_0 - v_2} + 1$ 이상이어야 합니다. 3차선의 "차 간 빈 공간" 들을 모두 전처리 해두면, 결국 문제는 현재 내 옆에 있는 빈 공간을 찾고, 그 공간 뒤에서 빈 공간 크기가 특정 수 이상인 첫 번째 수를 찾는 문제가 됩니다. 첫 번째는 이분 탐색으로 찾으면 되고, 두 번째는 적당한 자료구조를 쓰시면 됩니다. 이렇게 하면 $O(n \log n)$ 입니다.

첫 번째 부분은 1차선과 유사하게 전처리하고, 두 번째 부분을 Naive하게 처리하되 amortization이 되게 조심스레 구현하여도 됩니다. 이렇게 하면 $O(n)$ 에도 가능하지만, 필요하지는 않습니다.

Meta Hacker Cup 2019. Trees as a Service

BOJ에 쿼리와 트리 1 로 업로드 되었습니다.

백트래킹을 사용하여 Naive하게 접근해 봅시다. 트리를 top-down으로 구성해 나가는데, 매 순간 트리의 루트 를 모두 시도해 본 후 각각의 서브트리에 대해서 재귀적으로 문제를 해결합니다.

현재 트리의 루트가 $r$ 이라고 가정해 봅시다. 세 가지 경우가 있습니다:

$u = r$ 혹은 $v = r$: 이 경우 $w = r$ 이어야만 합니다.
위 경우가 아니고 $w = r$: $u, v$ 가 $r$ 을 기준으로 다른 서브트리에 속해야 합니다.
위 경우가 아니고 $w \neq r$: $u, v, w$ 가 $r$ 을 기준으로 같은 서브트리에 속해야 합니다.

1번 경우는 쉽게 판별할 수 있습니다. 3번 경우에 의해 같은 서브트리에 속해야 하는 정점들 사이에 간선을 잇고 Flood-fill을 합시다. 이렇게 컴포넌트를 구했을 때 2번 경우에 의해 모순이 생기게 되면 $r$ 은 올바른 루트가 아닙니다. $r$ 을 결정했다면, 3번 경우에 의한 컴포넌트에 따라 서브트리를 결정하고, 서브트리에 따라서 재귀적으로 문제를 해결해 주면 됩니다. $r$ 이 없다면 답은 없습니다.

위 조건을 만족하는 $r$ 이 여러개가 있다면 정말 백트래킹으로 모든 경우를 다 시도해 봐야 할까요? 사실은, 조건을 만족하는 $r$ 중 아무거나 선택해도 상관이 없습니다. 간단히 말해서, 조건을 만족하는 $r$을 선택했다가 문제가 생긴 상황이 있었다면, 그 문제를 주는 조건들은 어떤 $r$ 을 선택해도 없앨 수가 없기 때문에 $r$ 의 선택은 해를 찾는데 큰 차이를 주지 않습니다. 조금 구체적으로 말하면, 답이 없다는 것은 어떠한 정점 부분집합 $S$ 가 있어서, 이 부분집합 안에 있는 조건들로 루트를 구성할 수가 없다는 뜻이 됩니다. 이런 경우 트리를 찾으려면 $S$ 밖에 있는 루트를 잡아서 $S$ 를 다른 서브트리로 찢어야 한다는 것인데, 부분 집합은 $u, v, w$ 로 간선을 이었을 때 하나의 연결 컴포넌트를 이루기 때문에 $S$ 밖에 있는 루트로 $S$ 를 찢을 수 없고, $S$ 안에 있는 루트는 어차피 고를 수가 없습니다.

Subproblem의 수 $O(N)$ 개, 매번 루트를 고르는 데 $O(N)$ 개의 경우의 수, 루트가 답이 되는 지를 판별하는 데 $O(N+M)$ 시간이 들기 때문에, 시간 복잡도는 $O(N^2(N+M))$ 이 됩니다. 이걸 $O(N(N+M))$ 으로 줄이는 건 별로 어렵지 않습니다. 더 빠른 복잡도가 된다고 들었는데 전 그 방법을 모릅니다.

BOJ 28382 Yet Another Problem on Empodia 2

프레임 구간 을 세 가지 경우로 분리해서 생각합시다. 각각 $[1, k]$ 에 속하는 프레임 구간, $[k + 1, n]$ 에 속하는 프레임 구간, 둘을 가로지르는 프레임 구간 - 의 경우입니다.

첫 번째 경우는 이미 수가 결정되었으니 우리가 어떻게 할 수 없고, 고려해 줄 필요도 없습니다.

두 번째 경우를 보기 위해, $[1, k]$ 에 등장하지 않은 수들을 모아서 정렬해 봅시다. 수들을 정렬해 보면 $i, i + 1, i + 2, \ldots$ 의 형태로 연속한 수들의 구간을 관찰할 수 있습니다. 예를 들어 $n = 8, k = 2, a_1 = 2, a_2 = 6$ 이라면, $[1], [3, 4, 5], [7, 8]$ 와 같이 두 연속된 구간으로 묶을 수 있을 것입니다. 두 번째 형태의 구간만 최적화하는 배치는

연속된 구간을 아무 순서로 배치하고
각 구간 안에서는 증가 혹은 감소 순서로 배치하는

배치입니다. 예를 들어 $[3, 4, 5], [8, 7], [1]$, $[7, 8], [1], [5, 4, 3]$ 과 같은 배치가 되겠습니다. $[1], [4, 3, 5], [7, 8]$ 은 이러한 조건을 만족하는 배치가 아닙니다. 이러한 배치에서는 두 번째 경우의 답이 최대화되고, 또한 이러한 배치만이 두 번째 경우의 답을 최대화하는 것을 알 수 있습니다. 사실은 세 번째 경우의 답도 이러한 배치를 하는 것이 유리합니다. 왼쪽에 수가 붙는다고 해서 특별히 오른쪽 수를 섞을 이유가 생기지는 않기 때문입니다.

세 번째 경우를 보기 위해, 일단 $[1, k]$ 의 suffix 중 오른쪽에 수가 적당히 배정되었을 때 프레임 구간이 될 가능성이 있는 구간을 모아봅시다. 어떠한 구간 $[i, k]$ 에 대해서, $range([i, k]) = [\min(a_i, a_{i + 1}, \ldots, a_k), \max(a_i, a_{i + 1}, \ldots, a_k)]$ 구간에 있는 수들이 모두 위치 $i$ 이후에 등장한다면 이 구간을 좌측 프레임 구간 이라고 부릅시다. $k+1$ 이후의 수를 사용해서 프레임 구간을 만들기 위해서는 이 조건을 무조건 만족해야 합니다.

좌측 프레임 구간을 $i$ 가 감소하는 순서대로 처리하면서, 우측에 있는 연속 구간 중 하나를 붙인다고 생각합시다. 연속 구간 하나를 붙이는 시점은, 좌측 프레임 구간의 $range$ 가 연속 구간과 만나는 시점이어야 합니다. 이걸 말로 설명하기가 대단히 미묘하며, 실제로 정확히 어떠한 케이스이고 어떻게 구현해야 하는지를 찾기 어렵습니다. 여기서는 구체적인 알고리즘에 대한 설명은 없이, 예시 정도만 설명하고 글을 마칩니다.

첫 번째로, $n = 10, k = 5, a = [8, 1, 9, 4, 5]$ 라고 합시다. 등장하지 않은 수들로 연속 구간을 만들면 $[2, 3], [6, 7], [10]$ 이 나옵니다. 좌측 프레임 구간은 $[5], [4, 5], [8, 1, 9, 4, 5]$ 와 같이 $3$ 가지가 있습니다. 이 때:

$[5]$ 를 처리하는 시점에 붙일 수 있는 구간은 $[6, 7]$ 뿐입니다. 다른 구간을 붙인다고 프레임 구간을 만들 수 없습니다.
$[4, 5]$ 를 처리하는 시점에 붙일 수 있는 구간은 $[6, 7], [2, 3]$ 뿐입니다. $[4, 5]$ 입장에서는 둘 중 뭘 붙여도 상관이 없으나, 실제로는 $[5]$ 때문에 $[6, 7]$ 을 먼저 붙여야 합니다. $[2, 3]$ 을 붙일 때 $[3, 2]$ 순서로 붙여야 구간 수에 기여함을 조심해야 합니다.
$[8, 1, 9, 4, 5]$ 를 처리하는 시점에 붙일 수 있는 구간은 $[10]$ 뿐입니다. $[6, 7], [2, 3]$ 을 안 붙였다면 지금이라도 붙여야 겠지만, 이들 때문에 새로운 프레임 구간이 생기지는 않으니 $[4, 5]$ 가 처리될 때 붙였어야 했습니다.

$range$ 의 오른쪽 끝이 $5$ 일 때 $[6, 7]$ 을 붙일 수 있고, 왼쪽 끝이 $4$ 일 때 $[2, 3]$ 을 붙일 수 있습니다. 이러한 시점이 여럿 있을 때 어떤 것을 골라야 할지는 미묘합니다. 일단 여기서는 $[8, 1, 9, 4, 5, 6, 7, 3, 2, 10]$ 이 유일한 최적해입니다.

두 번째로, $n = 9, k = 5, a = [4, 6, 1, 9, 5]$ 라고 합시다. 좌측 프레임 구간은 $[5], [4, 6, 1, 9, 5]$ 뿐이고, 우측의 연속 구간은 $[2, 3], [7, 8]$ 입니다. 좌측 구간의 $range$ 가 이 연속 구간과 절대 닿지 않습니다. range가 이 구간을 가로지를 때 넣는게 유일한 선택지입니다. $[4, 6, 1, 9, 5, 3, 2, 7, 8], [4, 6, 1, 9, 5, 7, 8, 3, 2]$ 어떤 것을 선택해도 답이 같습니다.

세 번째로, $n = 12, k = 7, a = [1, 3, 4, 5, 6, 7, 9]$ 라고 합시다. 모든 suffix가 좌측 프레임 구간이고, 우측의 연속 구간은 $[2], [8], [10, 11, 12]$ 입니다. $[2], [8]$ 은 넣을 시점이 꽤 명확하지만, $[10, 11, 12]$ 는 사실상 아무데나 넣어도 됩니다. 선택지를 비교해 봅시다:

$[1, 3, 4, 5, 6, 7, 9, 10, 11, 12, 8, 2] = 36$
$[1, 3, 4, 5, 6, 7, 9, 8, 10, 11, 12, 2] = 51$
$[1, 3, 4, 5, 6, 7, 9, 8, 2, 10, 11, 12] = 39$

왜 차이가 날까요? $10, 11, 12$ 로 끝나는 구간 3가지를 생각해 보았을 때, 첫 번째 경우는 $range$ 의 가능한 끝점이 $9$ 하나, 두 번째 경우는 가능한 끝점이 $8, 7, 6, 5, 4, 3$ 6개, 세 번째 경우는 가능한 끝점이 $1, 2$ 2개이기 때문입니다. 결국 끝점을 넣는 경우가 여럿 있으면, 이 중에서 가능한 가용 구간이 최댓값인 시점 (시점은 좌측 프레임 구간의 번호로 identify하면 됩니다) 에 적당히 잘 끼워 넣어야 한다는 결론이 됩니다. 프레임 구간을 크기가 커지는 순서대로 보면서, 어떠한 수가 특정한 프레임 구간의 왼쪽 / 오른쪽 끝점으로 등장한다면, 그러한 수의 왼쪽 / 오른쪽 끝점이 확장되는 최적의 시점을 기록해 둘 수 있습니다. 이제 기록한 값을 토대로, 다시 프레임 구간을 크기가 증가하는 순서대로 보면서, 오른쪽 / 왼쪽 끝점을 확장해야 하는 시점에 맞게 확장시켜 주면 됩니다.

사실 이 문제에서는 최적의 배치를 찾는 것에서 끝나지 않고, 이에 따른 프레임 구간의 개수도 세어야 합니다. 가장 쉬운 방법은 위의 방식대로 construction을 한 후 프레임 구간의 개수를 따로 세는 것입니다. 조금 어려운 방법은 construction을 하는 과정에서 생긴 프레임 구간의 개수를 세는 것인데 이러한 식으로도 가능하지만 쉽지 않으니 첫 번째 방식만 설명합니다. $r = 1, 2, \ldots, n$ 으로 증가시켜나가면서, $val[l] = \max(a_l, \ldots, a_r) - \min(a_l, \ldots, a_r) - (r - l)$ 이라고 정의합니다. $val[l] \geq 0$ 이며, $val[l] = 0$ 인 경우 $(l, r)$ 이 프레임 구간입니다. 스택을 사용하여 $a_i$ 의 최댓값과 최솟값들을 관리하면, 문제는 $val$ 이라는 배열에 구간 덧셈을 하고, 최솟값과 최솟값의 개수를 관리하는 문제가 됩니다. 이는 Lazy propagation을 이용한 세그먼트 트리로 해결할 수 있습니다. 프레임 구간들의 Structure를 관리하는 Permutation Tree 라는 자료구조가 있는데, 이 문제의 풀이에는 사실 별로 도움이 되지 않지만 개수를 세는 딱 이 지점에는 도움이 될 수 있습니다.

여담으로 2023/05/14 진행되었던 Codeforces Round #873 의 Div1F 가 이 문제의 어려운 버전입니다.

Algorithmic Engagements 2021. Oranzada

맨 앞에 올 서로 다른 $k$ 개 수를 고를 때, 해당 수의 첫 등장 위치가 가장 앞인 $k$ 개의 수를 고르는 것이 최적입니다. 일단 첫 번째 등장 위치만 생각해도 되고, 굳이 뒤에 있는 숫자를 고를 이유도 없기 때문입니다. 이제 이 $k$ 개의 수를 맨 앞으로 옮기는 데 필요한 최소 비용을 계산해야 합니다. 이 비용은 위치 차이의 합보다 크거나 같은데, 왼쪽에 있는 것부터 차근차근 옮기면 위치 차이의 합의 비용으로 이것이 가능합니다.

결국, 각 수에 대해서 가장 먼저 등장한 위치를 구하고, 이 중 $k$ 개의 최솟값을 골라서 위치 차이를 계산하면 됩니다. 시간 복잡도는 최솟값을 고르는 데 필요한 정렬로 $O(n \log n)$ 입니다 ($O(n)$ 도 가능합니다).

POI 2020/2021 Stage 3. Les Biterables

$i$ 번 전동차의 위치 $n$ 개와 $i+1$ 번 전동차의 위치 $m$ 개가 주어졌을 때 문제를 푸는 방법을 생각해 봅시다. 이 문제를 $O(n + m)$ 정도에 풀 수 있다면 전체 문제는 그냥 이 알고리즘을 $n-1$ 번 반복하면 됩니다.

원래 문제에서는 $0, d$ 번 위치에 무한한 카메라가 공급되고, 또 무한한 카메라를 둘 수 있습니다. 여기서 아이디어를 하나 낼 수 있는데, 승강장을 한 바퀴 말아서 $0, d$ 번 위치를 같은 위치로 두는 것입니다. 원을 시계 반대방향으로 한바퀴 도는 행위를, $0$ 번 위치에 카메라를 두고 $d$ 번 위치에서 카메라를 받은 후 다시 출발한다는 식으로 생각하면 충분히 할 수 있기 때문입니다.

이제 둘레 $d$ 의 원 위에 공급점 $n$ 개 수요점 $m$ 개가 있고, $0$ 번 위치에서는 무한한 공급과 수요가 있을 때, 최소 비용으로 카메라들을 매칭하는 문제가 됩니다. 만약에 $0$ 번 위치에서 $x$ 개의 카메라를 공급받고, $y$ 개의 카메라를 채웠다고 하면, 이 중 $min(x, y)$ 개의 카메라는 그냥 $0$ 번 위치를 거치지 않고 직접 해당 위치에 배달하면 됩니다. 고로 $0$ 번 위치에는 $|n - m|$ 개의 카메라만 공급받거나 공급하면 됩니다. 다시 말해, $n = m$ 일 때 $0$ 번 위치는 아무 의미가 없으며, $n \neq m$ 일 때, 작은 쪽의 수를 $0$ 번 위치로 채워서 $n = m$ 으로 바꾸면 된다는 것입니다.

또 다시 단순화해서, 둘레 $d$ 의 원 위에 공급점 $n$ 개 수요점 $n$ 개가 있어서 이들을 최소 비용으로 매칭하는 문제로 바꿨습니다. 원 문제는 보통 직선 문제로 환원하면 쉬워집니다. 이 문제를 직선에서 해결하는 방법은, 공급점과 수요점을 그냥 왼쪽에서 오른쪽으로 순서대로 매칭하면 됩니다. 이런 식으로 해결하기 위해서 원 문제에 대해 몇가지 관찰을 해 봅시다.

공급점에서 수요점으로 가는 경로를 원 상에 화살표로 표시한다고 합시다. 여기서 몇 가지 관찰을 할 수 있습니다:

원 상의 어떠한 원호 지점에서, 왼쪽으로 가는 화살표와 오른쪽으로 가는 화살표가 동시에 존재하지 않습니다 (그렇다면 서로 Cancel해서 답의 비용을 줄일 수 있음)
모든 공급점이나 수요점이 다르다면, 원 상의 어떠한 원호 지점은 화살표가 존재하지 않는 경우가 존재 (아니라면 화살표가 한쪽 방향으로만 돌게 되는데 이 경우에 $d$ 만큼 답의 비용을 줄일 수 있습니다.)

실제로는 $0$ 인 지점이 여러개 있지만, $10^{-100}$ 정도 다르다고 속으로 생각하면 크게 차이가 없습니다. 끊어볼 수 있는 지점이 $2n$ 개이고, 직선에서는 이 문제를 $O(n)$ 에 해결할 수 있으니, 여기까지가 $O(n^2)$ 입니다.

마지막으로 이 문제를 최적화하기 위해서는 직선에서의 문제를 조금 더 잘 해결해야 합니다. 공급점은 A, 수요점은 B 로 마킹해두고 각각을 위치 오름차순으로 나열했다고 합시다. 이걸 일종의 괄호 문자열처럼 생각하는데, 높이 $0$ 에서 $A$ 는 높이를 1 증가시키고, $B$ 는 높이를 1 감소시킨다고 생각합시다. 높이 $[i, i + 1]$ 을 지나는 공급점과 수요점을 순서대로 써보면, ABBAABBA... 와 같이 홀수번째 위치와 짝수번째 위치에 공급/수요가 따로 배치되어 있음을 볼 수 있고, 이 두 위치를 매칭하면 된다는 것 역시 알 수 있습니다. 이런 식으로 매칭을 해결하면, 맨 앞 점이 빠지고 뒷 점이 들어오는 큐와 같은 상황을 지원할 수 있습니다. 점이 빠진다고 높이가 바뀌지 않아서, 각 높이 $[i, i + 1]$ 에 대해 해당 높이를 지나는 점들을 큐로 관리하고, 홀수번째 위치와 짝수번째 위치의 위치 차이를 정수 변수 2개로 관리할 수 있기 때문입니다. 이렇게 하면, 초기 정렬 이후 문제를 $O(n)$ 시간에 해결할 수 있습니다.

PA 2019. Osady i warownie 2

$(0, 0)$ 에서 $(n - 1, m - 1)$ 으로 가는 가장 낮은 경로와 가장 높은 경로 두 개를 관리하고, 이 두 경로가 사라지는지만 중점적으로 관리합니다. 가장 낮다는 것은, 이 경로가 가능한 최대로 $n-1$ 번째 행과 $0$ 번째 열에 붙어있다는 것이고, 가장 높다는 것은 반대로 $0$ 번째 행과 $m-1$ 번째 열에 붙어있다는 것입니다. 만약에 새로 들어오는 점이 이 두 경로와 모두 겹치지 않는다면, 여전히 경로가 존재하니 이 점을 추가합니다. 만약에 새로 들어오는 점이 이 두 경로와 모두 겹친다면, 해당 점은 모든 경로의 병목 이 되는 것과 마찬가지이니, 더 이상 경로가 존재하지 않아 점을 추가하지 않습니다.

새로 들어오는 점이 이 중 정확히 한 경로와만 겹치고, 그 경로가 일반성을 잃지 않고 가장 낮은 경로라고 합시다. 이 경우 이 점은 높은 경로와는 겹치지 않으니, 낮은 경로를 적당히 수정하면 어쨌든 새로운 경로를 찾을 수 있음이 보장됩니다. 낮은 경로가 지나는 길을 'A', 새로운 점을 'X' 로 표현하면, 새로운 경로 'B' 는 다음과 같은 식으로 생기게 됩니다.

#ABB.
#AXA.
###A.
###A.
###AA
#####

#ABBB
#AAXB
###AB
###AB
###AA
#####

#A...
#AAA.
###AB
###XB
###AA
#####

이 방식대로 새로운 경로를 찾아주면 되는데, 문제는 B로 마킹된 영역에도 점이 존재할 수 있다는 것입니다. 이 경우에는 B로 새로운 경로를 만들어준 후, 해당 위치에 점이 삽입 되었다고 생각하고 재귀적으로 움직이시면 됩니다. 새로운 경로 B는 ㄱ자 형태로, 가로와 세로 줄로 분리됩니다. 가로줄에서는 가장 오른쪽 점, 세로줄에서는 가장 위쪽 점만 중요하니, 이 두 점이 경로에 삽입되었다고 하고 재귀적으로 진행하시면 됩니다.

경로와 점 관리 등을 std::set으로 하시면, 한 경로 안에 점이 교차하는 지를 $O(\log q)$ 시간에, 경로 하나를 고치는 데 Amortized $O(\log q)$ 시간이 필요합니다. 고로 시간 복잡도는 $O(q\log q)$ 입니다. ($n, m$ 이 커도 상관이 없습니다.)

구현 시에는 높은 경로를 따로 짤 필요가 없이 같은 자료구조를 $n, m$ 만 바꿔서 그대로 쓰시면 됩니다.

ROI 2021 P4. Доклад инвесторам

$M = \sum m_i$ 라고 합시다.

다항 시간 풀이를 얻는 것은 어렵지 않습니다. $dp[v][w]$ 를 노드 $v$ 에서 번호 $w$ 이후의 보고서만 모았을 때 가능한 보고서 번호 최댓값의 최소라는 식으로 정의합시다. 리프가 아닌 노드에 대해서 이를 다음과 같이 합칠 수 있습니다:

$k!$ 개의 자식 순서를 다 시도해 보면, 대략 $dp[v_k][dp[v_{k - 1}] \ldots dp[v_1][w] \ldots ]]$ 와 같은 값을 계산한 후 이들 중 최소를 취하면 됩니다. 이렇게 하면 각 값을 계산하는 데 $O(k!)$ 정도의 시간이 들어 전체 문제가 $O(k! nM)$ 시간에 풀리고, $n, M \le 100$ 인 서브태스크를 풀 수 있습니다.
$k!$ 의 순서를 다 시도해 보는 문제에서 이를 bitmask dp를 사용하여 최적화할 수 있는 경우가 많습니다. 여기서도 $aux[S][w]$ 를, $S$ 에 있는 자식들을 $w$ 에 통과시켰을 때 가능한 최댓값 최소라고 정의하면, 각 값을 계산하는 데 $O(2^k k)$ 시간이 들어 전체 문제가 $O(2^k knM )$ 시간에 풀립니다. $n, M \le 500$ 인 서브태스크를 풀 수 있습니다.

제한을 보면 만점 풀이에서 $dp[v][w]$ 를 전부 계산하는 것은 그렇게 현실적이지 않아 보입니다. 그렇다고 간단한 그리디가 있을지도 잘 모르겠으니, 일단 DP에 기반한 방법의 상태를 최대한 줄여 봅시다. $dp[v][w] \le dp[v][w + 1]$ 이라는 사실은 자명한데, 사실 $dp[v][w] = dp[v][w + 1]$ 이면 $dp[v][w]$ 항은 쓸모가 없습니다. $(w, dp[v][w + 1])$ 을 해당 서브트리에서 택할 바에 더 좁은 $(w + 1, dp[v][w + 1])$ 을 택하면 되기 때문입니다. 비슷하게 $dp[v][w] = \infty$ 여도 쓸모가 없을 것입니다. 이런 식으로, $dp[v]$ 를 어떠한 단조 구간 들의 집합으로 둡시다. 즉

어떤 구간 $[a, b]$ 가 $dp[v]$ 에 속한다는 것은, $v$ 의 서브트리에서 $[a, b]$ 구간에 속하는 보고서들만 나열할 수 있는 방법이 존재한다는 뜻
만약 어떤 구간 $[a, b]$ 에 대해 $a \le c \le d \le b$ 를 만족하는 $[c,d] \in dp[v]$ 라면 $[a, b]$ 는 $dp[v]$ 에서 관리하지 않음

이렇게 하면 $dp[v]$ 의 상태를 충분히 작게 유지할 수 있을까요? 직관을 얻기 위해 $K = 2$ 인 케이스를 살펴봅시다. 노드의 두 자식 $dp[l], dp[r]$ 이 주어질 때, $dp[v]$ 의 크기는 $2\min(|dp[l]|, |dp[r]|)$ 을 넘지 않음을 알 수 있습니다. 왜냐하면:

$l$ 을 $r$ 보다 앞에 둘 경우 답의 크기는 $l$ 의 서로 다른 시작점 수 이하입니다.
$l$ 을 $r$ 보다 뒤에 둘 경우 답의 크기는 $l$ 의 서로 다른 끝점 수 이하입니다.

그렇다면 $dp[v]$ 의 크기 합은 얼마로 유지될까요? 어쨌든 $dp[v]$ 의 크기는 $v$ 의 서브트리에 있는 보고서 수보다 크지 않습니다. 고로 전체 크기 합은 모든 서브트리에 대해서 작은 서브트리의 크기 합에 2를 곱한 것이 되고, small-to-large argument에 의해 이는 $O(M \log M)$ 이하입니다. 두 자식을 합치는 것 역시 Two pointers로 해결할 수 있기 때문에, 전체 시간 복잡도는 $dp[v]$ 의 크기 합에 비례하고, 고로 $K = 2$ 인 케이스를 $O(M \log M + n)$ 에 해결할 수 있습니다.

$K > 2$ 인 경우에 이 알고리즘을 일반화하는 것은 어렵지 않습니다. 처음에 $aux[S][v]$ 와 같은 bitmask DP로 $2^k \times k$ 의 추가 시간을 사용하여 여러 노드를 합쳤었는데, 결국 $aux[S]$ 도 위와 똑같이 단조 구간의 집합으로 두면 모든 것을 똑같이 할 수 있습니다.

결론부터 말하자면, 이렇게 한 후 귀찮은 역추적을 구현하기만 하면 만점을 받을 수 있습니다. 증명도 간단한 편입니다. 만약 어떠한 노드의 서브트리 중 과반의 보고서를 가진 서브트리가 없다면, 구간이 고려되는 횟수는 서브트리를 타고 올라가는 $O(\log M)$ 번과 거기서 $O(2^k \times k)$ 번 사용되는 경우 뿐입니다. 그렇지 않다면, 과반의 보고서를 가진 서브트리가 아닌 쪽에서 $O(2^{k-1})$ 번의 연산으로 합쳐주고, 과반의 서브트리와 $K = 2$ 의 요령으로 합쳐주면 됩니다. 이렇게 하면 크기가 $2(\sum m_i - \max m_i)$ 로 bound되기 때문에, 그냥 위와 똑같은 small-to-large argument를 쓸 수 있습니다. 과반의 보고서를 무시해 주는 건 증명에서만 무시해 주면 되고, 실제로는 신경쓰지 않고 자연스러운 bitmask DP를 짜 주기만 하면 됩니다.

종합적으로, 시간 복잡도는 $O( 2^k kM \log M)$ 가 됩니다. (사실 정해에서는 $k$ 항은 안 붙어 있습니다. 저도 그게 맞다고 생각하지만 그 정도로 열심히 분석하지는 않겠습니다.) 여담으로 $k_i = 1$ 인 경우 위와 같이 구현하면 시간 복잡도가 $O(n^2)$ 가 될 수 있으니, 이 경우는 따로 처리해 주어야 합니다.

관련 있을 수도 있는 글들

2023.08.29 problem solving

댓글