ABC346 F - SSttrriinngg in StringString

Competitive Programming C++ AtCoder Algorithms

2024-03-24

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc346/tasks/abc346_f

원문 링크
https://atcoder.jp/contests/abc346/editorial/9644

먼저 \(k\)에 대해서 이분 탐색을 해봅시다.
그 다음, 어떤 \(k\)에 대해서 \(g(T, K)\)가 \(f(S, N)\)의 부분 문자열인지 아닌지에 대해 판정하는 방법을 생각할 수 있습니다.

\(S\)의 길이를 \(s\), \(T\)의 길이를 \(t\)라 두고, 문자열 \(X\)의 첫 \(i\)문자를 \(X[:i]\)라 하겠습니다.
또 \(T\)에 포한된 각각의 문자가 \(S\)에도 포함되어있는지를 판정합니다. (그렇지 않을 경우 확실히 \(0\)입니다.)

\(i = 1, 2, …, t\)에 대해 아래의 값을 구해 봅시다.

• \(\mathrm{iter}_i: g(T[:i], k)\)가 \(f(S, N) [:j]\)의 부분 문자열인 가장 작은 \(j\)

최종적으로 \(\mathrm{iter}_i\)와 \(N \times s\)의 대소를 비교하는 것으로 답을 구할 수 있습니다.
\(\mathrm{iter}_i\)부터 \(\mathrm{iter}_{i + 1}\)을 구하려면 \(f(s, N)\)의 \(\mathrm{iter}_{i + 1}\)번째 문자 이후에 \(T\)의 \(i + 1\)번째 문자가 \(k\)번째로 나타나는 위치를 구하는 것과 일치하므로, 이 문제는 다음의 형식을 가진 쿼리를 \(N\)번 처리하는 문제로 귀착됩니다.

• \(\mathrm{query}(a, b, c):\)양의 정수 \(a, b\), 문자 \(c\)가 주어질 때, \(f(S, N)\)의 \(a\)번째 문자 이후에 \(c\)가 \(b\)번째로 나타나는 것은 몇 번째 문자인가?

\(S\)에서 \(c\)가 나타나는 횟수를 \(\mathrm{cnt}_c\)라 둡시다. \(a\)가 \(s\)보다 큰 경우, \(\mathrm{query}(a, b, c) = \mathrm{query}(a - s, b, c) + s\)임을 이용해서 \(a \leq s\)인 경우로 귀착할 수 있습니다.
또한 \(b\)가 \(\mathrm{cnt}_c\)보다 큰 경우, \(\mathrm{query}(a,b, c) = \mathrm{query}(a + s, b - \mathrm{cnt}_c, c)\)임을 이용해 \(b \leq \mathrm{cnt}_c\)인 경우로 귀착할 수 있습니다.

따라서, \(a \leq s, b \leq \mathrm{cnt}_c\)의 조건을 토대로 쿼리를 처리하면 된다는 것을 알았습니다.
이러한 조건을 만족하는 \(\mathrm{query}(a, b, c)\)의 답은 \(2s\)이하가 되므로, 각 영어 소문자에 대해 그 문자가 \(f(S, 2)\)안에 나타나는 위치의 리스트를 전처리 해두면, 이분 탐색 등을 이용해 각 쿼리를 빠르게 처리할 수 있습니다.

따라서, 처음 \(k\)에 대한 이분 탐색을 포함해서, 전체 \(O(s \sigma + t \log N s)\)또는 \(O(s + \sigma + t \log s \log N s)\) (\(\sigma\)는 문자의 종류의 개수)등의 시간 복잡도로 이 문제를 풀 수 있습니다.

이번엔 E까진 풀었다.

나쁘진 않은 컨디션으로 E번까진 푼 대회였다.

이제 F나 G도 봐서 고득점을 노릴 때인가…