APIO 2020 Open Contest

솔직히 아쉽긴 한데 그래도 완전 망한 성적은 아니어서 만족하는 중. C를 못 푼건 그렇다치고 B는 100 맞았어야 했다.

중간에 바빠서 정신 없었던 것도 있지만 어쨌든 B에 대한 접근이 정해와 조금 많이 떨어져 있어서 100은 못 먹었을 듯.

A. 벽 칠하기

각 길이 $m$ 구간이 "칠하는 것이 가능한 구간"임을 판별할 수 있다면, 그 후의 계산은 간단한 그리디 알고리즘으로 할 수 있다.

이제 이걸 판단하는 것이 중요한데, 이제부터 색깔 $i$를 좋아하는 사람의 집합을 $S_i$라 하자.

그럼 구간 $[i, i+m)$이 색칠 가능한 것은, $t \in S_{C[i]}$, $t+1 \in S_{C[i+1]}$, $\cdots$, $t+m-1 \in S_{C[i+m-1]}$을 만족하는 정수 $t$가 존재하는 것이다. 

모든 인덱스는 $\pmod{m}$으로 본다. 물론, 조건 판별을 이대로하면 고통스러울 것이 뻔하다. 그러니 접근을 바꿔보자.

생각해보면, 저 인덱스들의 차이는 $i-t$로 동일하다는 것을 알 수 있다. 그러니 이를 활용하면 뭔가 보일 것 같다.

즉, $u \in S_{C[v]}$에 대하여 $v-u$의 카운트를 $1$씩 증가시키면, 카운트가 $m$인 정수가 존재하는지 판별하면 된다.

이제 이걸 효율적으로 관리할 방법을 생각해보자. $[0, m)$에서 시작되는 구간을 오른쪽으로 움직여보자.

$[i. i+m)$에서 $[i+1, i+m+1)$로 가려면, $S_{C[i]}$에 있는 정보를 제거하고 $S_{C[i+m]}$의 정보를 추가해야 한다.

우리가 지원해야 하는 연산은 값 하나를 바꾸고, 전체의 최댓값을 뽑아내는 것이다. 이는 세그먼트 트리로 할 수 있다.

또한, 각 $i$에 대하여 $S_{C[i]}$는 $\sqrt{400000}$ 이하이므로, 업데이트 횟수가 $N \sqrt{400000}$ 이하가 된다.

그런데 내 경험상 세그먼트 트리를 붙이면 TLE가 나고, 로그를 떼어내야 AC를 받을 수 있다.

로그를 떼는 방법은 간단한데, 필요한 것이 최댓값이 $m$인지만을 확인하는 것임을 사용하면 된다.

그냥 $c[x]$를 카운트가 $x$인 정수의 개수, $cnt[x]$를 $x$의 카운트 값이라고 정의하면 업데이트가 상수 시간에 된다. 

B. 자매 도시

Subtask 1은 각 연결컴포넌트가 path 아니면 cycle이다. path이면 당연히 실패하며, cycle이면 그 중 간선 길이 최댓값이다.

Subtask 2는 그래프가 매우 특수한 형태를 갖는다. 경우를 나눠서 생각하면 간선 길이 중 최소 3~4개 정도만 생각하면 된다는 사실을 알 수 있다. 

이는 원하는 방식으로 적당히 구현하면 된다. 나는 멀티셋 썼다. 근데 은근 케이스 생각하기 헷갈리긴 했다 ㅋㅋ

Subtask 3, 4를 위해서는 간단한 관찰이 필요한데, 바로 필요충분조건이 연결성 및 (사이클 존재 또는 차수 3 이상 정점 존재)라는 것이다.

물론, 사이클이 단순 사이클이 아니면 차수 3 이상 정점은 무조건 존재하게 되어있다. 이제 생각하기 편하다.

이제 문제를 각 쿼리당 $\mathcal{O}(N+M)$ 시간에 해결할 수 있다. 간선을 작은 것부터 순서대로 이으면서, disjoint set으로 위 사실들을 관리하면 된다. 

Subtask 5를 위해서 나는 트리 DP를 활용했다. 오프라인 풀이가 너무 자명해서 small-to-large 같은 게 먹히나 생각을 했었는데, 뭔가 아닌 것 같아서 트리를 긁기로 했다. 근데 저 방향이 정해여서 너무 아쉽다 ㅋㅋㅋ 트리라도 맞은 걸 다행이라고 생각해야겠다.

여기서 좋은 점은 사이클 존재의 경우를 생각하지 않아도 된다는 것이다. 연결성과 차수 3 이상 정점만 다루면 된다.

연결성을 위한 "최대 간선 길이의 최솟값"과, 차수 3 이상 정점을 위한 "최대 간선 길이의 최솟값"을 구한 뒤 최댓값을 취하자.

첫 번째 문제는 어렵지 않고, 잘 알려진 편이다. MST를 찾아주고, 거기서 경로 최댓값을 찾으면 충분하기 때문이다.

그러니까 단순하게 크루스칼 + Sparse Table을 열심히 구현하면 이 부분을 큰 문제 없이 해결할 수 있다.

두 번째 문제는 엄청 어려운 건 아닌 것 같지만 트리 DP 근본이 없는 수준인 나에게는 힘들었다.

우선 차수 3 이상 정점이 어디서 나올 것인가에 대해서 논의를 할 필요가 있다. 쿼리로 들어온 정점이 $X, Y$라고 하자. 

 

우선 공통된 것이 있다. $X$와 $Y$ 사이의 경로에서 차수 3 이상 정점이 나올 수 있다.

이 정점들은 (단, $X, Y$ 제외) $X, Y$가 연결된 시점에서 이미 차수가 2 이상인 것이 보장되므로, 간선 하나만 더 그으면 끝이다.

여기서 생각을 해보면 중요한 것은 각 정점에서 뻗어나오는 "3번째로 길이가 작은 간선의 길이"가 된다.

그러니 첫 번째 문제와 같은 방법으로 Sparse Table을 적용하면 이 경우를 해결할 수 있다. 

그런데 $X, Y$는 조금 다른 점이 있다. 밑으로 내려갈 수도 있기 때문이다! 잠시 $Z = \text{lca}(X, Y)$라고 하자.

$Z \neq X$라면, 차수 3 정점을 찾기 위해서 $X$에서 트리를 내려가 정점 $W$에 도착한 뒤, $W$에서 가지를 2개 치는 방법이 있다.

이 경우 필요한 최대 길이는 $X$에서 $W$로 내려가는 길이 중 최대, 그리고 $W$의 가지 중 두 번째로 작은 것이 되겠다.

이러한 경로로 가능한 것 중 필요한 최대 길이의 최솟값을 구해야 하는데, 이는 트리 DP로 미리 전처리를 할 수 있다.

$Z \neq Y$인 경우에도 이러한 계산을 하고, 이를 쿼리를 답할 때에 고려해야 한다. 

마지막으로, $Z=X$거나 $Z=Y$인 경우를 생각할 필요가 있다. 이 경우에는 위로 올라갈 수 있다!

앞선 경우와 큰 차이는 없지만, 개인적으로는 조금 헷갈렸다. 비슷한 스타일의 DP를 한 번 더 해주면 된다.

매우 고통스러운 풀이였는데, 이걸 어쨌든 짜서 서브태스크를 긁었다는 게 다행이다. 솔직히 틀릴 것 같았다.

이 풀이를 일반적인 경우로 확장하려고 했는데, 단순 사이클을 다루는 것이 어마어마하게 힘들더라 ㅠㅠ   

C. 즐거운 행로

Subtask 1, 2는 우선 트리 전체의 구조를 $N^2$번의 쿼리로 구한다. (모든 거리를 알면 복원은 자명)

그 후, 트리의 지름을 잡고 가능한 정점 중 가장 먼 곳을 반복적으로 사용하면 된다. 

Subtask 3은 이 과정을 전형적인 이진트리에서 하면 된다. 위 과정을 그대로 적용하되, 트리의 높이가 작다는 점을 이용한다.

그냥 각 정점에 대해서 "내 왼쪽에 있는 정점" / "내 오른쪽에 있는 정점"의 집합을 관리하면 된다.