ABC 450 업솔빙

E: Fibonacci String

대회때는 고민만 하다가 시간에 치여서 결국 풀지 못했던 문제였는데, 대회가 끝난 뒤 다시한번 고민해보았었다.

여전히.. 풀이는 떠오르지 않았고 에디토리얼에서 힌트를 얻고자 보았는데.. (태그만 볼려고 했다)

“엥?? 재귀??? $S_{10^{18}}$까지 구해야하는데 재귀를 쓴다고? $O(n)$으로 구해도 터지지 않나??”

그렇게 계속 그점에 꽂혀있던 중 갑자기 든 생각..

“범위가 $10^{18}$까지라면 사실 $S_{10^{18}}$까지 구할 필요 없이.. 문자열의 길이가 $10^{18}$이 되는 행까지만 구하면 되는게 아닐까?”

그리고 그게 실제 에디토리얼에 장황하게 풀어져 있던 내용이었다.

문자열 X와 Y가 1임을 가정할때 $S_{88}$까지만 구해도 되는 것이다..!

이거랑 재귀가 쓰이는데는 이유가 있는데…추가적으로 여기서 내가 생각치도 못한 발상이 또 나온다.

바로 예전에 여러번 문제로 만나왔던 누적합에서 쓰이던 기법!

[a, b] 구간의 합을 구할 때 sum(0, b) - sum(0, a - 1)을 이용하던 그것.

이 문제에서 구간의 개수를 물어볼때 위를 이용할 수 있었던 것이다.

이제 [a, b]에 대해서 b까지의 개수를 세면 되는 문제로 바뀌었는데, 업솔빙하면서 이걸 생각해내기 어려워서 에디토리얼을 봤다.

에디토리얼에선 다음과 같이 규정하고 있는데

사실 간단하게 풀어 쓰자면, F(n) = F(n - 1) + F(n - 2) 꼴이므로, 찾으려는 위치가 |F(n - 1)| 보다 크냐 작냐에 따라서 F(n - 1)을 탐색할지 F(n - 2)를 탐색할지를 나눠서 들어가는 식으로 구현이 된다.

이로서 최종적으로 a - z에 대해서 각각의 X와 Y에서의 개수를 미리 전처리 하고, $S_{i}$항의 문자열 크기를 각각 전처리해준 뒤, 각 $S_{i}$항에 대해서도 전처리를 해준 뒤, 쿼리마다 재귀함수 Fn을 호출해서 각각의 값을 얻어주면 답을 구할 수 있다.

여담

첫 구현때는 c의 개수를 찾는 연산을 쿼리마다 수행해줬었는데.. 이러면 원래 시간복잡도 상으로 시간 초과가 맞다. 다만.. 앳코더의 데이터가 약한건지 1100ms에 돌기는 했었다.