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년 전
어려워요
wizardrabbit 2년 전
네?
x32_noah 2년 전
선 댓글 후 감상이 유행한다고 합니다 일단 저부터
chessplayer 2년 전
제 머리로는 이해가 안 되네요(⊙_⊙;)