[18842] Chameleon's Love
마지막 수정 시각: 2021-07-25 21:49:28
독특한 인터랙티브 문제. 내가 문제 해결을 위해 접근했던 과정을 순서대로 정리했다.
\( O(N^2) \) 풀이
비교적 쉽게 성질을 탐색할 수 있는게 둘을 짝지어서 쿼리했을 때 경우를 살펴보는 것이므로, 각 쌍에 대한 쿼리 값이 어떻게 나오는지 생각해봤다. 정리를 쉽게 하기 위해 몇 가지 노테이션을 먼저 정의하고 시작하자.
- \(S(i)\) : \(i\)와 같은 원본색을 지닌 반대편 집합의 카멜레온.
- \(L(i)\) : 문제에서 정의된, \(i\)가 좋아하는 카멜레온
이렇게 정의하고 묶는 경우를 구분해보면 다음과 같은 케이스들이 있다.
- \(i\)와 \(S(i)\) 를 묶는 경우 : 쿼리 결과가 1
- \(i\)와 \(L(i)\) 를 묶는 경우 : 이 경우는 다시 두 가지로 생각할 수 있다. \(L(L(i)) = i\)인 경우, 쿼리 결과가 2가 나오고 그렇지 않다면 1로 나온다.
- 그 외의 경우 : 쿼리 결과가 2
따라서, 두 쌍씩 묶었을 때 쿼리 결과가 1이 나오는 것들이 뭔가 단서를 제공해준다는 것을 알 수 있다. 여기서 만약 \(L(L(i)) = i\)를 만족하는 경우, 쿼리 결과가 1이 나오는 쌍이 \(i\)와 \(S(i)\)쌍으로 고정된다. 그렇지 않다면, \(i\)에 대해 쿼리가 1이 나오는 수는 다음 세 종류가 있다.
- \(S(i)\)
- \(L(i)\)
- \(L(c) = i\) 를 만족하는 \(c\)
즉, 쿼리 결과가 1이 나오는 경우의 수는 각 수에 대해 1가지거나 3가지거나 둘 중 하나로 나뉜다. 경우의 수가 한 가지 밖에 없다면 그 쌍이 곧 서로 원본색이 같은 쌍이 되므로, 경우의 수가 세 가지인 경우에 대해서만 추가적인 고려를 해보면 된다.
이 때 \(S(i), L(i), c\) 세 수에 대해 다음 세 가지 쿼리를 진행해보면 셋 중 \(L(i)\)가 무엇인지 판단할 수 있다.
- \(Query(i, S(i), L(i))\) : 2를 반환
- \(Query(i, S(i), c)\) : 1을 반환
- \(Query(i, L(i), c)\) : 2를 반환
즉, 결과가 1이 나오는 쿼리에 대해 세 수 중 그 쿼리에 포함되지 않은 수가 \(L(i)\)임을 알 수 있다.
이렇게 할 경우 모든 카멜레온에 대해 \(L(i)\)가 무엇인지 알 수 있고, 모든 카멜레온에 대해 \(L(i)\)가 무엇인지 알면 \(c\)가 무엇인지도 알 수 있으므로(\(c\)는 \(L(c) = i\)를 만족하는 수이므로), \(S(i)\)를 찾을 수 있다.
따라서, 최대 \( 2N^2 + 3N \) 번의 쿼리로 답을 구할 수 있고, 이 풀이를 통해 40점을 획득할 수 있다.
Subtask4
이 경우 \(X\) 집합은 앞 \(N\)개, \(Y\) 집합은 뒤 \(N\)개임이 정해져 있다.
이 때 각각의 원소에 대해 \(S(i), L(i), c\)를 구할 수 있다면 위의 \(O(N^2)\) 풀이에서 언급한 방법을 통해 \( 4N \) 번의 쿼리면 문제를 해결할 수 있다. 따라서 적절한 횟수의 쿼리를 통해 각 \(i\) 번째 원소의 \(S(i), L(i), c\)를 구하는 방법을 생각해보자.
쿼리 횟수를 줄이는 방법으로는 이분탐색이 가장 일반적이니 이분탐색으로 접근해본다. \(i\)번째 원소는 무조건 포함하고, \(N+1\)번 원소부터 어떤 \(r\)번 원소까지를 포함했을 때 쿼리 결과값이 어떻게 변하는지를 보자.
- 먼저 \(L(L(i)) = i\)가 성립하는 경우, \(i\)와 \(N+1\) 부터 \(2N\)까지를 모두 포함한 쿼리를 하면 결과는 (쿼리를 보낸 집합 크기 - 1)이 나온다. 이 경우, \(S(i)\)를 포함하는 구간부터 쿼리 값이 쿼리를 보낸 집합 크기-1이 되므로 이분탐색 한 번에 \(S(i)\)를 찾을 수 있다.
- 그렇지 않은 경우, 영역이 (쿼리를 보낸 집합 크기와 결과가 동일한 영역) / (쿼리를 보낸 집합 크기 - 1)이 쿼리 결과가 되는 영역 / (쿼리를 보낸 집합 크기 -2)이 쿼리 결과가 되는 영역의 세 부분으로 나뉜다. 두번의 이분탐색을 통해 각 영역의 시작점을 찾고, 그 각 사이 영역에 대해 다시 이분탐색을 한 번 더 하면 필요한 값을 모두 찾을 수 있다.
이렇게 할 경우 각 원소에 대해 최대 약 \(30\)번의 쿼리(\(3log_2N\))가 필요하고 원소가 \(500\)개이므로 \(15000\)번의 쿼리면 필요한 값을 모두 구할 수 있고, 그 이후 답을 탐색하는데에는 \(1500\)번 정도의 쿼리면 충분하므로 주어진 횟수 내에 문제를 해결할 수 있다.
main solution
위 풀이에서 \( X \) 집합과 \( Y \) 집합을 쉽게 구분할 수 있는 방법을 찾으면 문제를 해결할 수 있다.
맨 처음 카멜레온부터 하나씩 고려해가면서 양 집합을 분류한다고 생각해보자. 각 카멜레온을 하나의 정점으로 생각하고 \(i\)번 정점과 \(S(i), L(i), c\) 번 정점 사이에 간선이 있다고 생각하면 이 그래프는 이분 그래프가 된다. 항상 반대편 집합하고만 간선이 있기 때문이다.
이 이분 그래프 상에서 같은 집합 안에 간선이 존재하지 않게 그래프를 반으로 나눠서 \(A\), \(B\) 두 집합으로 분류해 둔 상황이라고 하자. 여기서 새로운 원소 \(i\)가 추가됐을 때, 앞선 풀이에서 사용했던 방식과 마찬가지로 이분 탐색을 이용해 각각의 \(A\) 집합과 \(B\) 집합에서 \(i\)와 간선이 있는 정점을 찾을 수 있다. 이제 이렇게 찾아낸 정점들 사이에 간선을 연결해주자. 간선을 연결하고 나면 다시 DFS를 한 번 돌아서 조건을 만족하는 새로운 두 집합 \(A'\)과 \(B'\)을 만들 수 있다.
이렇게 새로 두 집합을 분류하고 나면 다시 \(i+1\)번 정점에 대해 동일한 과정을 반복해서 결과적으로 \(2N\)개의 원소를 모두 양 집합으로 분리해줌과 동시에 간선 정보도 모두 얻을 수 있다. 이 과정에서 필요한 쿼리 횟수는 앞서 Subtask4 풀이에서 간선을 찾는 과정과 비슷하게 되므로(\(O(NlogN)\)) 주어진 쿼리 횟수 내에서 충분히 수행할 수 있음을 알 수 있다.
간선 정보를 모두 알아내고 나면 그 이후 과정은 앞서 다뤘던 풀이와 동일한 방식으로 문제를 해결하면 된다.