Codeforces Round 862 (Div. 2)

A. We Need the Zero

code

 

길이가 \(N\)인 배열이 주어진다. 이제 이 배열의 모든 값에 특정 \(x\)를 XOR해서 배열의 모든 원소를 XOR한 값이 0이 될 수 있는지 확인하고 싶다. 가능하면 XOR 결과가 0이 되도록 하는 \(x\)를, 불가능하면 -1을 출력해야 한다.

XOR을 많이 다뤘다면 빠르게 풀 수 있는 문제이다. XOR의 가장 큰 특징은 \(a \oplus x \oplus x = a\)라는 점이다. 일단 처음 주어진 배열의 모든 원소의 XOR값을 \(A\)라 하고, 모든 원소에 \(x\)를 XOR하자. 만약 \(N\)이 짝수라면 모든 원소의 XOR값은 여전히 \(A\)일거고, \(N\)이 홀수라면 XOR값은 \(A \oplus x\)가 될 것이다.

따라서 \(N\)이 짝수인 경우에는 \(A\)가 처음부터 0이 아니면 불가능하므로 -1을 출력해야 하고, 그렇지 않으면 아무 정수나 출력하면 된다. \(N\)이 홀수라면 \(A\)를 출력하면 된다.

 

B. The String Has a Target

code

 

문자열이 하나 주어진다. 이제 문자열의 특정 글자를 맨 앞으로 옮기는 것을 한 번 해서 가능한 사전순으로 가장 빠른 문자열을 만들어야 한다.

일단 맨 앞으로 오는 글자는 사전순으로 가장 빠른 글자를 가져와야 한다. 즉 a가 있으면 a를 가져오고, a가 없으면 b를, b도 없으면 c를,... 이런 식으로 가져와야 한다.

그렇다면 가장 빠른 글자가 여러 개라면 무엇을 가져와야 할까? 정답부터 말하자면 가장 뒤에 있는 글자를 가져와야 한다. 문자열 \(bbbabbbba\)를 생각해보면 쉽게 알 수 있다. 중간에 있는 \(a\)를 가져오는 것보단 뒤에 있는 \(a\)를 가져오는 게 더 사전순으로 빠르다.

c++의 erase 함수를 활용하면 매우 빠르게 구현할 수 있다.

 

C. Place for a Selfie

code

 

총 \(n\)개의 원점을 지나는 1차함수가 있다. 이제 \(m\)개의 2차함수가 주어지고 각 2차함수에 대해 2차함수와 만나지 않는 1차함수가 존재하는 지를 출력해야 한다. 만약 존재하면 YES와 해당 1차함수의 기울기를, 존재하지 않는다면 NO를 출력해야 한다.

일단 \(n\)개의 1차함수의 기울기 \(k\)를 배열에 저장하고 정렬해두자. 주어진 2차함수의 계수가 각각 \(a, b, c\)일때, \((b-k)^2 < 4ac\)인 \(k\)를 하나 찾으면 된다. 수식을 잘 보면 \(b\)와 가장 가까운 \(k\)를 찾고, 이 \(k\)가 부등식을 만족하면 YES와 해당 \(k\)를, 만족하지 않으면 NO를 출력하면 된다.

가장 가까운 \(k\)는 이분탐색이나 lower_bound 함수를 이용하여 \(b\)이상인 것중 가장 작은 \(k\)와 \(b\)이하인 것중 가장 작은 \(k\)를 찾은 뒤 둘 중 \(b\)에서 가까운 \(k\)를 선택하면 된다.

 

D. A Wide, Wide Graph

code

 

정점이 \(N\)개인 트리가 주어진다. 이제 이 트리에서 거리가 \(k\)이하인 정점들은 모두 연결한 그래프의 연결 요소의 개수를 1이상 \(N\)이하의 모든 \(k\)에 대해서 계산해야 한다.

일단 특정 정점들의 집합 \(V_k\)를 생각해보자. 이 집합에 있는 정점 \(v\)는 정점 \(v\)와 거리가 \(k\) 이상인 정점이 트리에 존재해야 한다. 그렇다면 \(V_k\)에 있는 정점들은 모두 연결되어 있다. \(V_k\)에 없는 정점들은 모두 연결되어 있지 않을 것이다. 따라서 모든 \(k\)에 대해 \(V_k\)의 크기 \(|V_k|\)를 구한다면 연결 요소의 개수는 \( N-|V_k|-1\)가 된다.

각 정점에 대해서 가장 먼 정점까지의 거리를 구해놓았다고 해보자. 그렇다면 \(|V_k|\)는 거리가 \(k\) 이상인 정점의 개수이다. 가장 먼 정점을 구하는 방법은 트리의 지름을 활용하면 된다.

트리의 지름을 구하고 두 정점을 \(p_1, p_2\)라 하자. 만약 가능한 지름이 여러가지라면 아무 두 정점을 잡아도 된다. 이제 특정 정점 \(v\)에서 가장 먼 정점까지의 거리는 \(max( d(p_1, v), d(p2, v))\)로 계산할 수 있다. 즉, \(p_1\)과 \(v\)의 거리, \(p_2\)와 \(v\)의 거리를 구하고 둘 중 max값을 취하면 된다는 것이다.

 

E. There Should Be a Lot of Maximums

code

 

정점이 \(N\)개인 트리가 주어진다. 그리고 각 정점에는 값 \(a_i\)가 할당되어 있다. 이제 각 간선에 대해 간선을 제거하고 트리를 2개 얻은 뒤 두 트리의 MAD 값을 계산할 것이다. 각 트리의 MAD값은 트리에서 2번 등장하는 값 중 가장 큰 값이고, 두 트리의 MAD값은 각 트리의 MAD값 중 큰 값이다. 만약 2번 이상 등장하는 값이 없다면 MAD는 0이 된다. 모든 간선에 대해 해당 간선을 제거했을 때 트리의 MAD값을 출력해야 한다. 편의상 \(a_i\)값은 좌표압축을 진행한 결과라고 하자.

일단 우리가 고려해야 할 건 정확히 2번 등장하는 \(a_i\)값들이다. 3번 이상 등장하면, 트리를 어떻게 쪼개도 최소한 한 트리에는 2번 등장하고, 1번 등장하면 어떻게 쪼개도 한 트리에 2번 등장할 수 없기 때문이다. 따라서 트리에서 3번 등장하는 값들 중 최댓값을 \(minAns\)라 정의하고, 그 이후에는 고려하지 않을 것이다.

이제 간선을 자른 후 2번 등장하는 값들만 고려해서 MAD를 계산해보자. 한 간선에 대해서는 \(O(N)\)으로 쉽게할 수 있다. 일단 편의상 루트가 있는 트리라 하자. 그렇다면 간선을 제거한다면 하나의 서브 트리와 나머지 부분으로 나눌 수 있을 것이다. 이제 이 서브 트리에서 0번 또는 2번 등장하는 값들 중에서 가장 큰 값을 찾으면 된다. 하지만 이는 충분하지 않은 풀이이다. 간선이 \(O(N)\)개이기 때문에, 모든 간선에 대해 계산하면 \(O(N^2)\)이 되기 때문이다.

하지만 small to large 테크닉을 쓰면 이 시간복잡도를 \(O(N \log^2 N)\)으로 개선할 수 있다. 그 방법은 내가 이전에 만들었던 문제인 트리의 MEX와 매우 유사하다. set을 이용하여 1번 이상 등장한 값들을 저장해두면서 관리하면 된다. small to large 테크닉을 적용하려면 작은 sub 문제들을 합쳐서 큰 문제를 풀 수 있어야 한다. 이제 sub문제들로 큰 문제를 어떻게 풀지 생각해보자.

먼저 문제를 어떻게 관리할 지를 생각해보자. 나의 경우, 서브 트리에 있는 모든 정점들을 배열에, 1번 이상 등장한 값들을 set에 저장해두고, 0번 등장한 값들 중 최댓값과 2번 등장한 값들 중 최댓값을 저장하였다. 0번 등장한 값들 중 최댓값은 트리의 MEX 문제 테크닉을 그대로 적용하면 된다. 0번 이상 등장한 값 중 최댓값을 \(ans_1\)이라 하자. \(ans_1\)은 정점이 추가될 때마다 점점 작아지게 된다. 따라서 정점이 추가될 때, set에 해당 값을 추가하고, \(ans_1\)이 set에 있으면 \(ans_1\)을 1씩 감소시키면 된다. 2번 이상 등장한 값 중 최댓값을 \(ans_2\)라 하면 이 값은 정점이 추가될 때 항상 증가하게 된다. 따라서 특정 값이 추가할 때, 만약 set에 이미 있다면 \(ans_2\)값을 추가한 값과 \(ans_2\)중 더 큰 값으로 갱신해주면 된다. 이렇게 특정 값이 추가될 때 정답을 어떻게 갱신할 지를 정의하였다. 이 과정의 시간 복잡도는 \(O(\log N)\)으로, small to large의 시간 복잡도가 \(O(N\log N)\)이므로 총 시간 복잡도 \(O(\log^2 N)\)으로 문제를 해결할 수 있다. 글만으로는 이해하기 어려운 부분이 있을텐데, 코드를 보면 잘 이해할 수 있을 것이다.

그와는 별개로 전처리를 해야 할 부분이 좀 많다. 일단 각 간선의 index를 기록해야 정답을 올바른 순서로 출력할 수 있으므로 index를 저장하고, index대로 정답을 다시 배열해서 출력하는 전처리를 해야하고, 배열 \(a\)또한 좌표압축해서 계산하고 답을 출력할 땐 원래대로 변환해서 출력하는 부분을 전처리 해야 한다. 따라서 코드 구현량은 꽤 많아지지만, 핵심 부분인 small to large 부분만 보면 구현랑이 그렇게 많지는 않았던 것 같다. 그래서 복잡한 구현에 비해 그래도 꽤 정확하게 구현할 수 있었다.

답을 출력할 때, 맨 처음에 계산해둔 \(minAns\)도 고려해야 한다는 점을 까먹지 말자. 나는 이를 까먹고 한 번 틀렸다.

 

후기

최근에 debug함수를 구현해 두었다. E번 코드를 보면 알겠지만, 내 컴퓨터에서 컴파일할 때에만  debug 코드가 작동한다. debug 함수는 간단하게 입력받은 변수를 이쁘게 출력하는 코드이다. debug를 재귀 함수의 형태로 구현해놔서 vector, pair, queue, stack같은 것들을 바로 출력해준다. D번과 E번을 풀 때 debug 함수를 적극적으로 활용해서 빠르게 디버깅 및 제출을 할 수 있었다. E번은 대회 종료 3분전에 제출해서 맞았기 때문에 이 함수를 구현하지 않았다면 아마 못풀었을 것이다. 이런 local에서 쓸 수 있는 디버거를 미리 구현해두면 매우 편한 거 같다. 시간 된다면 set, map의 디버거를 구현해두고, 블로그에 자동으로 code link 추가 및 자동 formatting도 해두고 싶다.

debug() 사용 예시

실행 결과 - 최대한 깔끔하게 출력하도록 구현했다.