[IOI 2024] Hieroglyphs

문제 링크: https://www.acmicpc.net/problem/32267

 

제곱 미만 LCS가 나오는 레전드 문제이다. 문제를 읽고 적지 않은 충격을 받았을 불쌍한 국가대표들...

 

0. 기본적인 관찰

문자열 $S$ 안에 있는 문자 $x$의 개수를 $count(S, x)$로 정의하자.
UCS가 존재한다면 UCS 내부에 들어간 문자 $x$의 개수는 $min(count(A, x), count(B, x))$이다. 
$count(A, x) \leq count(B, x)$라면 $x$를 $A$의 문자, 아닌 경우에는 $x$를 $B$의 문자라고 하자.

앞으로 편의상 universal common sequence를 ucs, common sequence를 cs라고 부르자.

1. Subtask 2의 일부

$count(A, x)=0$ 또는 $count(B, x)=0$인 문자 $x$들은 제거하고 생각하자.
각 문자 $x$에 대해 $min(count(A, x), count(B, x))=1$이다.

ucs의 강력함을 사용하자. 임의의 cs가 ucs의 subsequence라는 점을 이용하는 것이다. 특정 형태의 문자열이 cs인지 판별함으로써 ucs를 찾는 것이다.

 

ucs가 존재한다고 가정하자.
두 문자 $i$와 $j$에 대해서 문자열 $ij$와 $ji$를 주목해보자. 두 문자열 중 정확히 하나만 cs이다. (둘 다 cs라면 ucs의 모든 문자가 다르다는 조건에 모순이고, 둘 다 cs가 아니라면 ucs에 모든 문자가 존재한다는 조건에 모순이다). $ij$가 cs라면 ucs에서 $i$가 $j$보다 앞에 오고, $ji$가 cs라면 ucs에서 $j$가 $i$보다 앞에 온다. 

$i$가 $j$보다 앞에 온다는 것을 $i < j$라고 표현할 때, ucs가 $a_1a_2\ldots a_n$라면 $i<j$에 대해 $a_i < a_j$를 만족해야 한다.

한 가지 재미있는 점은 $ij$가 cs라면 ucs 뿐만 아니라 모든 cs에 대해서 $i$가 $j$보다 앞에 온다. 따라서 임의의 $i<j$에 대해서 $a_i<a_j$를 만족하는 $a_1, a_2, \ldots, a_n$이 존재한다면 $a_1 a_2 \ldots a_n$이 ucs의 조건을 만족한다.

Subtask 2에 대해서 ucs의 필요충분조건을 알았다. Subtask 2는 이쯤에서 마무리하지만, ucs의 강력함을 알아보는 계기가 되었다.

2. Subtask 4

이번에는 ucs의 존재성이 보장되어있기 때문에, 두 문자의 순서관계만 알 수 있으면 된다.

두 문자 $i$와 $j$에 대해서 각 문자가 ucs에 $c_i$, $c_j$개 있다고 하자.
$x$번째 $i$와 $y$번째 $j$에 대해서 알아보기 위해서는 $S=ii \ldots i jj \ldots j$의 cs 유뮤를 알면 된다. 이때 $S$는 앞에 $i$가 $x$개 있고 뒤에 $j$가 $c_j-y+1$개 있는 문자열이다.

$S$가 cs인 것을 판별하는 것은 $S$가 $A$, $B$의 subsequence인지 판별을 통해 확인할 수 있고 이는 적절한 전처리로 $O(1)$에 확인할 수 있다. 이를 정렬 함수로 사용하면 Subtask 4를 $O(NlogN)$에 풀 수 있다.

 

3. Subtask 5

Subtask 4에서 ucs의 후보를 찾았다. 후보 문자열을 $C$라고 했을 때 $C$가 실제로 ucs인지 판별하는 문제로 바뀌었다.

우선 $C$가 실제로 cs인지 확인해본 뒤에, ucs 조건을 만족하는지 알아보자. cs 판정은 쉽게 할 수 있다.

 

우리가 찾고 싶은 문자열은, ucs의 subsequence는 아니지만 cs인 문자열을 찾고 싶다. 이쯤에서 간단하고 자명한 그리디 알고리즘을 선보인다.

 

문자열 $X$가 문자열 $Y$의 subsequence인 것을 보이기 위해서 $Y$의 앞에서부터 문자들을 보면서 $X$의 시작 문자와 같은지 확인한다. 만약 같다면 $X$의 시작 문자를 제거한다.

 

간단한 투포인터 알고리즘이다.

 

문자열 $X$가 $Y[0..i]$의 subsequence인 최소 $i$를 $f(X, Y)$라고 했을 때, 위의 조건은 $f(S, A) <|A|, f(S, B) <|B|$이고 $f(S, C)=|C|$인 $S$를 찾는 것과 동일하다. (편의상 $X$가 $Y$의 subsequence가 아니라면 $f(X, Y)=|Y|$라고 하자)

 

LCS 감성으로 $dp[i][j] = f(S, A) \leq i, f(S, B) \leq j$인 문자열 $S$ 중 $f(S, C)$의 최댓값으로 정의하자.

$A[i] \neq B[j]$인 경우에는 $dp[i][j]=max(dp[i-1][j], dp[i][j-1])$이다.

$A[i]=B[j]$이라면 추가적인 하나의 전파가 더 들어가는데, $k > dp[i-1][j-1]$ 중 $C[k]=A[i]$를 만족하는 최소 $k$에 대해 $dp[i][j]=min(dp[i][j], k)$이다. 이는 적당한 전처리로 $O(1)$에 구할 수 있어서 전체 문제를 $O(N^2)$에 풀 수 있다.

 

4. Full task를 위한 관찰 1

Subtask 5 풀이에는 문제점이 있다. LCS식 dp에서 벗어나지 못했다는 점이다. 이대로라면 dp state의 개수를 $O(N^2)$개 미만으로 줄이지 벗어나지 못한다. 몇가지 관찰을 해보자.

 

$match_A[i]$를 $f(C[0..i], A)$로 정의하자. 간단하게 말하자면 $C$를 $A$에 매칭시켰을 때 $C[i]$가 $A$에서 대응하는 위치와 같다. $match_B[i]$도 비슷하게 $f(C[0..i], B)$로 정의하자. $match$를 통해서 우리는 $C$의 원소들을 $A$의 원소와 $B$의 원소 사이의 간선으로 생각할 수 있다. $C[i]=A[match_A[i]]=B[match_B[i]]$이다.

 

C를 A와 B 사이의 간선으로 표현해보았다

 

문자열 $S$에 대해서 $g_A(S)=match_A[f(S, C)]$, $g_B(S)=match_B[f(S, C)]$로 정의하자. $g_A(S)$와 $g_B(S)$의 정의는 $A$와 $B$의 원소 사이의 간선으로 표현되는 $f(S, C)$를 표현한 것이다.

 

임의의 문자열 $S$에 대해서, $f(S, A) \leq g_A(S)$이고 $f(S, B) \leq g_B(S)$이다. 좀 더 풀어서 말하자면 $S$를 $A$와 $B$에 매칭시켜서 만든 간선이 $S$를 $A$와 $B$ 사이의 간선으로 표현된 $C$와 매칭시킨 간선보다 항상 왼쪽에 있다는 뜻이다. 

이유를 간단하게 설명하자면 $f(S, A)$는 $S$가 $A[0..i]$의 subsequence인 최소 $i$로 정의된다. $A$의 $g_A(S[0..i])$번째 원소들은 $S[i]$이기 때문에 $A$의 $g_A(S[0..0]), g_A(S[0..1]), \ldots, g_A(S[0..|S|-1])=g_A(S)$번째 원소들이 $S$를 이룬다. 따라서 $g_A(S) \geq f(S, A)$이다.

(빨간 간선은 $f(S, A)$와 $f(S, B)$를 연결한 간선, 파란 간선은 $g_A(S)$와 $g_B(S)$를 이은 간선이다. i번째 빨간 간선이 i번째 파란 간선보다 앞에 있다)

 

중요한 관찰은 $f(S, A) < match_A[f(S, C)]$이고 $f(S, B) < match_B[f(S, C)]$인 $S$가 존재하면 $C$는 ucs의 조건을 만족시키지 못한다. $S$의 마지막 문자를 $i$라고 하면, $S$ 뒤에 $i$를 붙일 수 있는 만큼 붙여서 $C$의 subsequence가 아닌 cs를 만들 수 있다.

빨간 간선 뒤에 0을 잇는 2개의 간선을 덧붙일 수 있다. 파란 간선 뒤에 0을 잇는 2개의 간선을 덧붙일 수 없다

따라서 $C$가 ucs라면 $f(S, A)=g_A(S)$ 혹은 $f(S, B)=g_B(S)$이다. 이제 dp 식을 뒤집을 수 있다.

 

뒤집는다고 하면, 기존의 dp 식은 $f(S, A)$와 $f(S, B)$를 고정시키고 $f(S, C)$를 구했다면, 이번에는 $f(S, C)$를 고정하고 $f(S, A) = g_A(S)$인 경우 $f(S, B)$의 최솟값, $f(S, B) = g_B(S)$인 경우 $f(S, A)$의 최솟값을 구할 것이다. 이렇게 하면 dp state 개수가 $O(N)$개로 줄어든다. 

 

$dp[i][0]$을 $f(S, C)=i, f(S, B)=g_B(S)$를 만족하는 $S$에 대해서 $f(S, A)$의 최솟값으로 정의하자. 마찬가지로 $dp[i][1]$을 $f(S, C)=i, f(S, A)=g_A(S)$를 만족하는 $S$에 대해서 $f(S, B)$의 최솟값으로 정의하자.

 

각 문자열 $c$에 대해서 $S$의 마지막에 $c$를 추가한다고 생각하자.

$k_X$를 $k>i_X$이고 $X[k]=c$를 만족하는 최소 $k$로 정의하자. 여기에서 $i_A=dp[i][0], i_B=g_B(S)=match_B[i], i_C=i$이다. 만약 $k_A<match_A[k_C]$이고 $k_B<match_B[k_C]$라면 $S$의 마지막에 $c$를 추가한 문자열 $S'$은 $k_A=f(S', A)<g_A(S')=match_A[k_C]$와 $k_B=f(S', B)<g_B(S')=match_B[k_C]$를 만족하게 된다. 그러면 $C$는 ucs가 아니라는 결론에 도달하게 된다.

 

만약 $k_A=match_A[k_C]$라면 $dp[k_C][1]=min(dp[k_C][1], k_B)$의 전이를, $k_B=match_B[k_C]$라면 $dp[k_C][0]=min(dp[k_C][0], k_A)$의 전이를 이루게 된다. 

 

dp 상태의 개수는 $O(N)$개로 적지만, $S$ 뒤에 문자열 $c$를 붙여서 만든 문자열 $S'$이 $f(S', A)=g_A(S')$ 혹은 $f(S', B)=g_B(S')$을 만족하는지 확인하는 과정은 여전히 $O(N^2)$이다. 이를 빠르게 하려고 노력해보자.

5. Full task를 위한 관찰 2

$S$의 뒤에 문자 $c$를 추가해서 만든 문자열 $S'$에 대해 $f(S', A)<g_A(S')$, $f(S', B)<g_B(S')$을 만족하는 $c$의 존재성에 대해서 알아볼 필요가 있다. 만약 이러한 $c$가 존재한다면, $C$는 ucs가 아니라는 것을 보이게 된다.

 

$g_A(S)>f(A, S)$이고 $g_B(S) = f(B, S)$라고 가정하자. $c$를 인덱스가 $f(A, S)$와 $g_A(S)$ 사이에 있는 $A$의 문자라고 하자. $A[g_A(S)+1 .. |A|-1]$에 있는 $c$의 개수가 $B[g_B[i]+1 .. |B|-1]$에 있는 $c$의 개수보다 적다면, $S$의 뒤에 $c$를 계속 붙여서 $C$의 subsequence는 아니지만 cs인 문자열을 만들 수 있다.

 

$A[g_A(S)+1 .. |A|-1]$에 있는 $c$의 개수가 $B[g_B(S)+1 .. |B|-1]$에 있는 $c$의 개수보다 많거나 같다면, $B$에 있는 $c$는 모두 ucs에 포함된다. 즉 $match_B[k_C]=k_B$라는 뜻이다.

따라서 우리는 $A[dp[i][0]+1 .. match_A[i]]$에 있는 모든 문자열 $c$에 대해서 $A[match_A[i]+1..|A|-1]$에 있는 $c$의 개수가 $B[match_B[i]+1 .. |B|-1]$에 있는 $c$의 개수보다 많거나 같은지 확인해주면 된다.

 

 

모든 cs $S$가 $f(S, A)=g_A(S)$ 또는 $f(S, B)=g_B(S)$를 만족한다면 $C$는 ucs의 조건을 만족한다고 할 수 있다. cs $S$가 $C$의 subsequence가 아니기 위해서는 어떤 $S$의 prefix 문자열 $S'$에 대해서 $f(S', A) < g_A(S')$이고 $f(S', B) < g_B(S')$을 만족해야 하기 때문이다.

6. Full task

$dp[i][0]$을 구하려고 해보자. $S$의 마지막 문자를 $c$라고 할 때, $A[match_A[i]]=B[match_B[i]]=c$이다. $dp[j][0]$에서 $dp[i][0]$으로 전이를 하기 위해서는 $B[match_B[j]+1 .. match_B[i]-1]$에는 $c$가 없어야 한다.

$C[k+1..i]$에 $c$가 없는 최소 $k$를 구하자. $k \leq j < i$인 모든 $j$에 대해 $dp[j][0]$의 최솟값을 $t$라고 하면, $dp[i][0]$은 $A[l]=c$이고 $l > t$를 만족하는 최소 $l$이다. 이런 형태의 전이는 segment tree로 $O(logN)$에 해줄 수 있다. $dp[i][1]$도 비슷하게 구할 수 있다.

 

한 가지 의문점이 들 수 있는 것은, $dp[j][1]$에서 $dp[i][0]$으로의 전이는 왜 고려하지 않냐고 할 수 있다. 그러한 전이는 고려해주지 않아도 된다. $dp[j][1]$을 고려하는 문자열 $S$의 경우 $f(A, S)=match_A[j]$인데, $dp[i][0]$를 구할 때는 $f(A, S)$가 작은 것이 중요하기 때문이다. $dp[j][0]$을 고려하는 모든 문자열 $S'$에 대해 $f(A, S') \leq match_A[j]$이기 때문에 고려하지 않아도 된다.

좌측은 dp[j][1] -> dp[i][0]의 전이, 우측은 dp[j][0] -> dp[i][0]의 전이를 나타내었다

 

 

이제 $A$의 $dp[i][0]$번째 문자부터 $match_A[i]-1$번째 문자 사이에 5.의 조건을 만족하지 않는 문자가 있는지 확인해야 한다. 이 문제처럼 스위핑하면서 구할 것이다. $i$를 증가시키면서 $A[match_A[i]+1 .. |A|-1]$에 있는 $c$의 개수가 $B[match_B[i]+1 .. |B|-1]$에 있는 $c$의 개수보다 적거나 같은 $c$를 관리하자. 그리고 이러한 $c$에 대해서 $A[k]=c$이고 $k < match_A[i]$인 최대 $k$를 모두 모아놓은 집합 $s$를 std::set으로 관리하자. $dp[i][0]$이 $s$의 최대 원소보다 작다면 $C$는 ucs가 아닌 것이다.

 

5.의 조건을 만족하지 않는 $dp[i][0]$이 없는 경우에는 $C$는 ucs의 조건을 만족한다고 할 수 있다. 이에 대한 간략한 설명은 5의 끝부분에서 확인할 수 있다.

 

따라서 전체 문제를 $O(NlogN)$에 풀 수 있다.

 

 

 

 

 

 

 

풀이를 읽다가 서술이 잘못된 것 같거나 이해가 안 가는 부분이 있다면 댓글에 적어주시면 제가 읽어보고 글에 추가적인 설명을 덧붙이거나 댓글로 설명해보려고 노력해 보겠습니다. 문제가 어려워서 풀이글 쓰는 것도 어려웠습니다...