RUN 2024 Spring Contest 풀이(내가 출제한 문제들)

E. Two Histograms

0. 직사각형 ($[x_1, x_2] \times [y, y]$)의 시작칸은 $(x_1, y)$으로 정의한다.

직사각형 ($[x_1, x_2] \times [y, y]$)의 끝칸은 $(x_1, y)$, $(x_2, y)$로 정의한다.

어떠한 직사각형이 $x=i$에 있다는 것은 시작칸의 $x$좌표가 $i$라는 것이다.

직사각형을 흰색/검은색으로 칠했다는 것은 시작칸을 흰색, 시작칸이 아닌 끝칸을 검은색으로 칠했다는 것이다.

직사각형을 검은색/흰색으로 칠했다는 것은 시작칸을 검은색, 시작칸이 아닌 끝칸을 흰색으로 칠했다는 것이다.

 

1.1. 어떠한 그림이 2개의 히스토그램의 교집합으로 칠해질 필요충분조건을 구하자.

 

그림이 2개의 히스토그램의 교집합으로 표현된다고 하자.

검은색 칸들은 위를 향하는 히스토그램과 오른쪽을 향하는 히스토그램의 교집합이다.

반대로 흰색 칸들은 각 히스토그램의 여집합(아래를 향하는 히스토그램, 왼쪽을 향하는 히스토그램)의 합집합이다.

 

각 흰색 칸에 대해서 위에 있는 모든 칸이 흰색이거나, 오른쪽에 있는 모든 칸이 흰색이어야 한다.

따라서 위에도 검은색 칸이 있고 오른쪽에도 검은색 칸이 있는 흰색 칸은 존재하면 안 된다. 

 

모든 흰색 칸에 대해서 위쪽 혹은 오른쪽에 검은색 칸이 없으면 그림이 2개의 히스토그램의 교집합으로 표현된다는 것은 쉽게 증명할 수 있다.

 

그림이 2개의 히스토그램의 교집합으로 칠해질 필요충분조건은 흰색 칸의 위와 오른쪽에 검은색 칸이 있는 구조가 존재하지 않는 것과 같다. 앞으로 흰색 칸의 위와 오른쪽에 검은색 칸이 있는 구조를 "ㄴ 구조"라고 하자.

 

1.2. 각 직사각형의 끝칸을 칠하자. ㄴ 구조가 없도록 칠했다면, 두 히스토그램의 교집합으로 만들 수 있는 그림 중 직사각형의 끝칸의 색이 모두 같은 그림이 존재한다.

 

각 흰색 히스토그램을 최대로 많이 칠해보자. 아래/오른쪽을 향하는 흰색 히스토그램의 경우, 직사각형의 검은색 끝칸을 만날 때까지 흰색 칸들을 확장한다는 뜻이다.

 

이렇게 만든 그림은 원래 칠해져 있던 칸의 색을 안 바꾼다는 것을 보이자.

 

검은색으로 칠했던 칸이 그대로 검은 색인 것은 자명하다.

흰색으로 칠했던 칸은 ㄴ 구조를 안 이루기 때문에 위 혹은 오른쪽에 검은색 칸이 없다. 따라서 2개의 흰색 히스토그램 중 적어도 하나에 속하게 되어, 새로 만든 그림에도 흰색으로 남게 된다.

 

2. 각 직사각형에 대해서 끝칸들을 칠한 경우, 나머지 직사각형을 어떻게 칠하는지와 관계없이 흰색으로 칠한 칸의 오른쪽에 검은색 칸이 존재하는지를 알 수 있다.

만약 어떠한 직사각형 a의 오른쪽에 직사각형 b가 존재한다고 하자. a의 흰색칸의 오른쪽에는 반드시 b의 검은 칸이 존재한다. 

직사각형 a의 오른쪽에 직사각형이 없다고 가정하자. a의 끝칸을 흰색/검은색으로 칠한 경우에는 a의 흰색칸의 오른쪽에 a의 검은 칸이 존재한다. a의 끝칸을 검은색/흰색으로 칠한 경우에는 a의 흰색칸 오른쪽에는 직사각형의 끝칸은 존재하지 않으므로 검은색 칸이 없다.

따라서 각 직사각형에 대해서 자신과 같은 y값을 가지는 직사각형이 자신의 오른쪽에 있는지 알아야 한다. 같은 y값을 가지고 시작하는 칸의 x값이 더 큰 직사각형이 없는 직사각형을 특별한 직사각형이라고 하자.

 

3. 각 직사각형에 대해서 특별한지 여부를 저장하자.

ㄴ 구조가 안 생기기 위해서는 특별하지 않은 직사각형에 대해서는 흰색 칸 위에 검은 칸이 있으면 안 된다.

특별한 직사각형을 흰색/검은색으로 칠한 경우에 흰색 칸 위에 검은 칸이 있으면 안 된다.

특별한 직사각형을 검은색/흰색으로 칠한 경우에 흰색 칸의 오른쪽에 어떠한 직사각형도 있지 않기 때문에 ㄴ 구조를 이룰 수 없고, 위에 검은색 칸이 있어도 된다. 

특별하지 않은 직사각형의 흰색 칸과 특별한 직사각형을 흰색/검은색으로 칠했을 때 흰색 칸의 위에 검은색 칸이 있으면 안 된다는 조건을 ☆이라고 하자. 이 조건을 만족한다는 것은 ㄴ 구조가 없는 것과 동치이다.

 

이제는 각 직사각형의 끝칸의 위/아래에 있는 직사각형의 끝칸이 중요하다. 따라서 직사각형의 끝칸의 x좌표를 $K-1$로 나눈 나머지로 직사각형을 그룹으로 나눈 뒤에 각 그룹에 대해서 $K=2$인 경우를 풀어주면 된다. 이때 각 직사각형이 특별한지 여부를 미리 구해두고 $K=2$의 경우를 풀어야 한다.

 

4. 시작하는 칸의 x좌표가 같은 여러 개의 직사각형들을 보자. 아래에 있는 직사각형의 끝칸이 흰색/검은색으로 칠해지고 위에 있는 직사각형의 끝칸이 검은색/흰색으로 칠해진다면 ㄴ 구조를 만들게 된다. 따라서 어떠한 직사각형의 끝칸이 검은색/흰색으로 칠해진다면 그 아래에 있는 직사각형들의 끝칸도 검은색/흰색으로 칠해지게 된다. 따라서 직사각형이 $p$개 있다면 가능한 색칠의 가짓수는 $p+1$가지이다.

 

5. 각 직사각형에 대해 특별한지 여부를 미리 구해두고 $K=2$인 경우를 풀어보자.

시작하는 칸의 x좌표가 $i$ 이하인 모든 직사각형의 끝칸을 ☆을 만족하도록 칠해보자.

$x=i$에 있는 직사각형이 $p$개, $x=i+1$에 있는 직사각형이 $q$개 있다고 하자.

 

시작하는 칸의 x좌표가 $i$ 이하인 모든 직사각형의 끝칸을 칠하는 경우 중 $x=i$에 있는 직사각형들 중 흰색/검은색으로 칠하는 직사각형의 개수가 $j$개인 경우 얻을 수 있는 최대 점수를 $dp[i][j]$로 정의하자. ($0 \leq j \leq p$)

 

dp 점화식은 $dp[i+1][k] = max(dp[i][j]+score[i+1][k])$으로 정의된다. 이때 $score[i+1][k]$는 $i+1$에서 시작하는 직사각형들 중 위에 있는 $k$개를 흰색/검은색으로 칠하고 아래에 있는 $q-k$개를 검은색/흰색으로 칠한 경우에 얻는 점수이다.

 

위의 점화식이 성립하기 위해서는 $x=i$에서 시작하는 직사각형 중 $j$개를 흰색/검은색으로 칠한 경우에서 $x=i+1$에서 시작하는 직사각형 중 $k$개를 흰색/검은색으로 칠했을 때 ☆조건을 만족하는지 알아봐야 한다. 이는 각 $j, k$에 대해서 $O(1)$에 구할 수 있다. 따라서 ($i$에서 시작하는 직사각형 개수) $\times$ ($i+1$에서 시작하는 직사각형 개수)를 모두 더한 만큼의 $dp$ 전이가 일어난다. 따라서 $O(N^2)$에 해결할 수 있다.

케이스워크를 통해서 $dp$ 전이를 선형에 할 수 있다. 그러면 $O(N)$ 또는 $O(NlogN)$에 문제를 해결할 수 있다.

 

G. One, Two, Three

0.0. $3$을 $-1$로 치환한 것을 $C$라고 하고 이의 prefix sum을 $S$라고 하자.

 

ex) A=1 2 2 3 3 1 -> C=1 2 2 -1 -1 1, S=1 3 5 4 3 4

 

0.1. $C$는 $A$와 mod 4로 같다. 따라서 어떤 구간의 $C$의 합이 $4$의 배수라면 $A$의 합도 $4$의 배수이다.

 

1. 모든 원소를 없앨 수 있는 필요충분조건은 $S[N]$이 $0$ 이상의 $4$의 배수인 것이다.

 

proof)

정방향은 자명하다. 역방향을 보이자.

 

$N$에 대한 귀납법을 사용해서 증명하자.

$N \leq 4$인 경우에는 전체 원소(A) 합이 $12$ 이하이다. $S[N]$이 $4$의 배수이므로 전체 원소(A) 합은 $4$의 배수이다. 전체 원소 합이 $12$인 경우는 $3$이 4개 있을 때 뿐인데 이는 $S[N] \geq 0$의 조건을 위배한다. 따라서 전체 원소 합이 $8$ 이하이다. 전체를 구간으로 잡아서 제거하면 해결된다.

 

$3$이 연속해서 있다면 끝에 있는 $1$혹은 $2$와 함께 $13$ 혹은 $233$을 구간으로 잡아서 제거할 수 있다. $S[N]$의 변화량은 $0$이고 $N$이 감소했기 때문에 귀납가설에 의해서 모든 원소를 없앨 수 있다.

 

이제 $3$이 연속해서 없다고 가정하자. $i < j$를 만족하면 $S[i] \leq S[j]+1$을 만족한다.(*)

 

$S[N] > 0$임을 가정하자. $S[0], S[1], \ldots, S[4]$ 중 $4$로 나눈 나머지가 같은 두 값이 존재한다. 각각 $S[p], S[q]$라고 하자. $p+1$부터 $q$까지 A의 합 4의 배수이므로 4 혹은 8이다. 이때 $C$의 합은 (*)에 의해서 0 이상이고, 따라서 0, 4 혹은 8이다. 8인 경우에는 $A[p+1], A[p+2], \ldots, A[q]$가 $2 2 2 2$인 경우밖에 없는데 이때 $q$를 $p+2$로 바꾸면 $C$의 합을 4로 바꿀 수 있다. $p+1$부터 $q$까지를 구간으로 잡아서 제거하면 $S[N]$은 $0$ 또는 $4$가 감소한다. 구간을 제거한 이후에도 $S[N]$이 $0$ 이상이므로 귀납가설에 의해 해결할 수 있다.

 

$S[N]=0$인 경우에 대해 알아보자.

$3$과 $1$이 인접하지 않는 경우에는 $3$이 연속해서 없다는 조건과 $S[N]=0$이라는 조건에 의해 $A=323$인 경우 밖에 없다. 이는 $N>4$라는 조건과 모순되기 때문에 항상 인접한 $3$과 $1$이 존재한다. 이 둘을 구간으로 묶어서 제거한 이후에 귀납가설을 적용하면 된다.

 

2. 각 원소들을 제거할지 안 제거할지를 정하자. 제거하기로 한 문자들은 구간을 이루는데, 각 구간은 1의 조건을 만족해야 한다.

 

ex) $A=2223222332$의 수열에서 $2[22]32[22332]$와 같이 제거한다고 하자. ([] 내부가 제거할 원소들) 각 구간들은 1의 조건을 만족한다. 

 

$dp[i]$를 $i$번째 원소 혹은 $i+1$번째 원소를 제거하지 않는 경우 pair($1$부터 $i$까지 원소들 중 제거하지 않는 문자들의 최소 합, -아름다움의 최대 합)으로 정의하자. (dp값이 pair이다) $0$번째 원소와 $N+1$번째 원소는 항상 제거하지 않는 것으로 간주하자. 

 

$i$번째 원소 혹은 $i+1$번째 원소를 제거하지 않는다는 것은 $i$번째 원소의 끝이 제거하는 원소가 이루는 구간 $a, a+1, \ldots, b$의 구간 끝 ($a$와 $b+1$)에 포함되거나 제거되지 않는 원소 $a$의 구간 끝($a$와 $a+1$)에 포함된다는 것이다. dp 전이에 초점을 두다 보니 dp배열의 정의가 자연스럽지 못하다.

 

$i$번째 원소를 제거하고 $i+1$번째 원소를 제거하지 않는 경우에는 $dp[i]=min(dp[j])$이다. 이때 $S[j]<S[i]$이고 $S[j]$와 $S[i]$를 $4$로 나눈 나머지가 같아야 한다.

$i$번째 원소를 제거하지 않는 경우에는 $dp[i]=dp[i-1]+pair(A[i], -B[i]))$이다.

 

따라서 전체 문제를 dp를 사용해서 $O(N^2)$에 해결할 수 있다.

 

3. $S[i]$를 4로 나눈 나머지에 따라 $i$의 그룹을 나누자. $dp[i]$를 $i$가 속한 그룹에서의 세그먼트 트리 연산으로 구할 수 있다. 따라서 전체 문제를 $O(NlogN)$에 풀 수 있다. (Challenge: 세그먼트 트리를 사용하지 않고 $O(N)$에도 풀 수 있다.)

 

4. 제거하는 원소들이 이루는 구간에 대해서 역추적을 어떻게 할지 생각해보자. 1의 귀납 가설에 의해 항상 $A$의 합이 $8$ 이하이고 $C$의 합이 $0$ 이상 $S[N]$ 이하이고 4의 배수인 구간이 존재한다. 이를 $O(N)$에 찾는 것을 반복해주면 $O(N^2)$에 역추적을 할 수 있다.

 

5. 원소들을 앞에서부터 보자. $1$번째 원소부터 $i$번째 원소까지 봤을 때 $i$번째 원소를 포함하는 제거할 수 있는 구간($C$의 합이 $0$ 이상 $S[N]$ 이하인 4의 배수)을 항상 제거해주도록 하자. 구간을 제거할수록 $S[N]$은 항상 감소하기 때문에 $C$의 합이 $S[N]$이하라는 조건에 의해 제거할 수 없었던 구간은 앞으로도 제거할 수 없다. 스택을 이용해서 관리해주면 $O(N)$에 역추적을 할 수 있다.