Yet Another Binary Problem 2

문자열에 있는 1의 개수를 $K$라 하고, 왼쪽부터 $i$번째 1의 위치를 $x_i$라 하자.

$a$번째부터 $b$번째까지의 1을 모두 포함하는 가장 짧은 구간을 연산에 사용하려면 다음 부등식이 필요하다.

$$x_b-x_a+1 \le 2(b-a+1)-1.$$

이를 정리하면

$$x_a-2a \ge x_b-2b$$

가 된다. 편의상

$$q_i=x_i-2i$$

로 두자.

다음 점화식으로 정의되는 구간 $[l,r]$을 good이라고 하자.

$$g[l][l]=\mathrm{true}.$$

$l<r$일 때,

$$g[l][r] = \left(g[l+1][r] \land q_l \ge \min(q_{l+1},\ldots,q_r)\right) \lor \left(g[l][r-1] \land \max(q_l,\ldots,q_{r-1}) \ge q_r\right).$$

첫 번째 조건은 왼쪽 끝의 1을 먼저 지우는 경우이고, 두 번째 조건은 오른쪽 끝의 1을 먼저 지우는 경우이다.

$l$을 감소시키는 순서로 순회하고 각 $l$에 대해 $r$을 증가시키면, 필요한 최솟값과 최댓값을 누적하여 모든 $g[l][r]$을 $O(K^2)$에 계산할 수 있다.

Lemma 1. 경계 바로 바깥에 0이 있는 good 구간은 내부의 1을 하나만 남길 수 있다.

구간 길이에 대해 귀납한다. 첫 번째 조건이 성립한다고 하자. $q_l \ge q_i$를 만족하는 가장 가까운 $i$를 고르면, $l$번째 을 포함하여 조건을 만족하는 연산 구간을 잡아 왼쪽 끝의 을 지울 수 있다. 두 번째 조건이 성립하는 경우에는 대칭적으로 오른쪽 끝의 을 지울 수 있다. 그 뒤 더 짧은 good 구간에 귀납 가정을 적용한다.

Lemma 2. 구간 $[a,b]$가 good인 것과, 다음을 만족하는 $a \le i \le j \le b$가 존재하는 것은 동치이다.

$$q_i=\max(q_a,\ldots,q_b), \qquad q_j=\min(q_a,\ldots,q_b).$$

즉, 구간의 최댓값이 등장하는 어떤 위치가 구간의 최솟값이 등장하는 어떤 위치보다 앞이거나 같다. 이는 good의 점화식에 대해 구간 길이로 귀납하면 증명할 수 있다.

이제 $dp[i]$를 앞의 $i$개 1을 good 구간들로 나누는 최소 구간 수라고 하자.

$$dp[0]=0,$$ $$dp[r]=\min_{1 \le l \le r,\ g[l][r]}\left(dp[l-1]+1\right).$$

모든 good 구간을 이미 알고 있으므로 이 DP도 $O(K^2)$에 계산할 수 있다.

이제 $dp[K]$가 답임을 보이면 된다.

Lemma 3. 연산을 한 번 수행해도 최소 good 분할 수는 감소하지 않는다.

연산 전후의 $q$ 배열을 각각 $Q,Q'$라 하자. 연산으로 하나의 1을 지우면 $q$ 배열에서는 원소 하나가 사라지고, 그 오른쪽 원소들이 모두 $2$씩 증가한다.

이를 거꾸로 보면 $Q'$의 한 위치에 값 $z$를 삽입한 뒤, 그 오른쪽 접미사의 모든 값에서 $2$를 빼면 $Q$가 된다. 삽입 위치를 포함하지 않는 good 블록은 모든 값이 그대로이거나 모두 $2$씩 감소하므로 여전히 good이다.

삭제에 사용한 연산 구간의 양 끝 1을 $a,b$라 하면 $q_a \ge q_b$이다. 따라서

$$(q_a-z)+(z-q_b)=q_a-q_b \ge 0$$

이므로 $q_a \ge z$ 또는 $z \ge q_b$ 중 하나가 성립한다.

$q_a \ge z$이면 삽입 위치의 왼쪽에서 $z$ 이상인 값을 포함하는 최초의 블록까지 합친다. $z \ge q_b$이면 오른쪽에서 이하인 값을 포함하는 최초의 블록까지 합친다. Lemma 2에 의해 합친 구간은 good이다.

삽입 위치가 블록 내부인 경우에도 $q_{i+1}-q_i \ge -1$을 이용하면, 삽입 전 블록이 good이면 삽입 후 블록도 good임을 Lemma 2로 보일 수 있다. 따라서 $Q$의 최소 good 분할 수는 의 최소 good 분할 수보다 클 수 없다. 즉, 실제 연산을 할수록 최소 good 분할 수는 감소하지 않는다.

Lemma 4. 초기 $q$ 배열의 최소 good 분할은 실제 연산으로 만들 수 있다.

최소 good 분할의 블록을 왼쪽부터 처리한다. $S_1=\texttt{0}$이므로 첫 번째 블록의 왼쪽에는 0이 있어 Lemma 1을 적용할 수 있다.

한 블록을 1 하나로 줄인 뒤, 그 1이 다음 블록의 첫 번째 1과 붙어 있다고 하자. 두 1이 붙어 있으면 앞쪽 1의 $q$ 값이 뒤쪽 1의 $q$ 값보다 $1$ 크므로, 앞쪽 1과 다음 good 블록을 합친 구간도 good이다. 이는 최소 good 분할의 블록 수를 더 줄일 수 있다는 뜻이므로 모순이다.

따라서 다음 블록의 왼쪽에는 항상 0이 존재하고, Lemma 1을 반복 적용하여 각 블록을 1 하나로 줄일 수 있다.

최종적으로 $m$개의 1이 남았다고 하자. 최종 배열은 길이 $1$인 good 구간 $m$개로 나눌 수 있다. Lemma 3을 반복 적용하면

$$dp[K] \le m$$

이다. 따라서 $dp[K]$보다 적은 수의 1을 남길 수 없다. 반대로 Lemma 4에 의해 정확히 $dp[K]$개의 1을 남길 수 있다.

그러므로 답은 $dp[K]$이다. $K=0$인 경우에는 답이 $0$이다.

각 테스트 케이스의 시간 복잡도는 $O(N^2)$이고, 공간 복잡도는 $O(N^2)$이다.

Solution written by GPT5.6