Codeforces Round 766 (Div. 2)

A. Not Shading

가장 많은 operation을 수행해야 하는 경우도 2번이면 충분하다는 성질만 관찰하면 된다. 자연스럽게 다음과 같은 케이스분류를 할 수 있다:

• -1 을 출력해야 하는 경우: 불가능한 경우는 색이 칠해져있는 칸이 없는 경우
• 0 을 출력해야 하는 경우: 색을 칠하고자 하는 칸이 이미 색칠되어 있는 경우
• 1 을 출력해야 하는 경우: 색을 칠하고자 하는 칸을 제외하고, 해당 칸의 각 행과 열중 아무 칸이나 이미 색칠되어 있는 경우
• 2 를 출력해야 하는 경우: 그외 나머지 모든 경우

B. Not Sitting

먼저 수를 두는 Tina는 최선의 수를 두었을 때, 무조건 주어진 영역중 모서리에 자리할 수 있고, 해야만 한다. 모서리에 에 자신의 자리를 두고 핑크색 의자로 자신을 가두어야 의자를 효율적으로 사용할 수 있다. 나중에 수를 두는 Rahul은 Tina가 무조건 모서리에 자리한다는 것을 알기 때문에 어떤 칸에 자리하고자 할때, 각 모서리까지의 맨해튼 거리의 최대거리를 최소화 하는 방향으로 자리할 것이다. 그러면 각 칸마다 Rahul이 위치했다고 가정했을 때, 모서리중 해당 칸과 가장 거리가 먼 칸의 위치를 저장한다. 이는 BFS등을 이용하면 $O(NM)$에 계산 가능하다. 그리고 각 칸에 저장되어 있는 거리 값을 배열에 넣고, 오름차순으로 정렬한 후 출력하면 된다. 따라서 총 시간복잡도는 $O(NM log (NM))$이 된다.

이해가 어려울 수도 있는데, Tina가 핑크색 의자를 모서리에 가까운 칸부터 우선적으로 (그리고 대칭적으로) 채워나간다고 생각해보면 편하다.

C. Not Assigning

한 간선이나 연속된 두 간선의 가중합이 모두 소수여야 하는데, 해당 조건을 보고 다음과 같은 성질을 관찰할 수 있다:

• 가중치가 소수인 두 간선의 가중합이 짝수인 소수인 경우는 없다. 그러므로 두 연속된 간선의 가중합은 무조건 홀수인 소수가 되어야 한다.
• 가중치가 소수인 두 간선의 가중합이 홀수인 소수인 경우는 한 간선의 가중치가 짝수, 다른 간선의 가중치가 홀수인 경우가 되어야 한다.

그런데 어떤 한 정점에 대하여 연결되어 있는 다른 정점이 3개 이상이라고 생각해보면, 모든 연속된 두 간선의 가중합이 소수가 되어야 한다는 조건을 지킬 수 없게 된다. 따라서 주어진 트리가 선형이 아니라면 -1을 출력해야 하는 유일한 상황이라고 말할 수 있다. 주어진 트리가 선형이라면 트리의 끝부터 끝까지 간선에 $2, 3, 2, 3, ...$ 과 같은 식으로 가중치를 달아주면 된다. 숫자 3이 마음에 들지 않는다면, 2와의 합이 여전히 소수인 소수중 아무 숫자를 골라서 사용하면 된다.

D. Not Adding

이 문제의 풀이는 연산을 통해 새롭게 수열에 추가되는 수는 절대 기존 배열 $a$의 원소의 최댓값 ($A$라고 하자) 을 넘지 않는다는 성질, 그리고 배열에 원소를 추가하는 연산의 순서에 상관없이 항상 최적해에 도달할 수 있다는 성질을 관찰하면서 부터 시작된다. 배열에 원소를 추가하는 연산은 상대적으로 "큰" 어떤 두 수 $a_i, a_j$ 에 대한 상대적으로 "작은" $gcd(a_i, a_j)$ 를 통해 이루어 지는데 ($gcd(a_i, a_j) \leq min(a_i, a_j)$), 따라서 $A$ 부터 $1$ 까지 역순으로 수를 순회하면서 이 수가 배열에 추가될 수 있는지 단 한번의 순회로 확인할 수 있다.

어떤 수 $a_i$에 대하여 배열에 새로 추가될 수 있는 수 인지에 대한 결정문제를 해결해보자. 이 문제는 현재 배열내에 존재하는 모든 $a_i$ 의 배수들의 GCD 값이 $a_i$인지 확인하면 된다. 유클리드 호제법을 사용하면 이 결정문제에 대한 답은 $O(A/i log(A))$ 에 해결할 수 있다. 범위 $[1,n]$ 내에 있는, $a$에 포함되지 않은 모든 수들에 대해 이 결정문제를 해결하면 된다. 시간복잡도의 $A/i$ 항은 조화수열을 이루고, 합은 조화수 $H_A=1/1+1/2+1/3+...+1/A=\sum_{i=1}^{A}1/i$ 이다. 조화수는 로그스케일로 근사할 수 있으므로, 총 시간복잡도를 다시 계산하면 $O(n+A (log A)^2)$이고, 이는 문제 해결에 충분히 짧은 시간복잡도이다.

수정 : 유클리드 호제법의 최악의 경우에도 $O(log A)$ 번의 단계만 거치기 때문에, 사실상 시간복잡도는 $O(n+A log A)$ 라고 볼 수 있다. 이미 GCD가 $a_i$ 인 경우에는 $O(1)$ 만에 GCD를 구할 수 있기 때문에, 대부분의 GCD 연산은 "생각보다" 훨씬 빨리 동작할 것이다. Editorial 댓글 을 참고하여 알게 되었다.

총평

아주 오랜만에 참여한 Virtual contest이다. A, B, C 까지는 제한시간안에 해결하였으나, D번은 제한시간이 끝나고 추가적으로 고민하여 해결하였다. 재밌는 문제들로 이루어진 좋은 set이라고 생각하는데, B번이 Div2 B답지 않게 조금 어려워 당황했다 ^^.

사실 D번 풀이의 시간복잡도가 내가 계산한 것보다 $O(log A)$ 만큼 작아서, 처음에 이해가 안가서 이런말을 했다:

GCD는 조상님이 구해주시나?? - 권도현

이제는 이해했지만, 아는만큼 보인다고... 재밌는 경험이였다.

• E, F번 문제에 대한 풀이는 문제를 해결하게 된다면 추가 예정