[UCPC 2022] 니은숲 예술가

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

 

대단한 문제라고 생각한다.

 

일단 $O(N^3)$ 솔루션은 어렵지 않게 이끌어낼 수 있다.

$D(i,j,k):=i-$정사각형에서 왼쪽 변이 $c_j\dots c_i$의 색을 포함하며 오른쪽 변이 $c_k\dots c_i$의 색을 포함하는 경우의 수.

 

점화식은 네 가지 전이를 갖는다. ($c_i\neq c_{i+1}$임은 전제한다.)

• $D(i,L,R) \leftarrow^+ D(i-1,L,R)$
• $D(i,R,i-1) \leftarrow^+ D(i-1,L,R)$ for $c_i \neq c_L \dots c_{i-1}$
• $D(i,i-1,L) \leftarrow^+ D(i-1,L,R)$ for $c_i \neq c_R \dots c_{i-1}$
• $D(i,i-1,i-1) \leftarrow^+ D(i-1,L,R)$ for $c_i \neq c_{\min\{L,R\}} \dots c_{i-1}$

네 부분에 속한 우변의 $L$, $R$ 첨자의 범위가 연속한 구간임을 알 수 있다. 따라서 구간 합을 이용 가능하다.

 

우변의 $i-1$, $L$, $R$의 범위를 잘 강제해보면 서로 간섭이 없는 관계임도 알 수 있다.

 

제일 의아하고 발견하기 어려웠던 점은, $D(i,L,R)$이 $i$와 관계없이 불변이라는 것이다.

즉, $L$, $R$을 떨거지 변으로 둔다면, 정사각형 사이즈를 늘리기 위해 $L$, $R$의 반대 방향으로 계속 쌓는 것 밖에 방법이 없다는 것.

 

DP 테이블을 상상한다면, $i$번째 정사각형을 다루는 전이가 아래와 같은 형태가 된다.

 

참조하는 값들이 row, col이라서 세그트리를 활용하는 것도 가능해 보인다. 그런 점이 며칠 전 코포에 나왔던 https://mathsciforstudent.tistory.com/452#article-5--d2--inversion-graph-coloring-(hard)와 비슷하다고 생각된다.