BOJ 31226 - 고슴도치 그래프 2

 

 

 

문제 링크

• https://www.acmicpc.net/problem/31226
• https://www.acmicpc.net/problem/23049

문제 풀이 (시간에 따라서 적어 놨던 글을 공개한 것입니다. 두서가 없을 수 있습니다.)

 

임의의 점에서 최대로 이동하면 사이클에 포함된 임의의 노드의 번호를 알 수 있다. 우린 이 임의의 노드에서 시작해 보자.
이 사이클에 포함된 임의의 번호를 $\text{s}$라고 하자.

개수가 N일 때, 제곱근 분할법을 사용하면, 무조건 겹치게 할 수 있기 때문에, $2\sqrt{N}$의 질의로는 가능하다.

24. 3. 4
문제에 대해 접근방법을 바꿔야 할 것 같다고 생각했다. 문제를 보면, 쿼리를 날릴 때 거리가 굉장히 길다.
왜 길까?

정답은 1부터 1,000,000까지 있다.

$1,000,000!$ 을 $k$라고 하자. 정답의 배수는 그 자신으로 돌아온다. 그러므로, $\text{Query}(s, k) = s$ 가 된다. 

이렇듯, 임의의 정답의 배수값 $A$값을 찾고, 소인수 분해를 하며, 질문을 하면 30번 내의 질의정도로, 정답이 되는 값을 찾을 수 있다.

답이 될 수 있는 정답의 경우의 수를 적절히 압축하여 곱한 뒤, 거리 쿼리를 날리고 자기 자신으로 되돌아오는 쿼리를 적절히 빨리 발견하여, 소인수 분해를 통해 빠르게 얻는다…라고 생각했다.

 

하지만, 거리의 제한은 $10^{18}$이고, 적당히 압축한다고 해도, 엄청나게 많이 수를 곱해야 하므로, 턱도 없는 풀이 발상이다.

 

하지만, 확실한 것은, 문제를 바꾸어서 $\text{Query}(s, x) = s$ 를 뱉는 $x$들중 하나를 찾는 것을 목표로 하는 게 더 쉽게 문제풀이에 접근할 수 있다는 것이다.

24.3.24 solved

 

무려 마지막, 글의 작성으로부터 20일이 지난 지금, 풀 수 있게 되었다.

제곱근 분할법은 엄청난 힌트가 되었다.

 

사이클에 속해있는 임의의 점 $s$에서 시작을 하자.

 

일단 확실한 것 하나는, 우리는 정답을 알아내기 위해서는, $\text{Query}(s, x) = \text{Query}(s, y)$ 인 $x$, $y$를 발견해야 한다는 것이다.

$s$로부터 3칸, $s$로 부터 10칸 건너뛰게 되면, 우린 사이클이 3인지 10인지 확인한 것뿐만 아니라 사이클이 7인지도 확인 한 것이 된다.

왜냐면 사이클이 7일 경우, s로부터 3칸 간 것과 10칸 간 것의 도착지점은 같을 것이기 때문이다. 즉, 이 상태에서 s에서 15칸을 건너뛴다면,12, 5, 15 또한 사이클인지 확인하게 되는 것이다.

 

이 발상을 이용하여, 제곱근 분할법이 왜 자명하게 답을 찾는지 다시 한번 생각해 볼 수 있었다.

$$A = \big[1, \cdots, \sqrt{V}\big], B = \big[\sqrt{V}, 2\sqrt{V}, \cdots, V \big]$$
A그룹과 B의 그룹의 수의 차이로 만들 수 있는 수는 $\big[1, 10^6\big]$ 전 범위이다. 전 범위가 사이클인지 확인했기에 자명하게 정답을 찾아낼 수 있는 것이다.

 

자, 정리를 한번 하고 넘어가는 게 좋을 것 같다. 우리가 질문하는 쿼리들을 순서대로 묵은 쿼리열, 

 

$$Q = [q_1, q_2, \cdots, q_K]$$ 가 존재하여, 이때 우리가 사이클인지 확인한 숫자들은 

 

$$Z = \big\{\; |q_i - q_j| \; \big| \;  i \leq K \; \text{ and } \; j < i \big\} \cup Q $$

 

인 $Z$의 원소들을 확인한 것이 된다.

하지만 굳이 $[1, V]$의 모든 수가 사이클인지 확인해야 하는 것은 아니다. 이전 풀이에서 생각했듯이, 배수들을 찾아도 괜찮다. 구간 [1, 500000]의 수들은 [500001, V] 구간에 배수를 갖는다. 그러므로, [500001, V] 구간의 수를 전부 확인할 것이다. 

 

우리가 확인해야 할 정답이 될 수 있는 경우는 50만 개가 된다. 그리고 질문할 수 있는 거리 x = 10^12.4 이므로, 구간 내의 수들을 두 개씩 곱해서 25만 개의 수로 줄일 것이다.

 

우린 여기서, 제곱근 분할법을 응용할 수 있다. 위의 제곱근분할의 예시에서, 그룹 A는 수를 만들기 위해서 일정하게 수를 빼줘야 하는 prefix형태를 띠고 있고, 그룹 B는 모든 수를 만들기 위해서 중간중간 기준이 되는 수들이 들어가 있다.

 

25만 개의 수를 만들기 위해서, 이 방식을 똑같이 응용할 수 있다.

수를 작은 수부터 순서대로 곱한 다음, 2차원상의 매트릭스 형태로 나열하면, 열에 상관없이 수의 차이가 일정해지는 매트릭스 형태의 2차원 배열이 나온다.

Prefix형태로 빼줄 수 있는 수들 500개를 넣어주고, 열에 있는 모든 수 500개씩을 각각 만들 수 있는 기준이 되는 수 500개를 넣어주면,

 

25만 개의 수를 전부 커버할 수 있다. 이것은 고슴도치 1의 풀이이다.

Q=800, x < 5e18일 때, 이번엔 모든 홀수만 전부 넣어보자.

구간 [1,999999]의 모든 홀수를 전부 확인해보자.
홀수의 곱은 홀수이다.
곱셈으로 값을 증가시키며, 홀수가 되는 가장 작은 홀수는 3이다.
그러므로, 구간 [1, 333333]은 [333335, 999999]에 배수를 갖는다.
따라서 [333335, 999999]의 구간의 홀수를 전부 확인해 보자.

수가 생각보다 적기 때문에 409개의 prefix와 기준이 되는 수 410개를 만들 수 있다.

우리는 존재하는 모든 홀 수를 만들었기 때문에, 단순히 모든 매트릭스에 2의 19승을 곱하는 것 만으로, 모든 짝수도 포함시킬 수 있다