题解 · 949

题解

$1$ 부터 $k$ 까지 외쳤을 때 짬뽕 문자열의 길이를 $\mathrm{len}(k)$ 라 합시다. $\mathrm{len}(k) \ge L$ 인 가장 작은 $k$ 를 이분탐색으로 찾으면, $L$ 번째 문자는 $k$ 번째 차례에 있습니다.
$\mathrm{len}(k)$ $len (k)$ 는 $1$ $1$ 부터 $k$ $k$ 까지의 수를 세 종류로 나누어 구합니다.
- 두 자리 이상이면서 맨 앞자리와 일의 자리가 모두 $3$ , $6$ , $9$ 중 하나인 수: , 글자
JJAM과 PPONG은 JJAM부터 번갈아 나오고, JJAMPPONG은 이 순서에 영향을 주지 않습니다. 그래서 둘째 종류의 수가 $c$ 개이면 그 길이 합은 $4\lceil c/2 \rceil + 5\lfloor c/2 \rfloor$ 입니다.
각 종류의 개수는 자릿수별로 맨 앞자리와 일의 자리를 따져 세면 됩니다. 한 번 세는 데 $\mathcal{O}(\log k)$ 가 듭니다.
$k$ 를 찾은 뒤에는 $k$ 번째 차례부터 수를 하나씩 늘려 가며, 외칠 수나 단어를 $R - L + 1$ 글자가 될 때까지 이어 붙입니다. 이때 $k-1$ 번째 차례까지 나온 JJAM·PPONG 개수로 다음 단어를 정합니다.
시간복잡도는 $\mathcal{O}(N(\log^2 R + R - L))$ 입니다.