APIO 2019

A. Strange Device

Subtask 1 (10점)

문제에 적힌 대로 모든 순서쌍을 나열한 후, 정렬하여 서로 다른 순서쌍의 개수를 세자.

Subtask 4/5 (20점)

고정된 $0 \le y < B$ 에 대해서 쌍이 겹칠 수 없으니, 각각 따로 문제를 해결한 후 합쳐주자. $t = qB + y$라고 하면, $x = qB + y + q$ 로 표현 가능하다. 이때, $y$ 는 상수이고, $q(B+1) + y \mod A$라는 식은 $q$가 $T = A / gcd(A, B + 1)$ 주기로 반복됨을 알 수 있다.

각각의 구간 $[L_i, R_i]$ 에 대해서, 가능한 $q$ 의 구간을 계산할 수 있다. 가능한 $q$ 의 구간을 계산했다면, 가능한 $q \mod T$ 의 구간 역시 알 수 있다. (원형으로 넘어가는 것을 주의하도록 하자.) 결국 각 $y$ 에 대해서 가능한 $x$ 의 개수는 가능한 $q \mod T$ 의 개수랑 동일하니, 이러한 구간을 전부 추린 후, 구간 합집합을 $O(N \log N)$ 시간에 계산하면 $O(BN \log N)$ 에 문제를 해결할 수 있다.

$N$ 개의 구간의 합집합을 구하는 것은, $[A_i, B_i]$ 구간이 주어질 때, $(A_i, +1), (B_i + 1, -1)$ 과 같은 쌍을 $2N$ 개 만든 후 좌표 순으로 정렬하여, 두 번째 값에 대한 prefix sum이 0을 초과하는 구간의 길이 합을 세면 된다. 변화값 배열과 같은 원리지만, 좌표가 커서 정렬로 대체했다는 정도의 차이가 있다.

Full solution (100점)

$t = qB + y$라고 하면, 결국 우리가 원하는 것은 모든 $0 \le y < B$ 에 대해서 가능한 $q \mod T$ 의 구간을 찾는 것이다. 이제는 $y$ 를 분리할 필요가 없이, 단순히 $t \in [L_i, R_i]$ 에 대해 가능한 모든 $t \mod (TB)$ 의 구간을 찾으면 된다. 이는 위에 적은 방법을 그대로 사용하면 된다. $TB \ge 10^{18}$ 인 경우를 유의하자.

난 이 풀이를 찾지 못하고 상당히 복잡한 풀이를 찾아서 문제를 푸는 데 오래 걸렸다.

B. Bridges

Subtask 1 (13점)

각각의 쿼리를 naive 하게 처리해 주면 된다. 쿼리 1에서 간선의 가중치는 $O(1)$ 에 갱신 가능하고, 쿼리 2는 깊이 우선 탐색을 사용하여 $O(n+m)$ 에 계산 가능하다. 기호에 따라 Union-Find를 사용해도 된다. 시간 복잡도는 $O(q(n+m))$이다.

Subtask 4 (27점)

Union-Find 자료구조를 사용한다. 모든 쿼리와 간선을 가중치가 감소하는 순으로 정렬한다. 쿼리를 정렬된 순서로 보면서, 해당 쿼리보다 가중치가 큰 간선들을 union-find에 삽입한다. union-find에서 어떤 정점에서 도달 가능한 정점의 개수를 세는 것은, union-find의 각 컴포넌트에 size 정보를 추가하고, union 쿼리마다 size를 관리해 주면 어렵지 않게 셀 수 있다. 시간 복잡도는 $O((m + q) \log (m + q))$이다.

Subtask 2 (43점)

직선이니, 배열이라고 생각하고 문제를 해결한다. 첫 번째 쿼리는 배열의 원소를 갱신하는 것이고, 두 번째 쿼리는 어떠한 배열의 위치를 포함하며 $w$ 이상의 원소로만 이루어진 연속 배열의 크기를 세는 것이다.

두 번째 쿼리를 해결할 때의 전략은, 주어진 위치에서 $w$ 미만의 수가 나올 때까지 왼쪽으로 가 보고, 주어진 위치에서 $w$ 미만의 수가 나올 때까지 오른쪽으로 가 보는 것이다. 이러한 전략은 구간 최솟값을 빠르게 구할 수 있다면 이진 탐색으로 최적화할 수 있다. 오른쪽으로 가 볼 때, 최솟값이 $w$ 미만인지 아닌지를 토대로 이진 탐색에서 분기 방향을 판정할 수 있다. 왼쪽도 동일하게 하면 된다.

고로, 가중치에 대한 Min Segment Tree를 만들면 된다. 첫 번째 쿼리는 원소 갱신이니 간단하고, 두 번째 쿼리는 이진 탐색을 통해서 $O(\log N)$ 번의 쿼리를 사용하면 해결할 수 있다. 시간 복잡도는 대략 $O(Q \log^2 N)$ 정도이다. 이진 탐색을 사용하지 않고 트리를 효율적으로 탐색하면 $O(Q \log N)$ 도 어렵지 않다.

Full solution (100점)

쿼리에 대한 Sqrt-decomposition을 사용한다. 방법은 다음과 같다. 쿼리가 $B$ 개 정도라고 가정하고 문제를 $O(N \log N + B^2)$ 시간 복잡도에 해결한다. 이러한 방법을 사용해서 $B$ 개의 쿼리를 해결한 후, 실제 입력으로 들어온 간선의 가중치를 $O(M)$ 정도의 시간 복잡도로 갱신해 준다. 이를 반복해 주면, $O(\frac{Q}{B} M + \frac{Q}{B}(M + N \log N + B^2 \log N))$ 시간 복잡도에 문제가 해결된다. $B = N^{0.5}$ 로 잡아주면, 시간 복잡도 $O(QN^{0.5}\log N)$ 풀이를 찾을 수 있다.

첫 번째 단계는 $O(M + N \log N + B^2\log N)$ 시간에 문제를 해결하는 것이다. 모든 간선이 가중치 역순으로 정렬되어 있다고 가정하자. 일단 어떠한 간선이 해당 쿼리에서 가중치가 갱신되는지를 $O(M)$ 스캔으로 확인한 후, 해당 쿼리에서 가중치가 갱신되지 않는 간선들만 가지고 최대 스패닝 트리를 만든다. 이제 간선들을, 가중치가 갱신되지 않는 간선의 최대 스패닝 트리와, 가중치가 갱신되는 간선의 리스트 (사이즈가 최대 $B$)로 분류할 수 있다. 질의 쿼리를 모두 가중치 역순으로 정렬하자. 가중치가 갱신되지 않는 간선들은 갱신과 상관없이 무조건 그래프에 존재한다. 고로 27점 풀이와 마찬가지로 이들을 하나씩 union-find에 삽입한다.

가중치가 갱신된 간선들은, 직접 리스트를 돌면서 쿼리가 적용되는 시점에 해당 간선에 적용된 가중치를 찾아준다. 이 가중치가 쿼리 이상이면 union-find에 삽입하고, 삽입이 끝나면 union-find에서 컴포넌트 사이즈를 체크한다. 다음 쿼리를 처리하기 위해서, 이렇게 삽입한 $O(B)$ 개의 간선들을 다시 제거해야 함이 중요하다. 이를 위해서, 되돌리기가 가능한 union-find를 사용해야 한다. size나 rank compression을 사용하여 amortization이 필요 없게 해야 한다. 이에 대해서는 이 곳을 읽어보자. 하여튼 관건은, $O(B)$ 개의 간선을 추가할 때 해당 간선의 가중치를 정확히 알아야 하고, 연산 이전의 상태로 $O(B \log N)$ 시간에 완벽히 되돌릴 수 있도록 신중히 구현해야 한다. Path compression을 사용할 수 없기 때문에 union-find의 시간 복잡도는 $O(\log N)$이다. 실제로 Path compression을 쓰면 TLE가 나는지는 잘 모르겠다.

이 부분에서, 스패닝 트리를 굳이 만들 필요가 없다고 주장할 수 있다. 굳이 스패닝 트리를 만들지 않더라도 $O(M \log N)$ 시간에 갱신되지 않는 간선들을 스캔해 주면 되기 때문이고, 2배밖에 차이가 안 나기 때문이다. 좋은 지적이라고 생각하지만, 이 문제에서는 애석하게도 2배의 차이가 중요해서 확답을 할 수는 없을 것 같다. 나는 어째서인지 스패닝 트리를 꼭 만들어야 한다고 생각해서 그렇게 했는데, 안 하고 AC를 맞은 사람이 있다면 알려주면 좋을 것 같다. 아무튼 만들어주는 게 어렵지 않으니 그냥 만들어 주자.

두 번째 단계는 $O(M)$ 시간 복잡도에 간선의 가중치를 갱신하는 것이다. 그냥 적당한 위치에 써 주면 되니까, 간선 가중치의 갱신이 어려울 이유가 없다고 생각할 수 있다. 하지만, 첫 번째 단계에서 정렬을 가정했으니 $O(M)$ 시간 복잡도에 정렬을 해야 한다. 여기서는, 가중치가 갱신된 간선이 많지 않으니 이를 효율적으로 할 수 있다. 가중치가 갱신되지 않은 간선들과 가중치가 갱신된 간선들을 따로 생각하자. 갱신되지 않은 간선들은 이미 정렬되어 있을 거고, 갱신된 간선들은 $O(B \log B)$ 에 내장 정렬로 정렬해 주자. 이제 두 정렬된 리스트를 Merge sort와 같은 방법으로 합쳐주면 된다. 이는 std::merge라는 STL 함수를 사용하면 한 줄로 해결할 수 있다. 어차피 $O(M \log M)$ 이니까 두 번째 단계가 필요 없다고 생각할 수 있겠지만, 나를 포함한 많은 사람들이 이 과정을 안 거친 후 TLE를 받았다.

시간제한이 여유롭지 않으니 상수 최적화에 신경 쓰자. $B$ 의 사이즈도 중요하다. 단순히 생각하면 $B = 300$ 정도를 잡을 수 있겠으나, 쿼리 $B$개를 한꺼번에 처리할 때 전처리 단계에서 오버헤드가 많아 줄이는 것이 좋다. 나는 $B = 800$ 을 사용했다.

Challenge

비슷하지만 조금 더 쉬운 문제인 Dynamic MST는 $O((m + q)\log(m + q))$ 시간에 오프라인 알고리즘으로 해결할 수 있음이 알려져 있다. 이 문제 역시 임의의 $\epsilon > 0$ 에 대해 $O((m + q)^{1 + \epsilon})$ 시간에 해결할 수 있을까?

다음과 같은 Conjecture를 가정하자:
Conjecture (OMv Conjecture). $n \times n$ Boolean matrix와 vector $v_1, v_2, \ldots, v_n$ 이 주어졌을 때, $M v_1, M v_2, \ldots, M v_n$ 을 계산하여라. 이 때 $v_i$ 는 $M v_{i-1}$ 을 계산한 후에만 얻을 수 있다 (Online). 이 문제는 $O(n^{3-\epsilon})$ 에해결하는 것이 불가능하다.

이 Conjecture에 따라서 온라인 쿼리로 이 문제를 쿼리당 $O(n^{1/2-\epsilon})$ 에 해결할 수 없음을 증명하라. 정답은 이 글에서 찾을 수 있다.

C. Street Lamps

Subtask 1 (20점)

모든 가로등 상태를 $q \times n$ 크기의 2차원 배열로 관리하고, 각 쿼리에 대해서 해당 배열에서 $[a, b)$ 구간이 전부 1로 되어 있는 행의 개수를 세면 된다. 시간 복잡도는 $O(q^2n)$이다.

Subtask 2 (40점)

$b - a = 1$이라, 해당 문자열에서 특정 위치가 1이었던 시간의 합을 구하는 문제가 된다. 어떠한 위치가 켜질 때, 이 위치가 켜진 시간을 적어놓자. 어떠한 위치가 꺼질 때, 이 위치가 켜진 시간과 꺼진 시간의 차를 계산한 후, 이렇게 "완전히 켜졌다 꺼진" 시간을 다른 배열에 더해 준다.

쿼리가 들어오면 두 가지 경우가 있다. 현재 쿼리로 묻는 정점이 꺼져있다면, "완전히 켜졌다 꺼진" 시간의 합이 문제의 정답이니 이를 출력하면 된다. 켜져 있다면, 이 값에다가, 해당 위치가 켜진 시간과 쿼리로 들어온 시간의 차를 더해주면 된다. 모두 단순 배열 처리이고 시간 복잡도는 $O(q + n)$이다.

Subtask 3 (60점)

결국 가로등이 켜지기만 하지 꺼지지는 않으니, 어떠한 구간이 모두 켜져 있게 되는 최초의 시간을 알면, 그 시간부터 쿼리로 들어오는 시간까지는 모두 가로등이 켜져 있음을 알 수 있다.

오프라인으로 문제를 해결하자. 처음에는 toggle 쿼리만을 처리한다. 각각의 위치에 대해서 해당 위치가 처음으로 켜진 시점을 배열에 저장하자. 이제 어떠한 구간이 모두 켜져 있게 되는 최초의 시간은 해당 구간의 배열 최댓값임을 알 수 있다. Max Segment Tree를 만든 후, query 쿼리가 들어올 때 어떠한 구간이 모두 켜져있게 되는 최초의 시간을 트리를 사용해서 계산하고, 쿼리 시간하고 빼서 정답을 찾는다.

Subtask 4 (80점)

쿼리가 들어옴에 따라서 온라인으로 현재 배열의 상태를 관리해보자. 1로 이루어진 연속된 구간들을 관리할 것이다. 만약에 어떠한 위치가 0에서 1로 바뀐다면, 해당 위치에 새로운 길이 1의 구간이 생기며, 그 구간에 바로 인접한 구간들은 이 구간과 합쳐진다. 고로 최대 2개의 구간이 사라지고 1개의 구간이 추가된다. 반대로, 어떠한 위치가 1에서 0으로 바뀐다면, 해당 1을 포함하는 구간은 왼쪽 / 오른쪽으로 분해되어, 1개의 구간이 사라지고 최대 2개의 구간이 생긴다. 각 toggle 쿼리가 들어왔을 때, 이러한 식으로 구간을 관리하는 것은 std::set과 같은 자료구조를 사용하면 할 수 있다.

이제 query 쿼리를 처리해야 한다. Subtask 2와 같이, 각 구간이 언제 추가되고 사라졌는지에 따라서 "완전히 켜졌다 꺼진 구간"과 현재 켜진 구간을 분리한다고 하자. 위에서 std::set에 구간들을 관리할 때, 어떠한 구간이 삭제되는 일이 있다면, 이들을 "완전히 켜졌다 꺼진 구간"으로 분류하고, 해당 구간이 존재했던 시간 (꺼진 시간 - 켜진 시간)와 함께 적당한 자료구조에 추가하자. (어떠한 자료구조를 사용할지는 후에 서술한다.)

쿼리가 들어올 때, 현재 켜진 구간에 대한 시간은, 결국 현재 주어진 구간을 완전히 포함하는 구간이 있는지, 그리고 이 구간이 언제부터 살아 있었는지를 확인하면 된다. 이는 구간을 시작점 순으로 관리하고, 각 구간에 켜진 시간을 같이 관리했다면 set에 lower_bound 연산을 하는 것으로 해결할 수 있다.

완전히 켜졌다 꺼진 구간들을 일단 배열에 담았다고 하자. 배열에는 최대 $O(q + n)$ 개의 구간들이 있고, 쿼리가 주어지면 주어진 쿼리를 완전히 포함하는 꺼진 구간 들에 대해서 해당 구간이 살아있던 시간을 더해주는 식으로 Naive 하게 해결할 수 있다. 이러한 풀이는 $O((n + q)^2)$ 시간에 문제를 해결할 수 있다.

이는 비효율적이니 효율적인 방법을 생각해본다. 입력으로 주어진 구간을 $[A, B]$라고 하였을 때, 어떠한 구간 $[S_i, E_i]$ 가 이 구간을 포함한다는 것은 $S_i \le A, B \le E_i$ 임을 뜻한다. 여기서, 시작점과 끝점을 2차원 평면상에 plotting 하여서 기하 문제로 변형하는 테크닉을 사용할 수 있다. 이 경우, $(S_i, E_i)$ 를 어떠한 2차원 평면 상의 점이라고 보면, 우리는 $[1, A] \times [B, N]$ 구간에 있는 이러한 점들을 전부 모아, 이들에 대한 살아있던 시간의 합을 계산하고 싶은 것이다. 고로, 각 구간을 가중치를 가진 2차원 평면 상의 점으로 보고, 원소 갱신과 구간 합 쿼리를 하면 된다.

서브태스크 4에서는 toggle 쿼리가 query 쿼리보다 모두 선행한다. 고로, 꺼진 구간들이 생기는 시점이 쿼리로 들어오는 시점보다 무조건 앞선다. 이는 구간(점)들이 모두 주어진 상태에서 문제를 해결하면 된다는 것을 뜻한다. 이는 잘 알려진 Plane sweeping을 사용하여 오프라인으로 처리할 수 있다. 모든 쿼리와 점을 $X$ 좌표 순으로 정렬하고, 각 $Y$ 좌표에 있는 점의 가중치 합을 Fenwick tree와 같은 자료구조에 관리한다. 쿼리가 주어졌을 때 해당 쿼리보다 $X$ 좌표가 작거나 같은 점을 모두 Fenwick tree에 저장했다면, 단순 $[B, N]$ 구간 합으로 답을 찾을 수 있다.

켜진 구간은 온라인으로 처리하고, 꺼진 구간은 오프라인으로 처리하는 것이 헷갈릴 수 있으나, 둘에 대한 답을 구하는 것은 완전히 독립적인 문제라고 생각하면 된다.

Full solution (100점)

서브태스크 4와의 차이점은 쿼리를 처리하는 와중에 점이 들어올 수 있다는 것이다. 사실 이러한 경우를 해결할 수 있는 해법은 다양하다. 가장 쉬운 것은 IOI 2013 Game에 나온 식의 2D Segment Tree를 사용하는 것이지만, 시간, 메모리, 구현 면에서 매우 비효율적인 풀이이다. 해당 문제는 온라인 풀이가 강제되는 상황이어서 그렇게 풀어야 했으나, 이 문제는 오프라인 으로 푸는 것이 가능하다. 현재 켜진 구간은 온라인으로 따로 처리한 후, 그 과정에서 구간이 언제 꺼지고, 쿼리가 언제 들어오는지에 대한 sequence를 구해놓으면, 꺼진 구간을 계산하는 것은 이와 독립적인 오프라인 문제라고 해석할 수 있다.

이러한 문제를 해결할 수 있는 방식은 여러 가지가 있는데, 가장 깔끔하다고 생각하는 분할 정복 풀이를 소개한다. 구간 추가와 구간 합을 묻는 쿼리의 수열이 있다고 하자. 구간의 합을 구하는 것은, 해당 구간보다 먼저 추가된 구간들을 쭉 돌면서 이 중 자신을 포함하는 구간들에 대해서 크기의 합을 더하는 것이다. 즉, 모든 $i < j$ 쌍에 대해서, $i$가 구간 추가, $j$ 가 구간 합 쿼리이고, $i$에 등장한 구간이 $j$ 에 등장한 구간을 포함한다면 $j$ 에 답을 더해주는 과정이다.

이를 분할 정복으로 해결해보자. Solve(S, E)를 모든 $S \le i < j \le E$ 구간에 대해서 위 과정을 실행하는 함수라고 정의하자. 기저 조건인 $S = E$ 는 자명하다. 아닐 경우, $M = (S + E) / 2$ 를 잡고, Solve(S, M)과 Solve(M+1, E)를 호출해서 $i \in [S, M], j \in [M + 1, E]$ 인 경우만을 남겨두자.

$i \in [S, M], j \in [M + 1, E]$ 인 경우를 해결할 때, 이 경우가 사실 서브태스크 4와 동일한 문제라는 것을 알 수 있다. 모든 구간 추가 쿼리는 $[S, M]$ 에 있고, 모든 구간 합 쿼리는 $[M + 1, E]$에 있어, 결국 구간 추가 쿼리를 전부 진행한 후 구간 합 쿼리를 처리하는 것이기 때문이다. 고로, 이 부분은 위에서 설명한 것과 동일한 분할 정복으로 $(E - S) \log (E - S)$ 시간 복잡도에 해결할 수 있다. $T(N) = 2T(N/2) + O(N\log N)$으로, $O((N + Q)\log^2(N + Q))$ 에 문제를 해결했다. 비슷한 방식으로 해결되는 문제에는 KOI 2018 조화로운 행렬, SEERC 2018 Points and Rectangles, ONTAK 2016 Cooking 등이 있다.