APIO 2019 풀이

얼마전 APIO 2019 대회가 진행되었다. Open Contest를 진행한 후, 풀이를 써달라는 분이 계서서 풀이를 작성하였다.

이러고 바로 풀이로 진행하면 블로그 미리보기로 스포일러가 되기 때문에, 몇가지 TMI를 추가한다. 한국은 비공식 성적으로 금메달 0개, 은메달 13개, 동메달 0개를 얻었으며, 보통 6명의 학생만 메달을 받는 것이 룰이지만 너무 많은 동점이 나와서 13명의 학생이 수상을 하는 일이 발생하였다. APIO 2008 이후 초유의 사태이지만 사실 금메달 컷이 깔끔하게 잘려서 별 상관은 없는 것 같다.

문제는 Strange Device / Bridges / Street Lamps 3 문제가 출제되었다.

APIO 문제들은 항상 굉장히 좋은 문제들이 나온 경우가 많았는데, 이번 APIO에서는 문제가 약간 실망스럽다는 평이 많았다. Educational Codeforces Round를 치는 것 같다는 평이 많았다. 나도 동의한다.

이 정도면 TMI를 충분히 해서 잘 가려졌을 것 같으니 이제 본론으로 들어간다.

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)$ 도 어렵지 않다.

B번 문제의 만점 풀이와, C번 문제의 풀이는 구사과 블로그 에서 계속됩니다.

댓글 댓글 쓰기