색종이 붙이기

문제 링크

 

1. $N, M \leq 400$

 

모든 칸을 다 덮을 수 있는 색종이의 집합을 $S$라고 하자. 각 $w$에 대해서 $(w, h) \in S$인 $h$의 범위는 $h \leq f(w)$의 형태로 나타난다. 이때 $f(w)$는 $w$에 대한 감소 함수이다.

 

따라서 $(w, h) \in S$를 판별하는 결정 문제를 $O(N+M)$번 해결해주면 해당 문제를 해결할 수 있다. 이 문제는 prefix sum을 이용해서 $O(NM)$에 쉽게 해결할 수 있다.

 

2. Maximal rectangle에 대하여

 

Maximal 직사각형이란, 내부에는 칠해진 칸이 없고 해당 직사각형을 포함하는 직사각형은 내부에 칠해진 칸이 있는 직사각형을 의미한다. 다시 말하면 직사각형의 각 변의 테두리에 칠해진 칸이 있는 직사각형을 의미한다. 이러한 직사각형의 개수는 $O(NM)$개이다. 

maximal 직사각형의 조건을 조금 완화시켜, 왼쪽/오른쪽/윗변의 테두리에 칠해진 칸이 있는 직사각형의 개수를 세보자. 아랫변을 고정해보면, 칠해지지 않은 칸들은 히스토그램을 이룬다. 

밑변을 기준으로 칠하지 않은 칸들은 히스토그램을 이룬다. 빨간 직사각형은 완화된 maximal 직사각형의 예시이다.

히스토그램에서 완화된 maximal 직사각형의 개수는 $O(N)$개임은 well known fact이다. 각 maximal 직사각형 마다 최소 높이를 가지는 인덱스를 매칭시켜주면 일대일 매칭이 성립한다. 

각 색종이는 maximal 직사각형에 속한다. 따라서 $(w, h)$가 maximal 직사각형이라면 $f(w) \leq h$이다.

 

maximal 직사각형을 모두 구하는 것은 $O(NM)$에 할 수 있다. 각 밑변에 대해서 히스토그램에서 $N$개의 maximal 직사각형 구하는 것을 해주면 된다.

 

3. $(w, h) \in S$ 판별하기

$f(1)$는 $O(NM)$에 쉽게 구할 수 있다. $f(i)$를 알고 있을 때 $f(i+1)$을 구하는 방법을 알아보자.

 

직사각형 $A$의 가로/세로 길이가 $B$의 가로/세로 길이보다 모두 크거나 같다면 $A$가 $B$보다 뛰어나다고 하자. $(w, h) \in S$인 것과 필요충분의 조건은 각 칠해지지 않은 칸은 자신을 포함하고 $(w, h)$보다 뛰어난 maximal 직사각형이 존재하는 것이다.

 

$(i, f(i))$보다 뛰어난 maximal 직사각형 중 가로의 길이가 $i+1$ 이상인 직사각형은 $(i+1, h) \in S$를 판별할 때에도 $(i+1, h)$보다 뛰어난 maximal 직사각형이 될 것이다. 이는 $h \leq f(i)$인 $h$에 대해서만 $(i+1, h) \in S$ 판별을 진행하기 때문이다. 따라서 가로 길이가 정확히 $i$인 maximal 직사각형들만 $(i+1, h)$보다 뛰어난 maximal 직사각형에서 제외된다.

 

가로의 길이가 $i$인 maximal 직사각형 내부에 있는 칸들만 $(i+1, h)$보다 뛰어난 maximal 직사각형으로 덮을 수 있다면 해결이다. 이는 직사각형의 오른쪽/왼쪽 가장자리에 칠해진 칸과 인접한 칸을 덮는 가로 길이 $i+1$ 이상의 maximal 직사각형이 있으면 된다. 대략적인 증명은 그림으로 대체한다.

가로 길이 $i$의 maximal 직사각형은 검은색으로, 가로 길이 $i+1$ 이상의 maximal한 직사각형은 빨간색과 파란색으로 그렸다.

 

이러한 칸의 개수는 오른쪽/왼쪽 테두리에 칠해진 칸의 개수와 동일하다. 모든 maximal 직사각형에 대해 오른쪽/왼쪽 테두리에 칠해진 칸의 개수의 합은 $O(NM)$의 bound를 가진다. 이는 각 maximal 직사각형을 히스토그램으로 생각했을 때, 기존 직사각형과 확장된 maximal 직사각형 사이의 관계는 히스토그램 상에서 카르테시안 트리의 부모/자식 관계와 같기 때문이다. $f(i+1)$은 가로 길이 $i$의 직사각형을 덮는 가로 길이 $i+1$ 이상의 maximal 직사각형 중 최소 높이가 된다.

 

각 가로 길이가 $i+1$ 이상인 maximal 직사각형은 이분탐색으로 $O(logN)$에 구할 수 있다. 따라서 해당 문제를 $O(NMlogNM)$에 풀 수 있다.