31442번 좋은 수열 문제의 오토마타 기반 풀이

https://www.acmicpc.net/problem/31442

에디토리얼과 결이 다른 풀이가 있어 공유합니다.

처음에 $1$이 $N$개이므로, 최소 $N - 1$번 작업을 수행해야 $N$이 만들어집니다. 한편 처음 $A$의 길이에서 작업의 가능한 횟수가 최대 $N - 1$번이므로, 작업을 정확히 $N - 1$번 하는 경우만 고려해도 됩니다. 그러면 문제에서 원하는 상황은 매 작업에서 $x, y \geq 1$, $z = 0$인 것과 동치임을 보일 수 있습니다.

이제 값이 $1$ 이상인지 여부만이 중요함을 알 수 있으므로, $x = y = 1$, $z = 0$인 경우 $w$, $1$을 삽입하는 문제로 변형해봅시다. 그러면 가능한 작업은 아래 두 가지가 됩니다. 모든 원소가 $0$ 또는 $1$이므로 문자열처럼 표기했습니다.

  • $1101$을 $11$로 바꾼다.
  • $1100$을 $01$로 바꾼다.

편의를 위해 다음과 같은 표기를 사용합니다.

수열 $A$와 정수 $i$에 대해 $A_i A_{i+1}, A_{i+2}, A_{i+3}$이 $1101$ 또는 $1100$인 경우 $f(A, i)$를 위 작업을 해당 위치에서 했을 때 나오는 수열로 정의합니다.

수열 $A$에 대해 $A_i A_{i+1}, A_{i+2}, A_{i+3}$이 $1101$ 또는 $1100$인 최소의 정수를 $g(A)$로 표기합니다. 그러한 정수가 존재하는 경우에만 표기를 사용합니다.

그러면 $N=1$인 좋은 수열은 $10$과 $01$뿐이고 $N=k \geq 2$인 경우 수열 $A$에 대해 $f(A, i)$가 $N=k-1$ 좋은 수열인 경우가 존재하면 $A$가 $N=k$ 좋은 수열이라고 할 수 있습니다. 이 성질을 좋은 수열의 귀납적 정의라고 부르겠습니다.

다음을 증명하고자 합니다.

명제 1. $N = k \geq 2$인 좋은 수열 $A$에 대해 $f(A, g(A))$는 $N = k - 1$인 좋은 수열이다.


명제 1의 증명은 뒤에서 하고, 우선 $A := f(A, g(A))$를 반복하는 방법에서 출발해서 오토마타를 구성해봅시다. 아래는 이진 문자열이 주어졌을 때 $A := f(A, g(A))$를 반복해서 길이가 $2$가 되는 길이 $4$ 이상의 좋은 수열인지 판별하는 의사코드입니다. 명제 1이 참이면 이는 길이 $4$ 이상의 좋은 수열인지 판별하는 것과 동치입니다.

의사코드에서 인덱스가 0 based임에 주의해야 합니다.

def f(A: str, i: int):
    assert len(A) >= i + 4 and A[i:i+3] == '110'
    return A[:i] + A[i+3] + '1' + A[i+4:]
def check1(A: str):
    assert all(c == '0' or c == '1' for c in A)
    if len(A) % 2 != 0 or len(A) < 4: return False
    while True:
        i = A.find('110')
        if i == -1 or i + 4 > len(A): break
        A = f(A, i)
    return A == '01'

이때 check1을 아래와 같이 수정해도 같은 결과가 나옴을 보일 수 있습니다. 증명은 f가 실행된 횟수가 같을 때 check1의 A와 check1의 s + (remainder of A)가 같음을 보이면 됩니다.

def check2(A: str):
    assert all(c == '0' or c == '1' for c in A)
    if len(A) % 2 != 0: return False
    s = ''
    for c in A:
        s += c
        while True:
            i = s.find('110')
            if i == -1 or i + 4 > len(s): break
            s = f(s, i)
        pass # end while
    return len(A) >= 4 and s == '01'

이제 check2에서 while문이 끝났을 때 s가 특정 형태의 경우 결과가 무조건 False가 됨을 보입니다.

명제 2. check2에서 while문이 끝났을 때 다음 중 하나 이상이 성립할 경우 함수를 마저 실행했을 때 반환값이 False가 된다.

  • s == '0'
  • s == '10'
  • s == '011' or s == '010'
  • s == '101'

증명:

len(A) < 4면 자명하므로 len(A) >= 4인 경우만 고려합니다.

반환값이 True이려면 맨 마지막으로 f가 실행될 때 s == '1100'이어야 합니다.

  • s == '0'

f를 한 번이라도 수행한 이후는 항상 len(s) >= 2이므로 A[0] == '0'일 때만 이런 경우가 가능합니다. 이 이후로 f가 실행되는 경우 i >= 1이 되고, s[0] == '0'이 유지되므로 언제나 s != '1100'입니다.

나머지 케이스도 비슷한 논리로 증명할 수 있습니다. 귀찮아ㅏ...


check2에서 명제 2의 조건들을 처리하고 A의 길이 조건을 제거한 의사 코드를 아래와 같이 적을 수 있습니다.

def check3(A: str):
    assert all(c == '0' or c == '1' for c in A)
    s = ''
    for c in A:
        s += c
        while True:
            i = s.find('110')
            if i == -1 or i + 4 > len(s): break
            s = f(s, i)
        if s in ('0', '10', '011', '010', '101'): return False
        pass # end if
    return s == '01'

check3 또한 check2와 같은 결과를 반환함을 보일 수 있습니다. 증명은 홀수 길이에 대해서 언제나 False임을 보이고, A in ('01', '10')일 때 False임을 보이면 됩니다.

이제 check3에서 if문이 끝났을 때 다음과 같이 s가 특정한 형태만을 가짐을 보일 수 있습니다. 증명은 생략합니다.

명제 3. check3에서 if문이 끝났을 때 s가 다음 중 하나의 형태를 가집니다.

  • '1' * t (단, t >= 0)
  • '1' * t + '0' (단, t >= 2)
  • '01'

이제 s의 각 형태를 오토마타의 상태로 생각하고 다음과 같이 이름을 붙입니다.

  • '1' * t: $t$
  • '1' * t + '0': $(t-1)'$
  • '01': $d'$
  • if ... False: $d$

그러면 상태 전이를 다음과 같이 표현할 수 있습니다. accept 상태는 $d'$뿐입니다.

상태\입력 0 1
$0$ $d$ $1$
$1$ $d$ $2$
$t \geq 2$ $(t-1)'$ $t+1$
$1'$ $d'$ $2$
$2'$ $d$ $3$
$(t \geq 3)'$ $t-1$ $t+1$
$d$ $d$ $d$
$d'$ $d$ $d$

이제 명제 1을 증명합니다.

수열의 처음 길이에 대한 귀납법으로 증명합니다.

$N = 2$일 때의 좋은 수열은 $1100$뿐이고, $N = 3$일 때의 좋은 수열은 $110100$뿐입니다. 두 경우 모두 가정이 성립함을 알 수 있습니다.

$N = k \geq 4$인 경우를 생각해봅시다.

좋은 수열 $A$를 생각해봅시다. 그러면 $f(A, x)$가 $N=k-1$ 좋은 수열인 인덱스 $x$가 존재합니다. 그런 인덱스가 여러 개이면 최솟값을 생각합니다. 이제 $p = x - g(A)$라 하면 $p \geq 0$입니다. 증명해야 할 명제는 $p = 0$인 것이 됩니다.

$p \geq 4$면 $g(f(A, x)) = g(A)$이고, 귀납법의 가정에 의해 $f(f(A, x), g(f(A, x)) = f(f(A, x), g(A)) = f(f(A, g(A)), x - 2)$도 좋은 수열입니다. 그러면 좋은 수열의 귀납적 정의에 의해 $f(A, g(A))$가 좋은 수열이고 $p \leq 0$이어서 모순입니다.

$p = 3$이면 $g(f(A, x)) = g(A) = x - 3$이고, 귀납법의 가정에 의해 $f(f(A, x), g(f(A, x)) = f(f(A, x), x - 3)$도 좋은 수열입니다. 이때 $f(f(A, x), x - 3)$은 다음 중 하나입니다.

  • $A$에서 $1101101$을 $111$로 바꾼 형태.
  • $A$에서 $1101100$을 $011$로 바꾼 형태.

$1101101$의 경우 $f(f(A, x), x - 3) = f(f(A, x - 3), x - 2)$이므로, $f(A, x - 3) = f(A, g(A))$가 좋은 수열이어서 $p \leq 0$이고 모순입니다.

$1101100$ 의 경우, $f(f(A, x), x - 3)$ 은 $N=k-2$ 인 좋은 수열이고, 귀납법의 가정에 의해 오토마타가 $f(f(A, x), x - 3)$ 을 accept합니다. 따라서 오토마타에 $A_{\lt x-3}011$ 을 넣었을 때 오토마타의 상태는 $d$ 가 아니어야 하고, $A_{\lt x-3}$ 만을 넣었을 때의 상태는 $t \geq 2$  또는 $(t \geq 3)'$ 입니다. 이때, $t \geq 2$  또는 $(t \geq 3)'$ 인 상태에서 $011$ 을 더 넣는 경우와 $101$ 을 더 넣는 경우가 같은 상태가 됨을 알 수 있습니다. 따라서 $A$ 에서 $1101100$ 을 $101$ 로 바꾼 형태인 $f(f(A, x - 3), x - 2)$ 는 좋은 수열이고, $f(A, x - 3) = f(A, g(A))$ 가 좋은 수열이어서 $p \leq 0$ 이고 모순입니다.

$p=2$이나 $p=1$인 경우는 $x$에서부터 $110?$의 형태가 나올 수 없으므로 불가능합니다.


이제 오토마타가 accept하는 수열이 좋은 수열임을 알고 있습니다.

문제에 세그먼트 트리를 사용하기 위해서, 수열의 각 원소를 오토마타의 처음 상태에서 오토마타의 나중 상태로 가는 함수로 생각하고, 수열을 각 원소에 대응하는 함수들을 합성한 함수로 생각할 수 있습니다.

이제 이런 함수들은 다음과 같은 개형을 가짐을 알 수 있습니다.

이전 이후
$t \lt T$ $d$ 또는 $d'$
$t \geq T$ $t+\delta$ 또는 $(t+\delta)'$
$(t \lt T')'$ $d$ 또는 $d'$
$(t \geq T')'$ $t+\delta$ 또는 $(t+\delta)'$
$d$ $d$
$d'$ $d$
  • $\delta$는 원래 원소들 중 $1$의 개수에서 $0$의 개수를 뺀 값이 됩니다.
  • $t \geq T$ 상태들은 모두 $t+\delta$로 가거나, 모두 $(t+\delta)'$로 가게 됩니다.
  • $(t \geq T')'$ 상태들도 비슷하게 모두 $t+\delta$로 가거나, 모두 $(t+\delta)'$로 가게 됩니다.
  • $d'$으로 가게 되는 상태들은 $t$ 상태들과 $t'$ 상태들 각각에 대해 최대 한 개뿐이고, 만약 존재하면 $-\delta$ 상태 또는 $(-\delta)'$ 상태입니다.

따라서 아래와 같은 인자를 저장하면 함수를 완전히 표현할 수 있습니다.

  • $\delta$
  • $T$
  • $T'$
  • $t$가 $t+\delta$와 $(t+\delta)'$ 중 어느쪽으로 가는지
  • $t'$가 $t+\delta$와 $(t+\delta)'$ 중 어느쪽으로 가는지
  • $-\delta$가 $d$와 $d'$ 중 어느쪽으로 가는지
  • $(-\delta)'$가 $d$와 $d'$ 중 어느쪽으로 가는지

예를 들어 $0$에 대응하는 함수는 다음과 같습니다.

  • $\delta = -1$
  • $T = 2$
  • $T' = 3$
  • $t$ → $(t+\delta)'$
  • $t'$ → $(t+\delta)'$
  • $-\delta$ → $d$
  • $(-\delta)'$ → $d'$

이제 위의 인자들로 표현된 함수 두개를 합성하는 로직을 작성하고, 세그먼트 트리의 각 노드에는 주어진 구간의 원소들에 해당하는 함수들을 순서대로 합성한 함수와, 모든 원소들을 뒤집은 다음 해당하는 함수를 합성한 함수 이렇게 두 개의 함수를 저장하면 문제를 풀 수 있습니다.

함수 합성은 설명을 적기 귀찮아서 코드로 대체합니다

res.delta = f1.delta + f2.delta;
res.T = max(f1.T, (f1.t_to_p ? f2.Tp : f2.T) - f1.delta);
res.Tp = max(f1.Tp, (f1.tp_to_p ? f2.Tp : f2.T) - f1.delta);
res.t_to_p = f1.t_to_p ? f2.tp_to_p : f2.t_to_p;
res.tp_to_p = f1.tp_to_p ? f2.tp_to_p : f2.t_to_p;
res.md_to_dp = -res.delta >= f1.T && (f1.t_to_p ? f2.mdp_to_dp : f2.md_to_dp);
res.mdp_to_dp = -res.delta >= f1.Tp && (f1.tp_to_p ? f2.mdp_to_dp : f2.md_to_dp);

댓글 (4개) 댓글 쓰기


kaorin 2년 전

어려워요



x32_noah 2년 전

선 댓글 후 감상이 유행한다고 합니다 일단 저부터


chessplayer 2년 전

제 머리로는 이해가 안 되네요(⊙_⊙;)