링크

문제 요약

알파벳 대문자로 이루어진 문자열이 주어진다. 이때 해당 문자열의 sub-sequence 중 왕의 이름과 일치하는 경우의 수를 구하는 문제이다. 다만, 주어진 문자열이 변화가 있으므로 변할 때 마다, 경우의 수를 계산하여 출력하도록 한다.

관찰

일단 가장 기본적으로 2가지 생각을 해볼 수 있다. 첫번째로 문자열에서 왕의 이름을 읽는 경우의 수를 구하는 방법을 알아야 하고, 두번째로 업데이트 쿼리를 효과적으로 대응해야 한다는 것이다. 업데이트 쿼리에 효과적으로 대응하는 방법은 세그먼트 트리를 사용하는 것이므로, 세그먼트 트리를 이용하기 위해 경우의 수를 계산하는 과정을 분할 정복으로 해결할 필요가 있다.

경우의 수를 계산할 때 분할 정복으로 계산을 하는 방법은 다음과 같다. 구간 $[L,R]$ 에 대하여 분할된 양쪽 구간을 $A, B$라 할 때 다음과 같은 점화식을 채우면 된다.

$D(i,j)=$왕의 이름 중 $i$번째 문자부터 $j$번째 문자까지를 읽어내는 경우의 수
$\displaystyle D(i,j)=D_A(i,j)+D_B(i,j)+\sum_{k=i}^{j-1} (D_A(i,k)\times{}D_B(k+1,j))$

따라서 위의 점화식을 이용하여 두 구간의 정답을 combine 할 수 있음을 알 수 있다. 또한 왕의 이름의 길이는 최대 5이므로 전체 분할 정복에 드는 시간 복잡도는 $O(5^3N)$ 이 된다. (물론 실제로 상수는 이것보다 작을 것이다.)

풀이

그렇다면 경우의 수를 계산하는 적절한 분할 정복을 만들었으므로, 해당 알고리즘을 메모이제이션 하면 세그먼트 트리가 구축될 것이다. 해당 세그먼트 트리는 1개의 노드를 업데이트 하는데, $O(5^3\log{N})$ 의 시간이 걸리게 된다. 상수를 rough 하게 잡았기 때문에 실제로는 시간이 덜 걸린다고 하더라도, 이 연산을 총 200만번 하면 당연히 결과는 TLE 이다. 따라서 업데이트 과정을 최적화할 필요가 있다.

업데이트를 최적화하기 위해서 관찰할 포인트는 쿼리로 업데이트 되는 노드들이 서로 연속적이라는 것이다. 따라서 세그먼트 트리를 선형시간에 구축하는 아이디어(=트리를 가장 깊은 곳부터 한 층씩 업데이트)를 그대로 차용하면, 대략적으로 모든 쿼리를 업데이트 하는동안 방문하게 되는 노드의 개수를 $O(Q\log{N}+\sum{ \vert{} S \vert{} })$ 로 줄일 수 있다. 이러한 방식으로 업데이트를 하게 되면 문제를 해결하는데 걸리는 시간은 $O(5^3(N+Q\log{N}+\sum{ \vert{} S \vert{} }))$ 가 되고, 이는 문제를 해결하는데 적절한 시간 복잡도이다.