Setting Three Contests

각 대회에 속한 문제들을 마감 시각이 증가하는 순서로 정렬한다. 같은 대회의 두 문제가 이 순서를 어기고 있다면 두 문제의 위치를 바꾸어도 전환 횟수는 변하지 않고, 더 이른 마감의 문제가 더 일찍 끝나므로 불리해지지 않는다. 따라서 각 대회 내부의 순서는 고정된 세 개의 수열로 생각할 수 있다.

$x$번 대회의 문제 수를 $m_x$라 하고, 정렬된 문제의 준비 시간과 마감 시각을 각각 $E_{x,r},D_{x,r}$라 하자. 마감 시각을 뒤에서부터 다음과 같이 보정한다.

$$D_{x,r}\leftarrow\min(D_{x,r},D_{x,r+1}-E_{x,r+1})\qquad(1\leq r<m_x).$$

이 보정은 가능 여부를 바꾸지 않는다. 원래 일정에서 $r$번 문제를 끝낸 뒤 같은 대회의 $r+1,r+2,\cdots,q$번 문제를 처리하려면 적어도 그 문제들의 준비 시간 합만큼 시간이 더 필요하다. 따라서 원래 가능한 일정도 보정된 모든 마감 시각을 자동으로 만족한다. 반대로 보정된 마감 시각은 원래 마감 시각 이하이므로 보정된 조건을 만족하면 원래 조건도 만족한다.

보정 후에는 다음 관계가 성립한다.

$$D_{x,r}+E_{x,r+1}\leq D_{x,r+1}.$$

따라서 어떤 대회의 문제를 마지막으로 처리한 상태가 가능하다면, 다른 대회로 전환하지 않고 그 대회의 다음 문제를 계속 처리하는 것도 항상 가능하다.

$P_x[r]=E_{x,1}+E_{x,2}+\cdots+E_{x,r}$라 하자. 세 대회에서 각각 개의 문제를 처리했고 마지막 문제가 번 대회라면, 전환 횟수가 일 때 현재 시각은

$$P_1[a]+P_2[b]+P_3[c]+Ks$$

이다.

$\operatorname{dp}_1[a][b][c]$를 이러한 상태를 만드는 최소 전환 횟수라 정의하고, 마지막 대회가 $2,3$인 배열도 같은 방식으로 정의하면 직접적인 풀이는 $O(m_1m_2m_3)$이다.

보정된 마감 시각 때문에 한 축을 없앨 수 있다. $b,c$를 고정하고 $a$만 변화시키면 $\operatorname{dp}_1[a][b][c]$는 어떤 위치 전까지는 불가능하고, 처음 가능해진 위치부터는 같은 값으로 유지된다. 이 성질은 전체 처리 문제 수에 대한 귀납법으로 보일 수 있다. 같은 대회를 계속 처리하는 전이는 값을 그대로 오른쪽으로 전파하고, 다른 대회에서 들어오는 전이는 처음 가능한 위치 하나를 만든 뒤 같은 방식으로 그 뒤 전체에 전파된다.

따라서 다음 쌍만 저장한다.

• $F_1[b][c]=(a,s)$: $1$번 대회 문제를 마지막으로 처리하는 상태가 처음 가능해지는 최소 $a$와 그때의 전환 횟수 .

예를 들어 $F_1[b][c]=(a,s)$라고 하자. 현재 마지막 블록에서 $1$번 대회 문제를 더 처리하여 정확히 $q$개까지 처리한 뒤 번 대회로 전환할 수 있다. 번 대회의 다음 문제까지 처리했을 때의 조건은

$$P_1[q]+P_2[b+1]+P_3[c]+K(s+1)\leq D_{2,b+1}$$

이다. $P_1$은 증가하므로 가능한 $q$는 빈 구간이거나 $[a,r]$ 꼴의 연속 구간이다. $r$은 이분 탐색으로 구할 수 있다. 이 구간의 모든 $$에 대해

$$F_2[q][c]\leftarrow\min(F_2[q][c],(b+1,s+1))$$

이라는 구간 갱신을 한다. 나머지 다섯 종류의 전이도 완전히 대칭적이다.

상태 후보 $(h,s)$의 우선순위를 $({\rm row}+{\rm column}+h,s)$로 둔다. 첫 번째 값은 그 후보가 처음 나타내는 상태에서 처리한 문제의 총개수이다. 모든 전이는 이 값을 적어도 $1$ 증가시키므로, 현재 우선순위가 가장 작은 상태는 이후의 전이로 더 좋아질 수 없다. 상태를 확정한 뒤 두 전이 구간을 추가하면 된다.

각 $F_x$ 표에는 한 이전 대회에서 행 방향 구간 갱신이 들어오고, 다른 이전 대회에서 열 방향 구간 갱신이 들어온다. 구현에서는 표를 두 방향으로 각각 한 번씩 저장한다. 각 복사본은 다음 연산을 지원해야 한다.

• 구간의 값에 후보 쌍과의 최솟값을 취한다.
• 확정된 한 위치를 삭제한다.
• 전체 위치 중 우선순위가 가장 작은 후보를 찾는다.

쌍을 사전순으로 하나의 정수에 인코딩하면 구간 연산은 range chmin이 된다. 세그먼트 트리 비츠에서 구간의 최댓값과 두 번째 최댓값을 관리하면 한 번의 갱신을 $O(\log N)$ 상각 시간에 처리할 수 있다. 최댓값을 가진 원소들 중 행과 열의 합이 최소인 위치와, 최댓값이 아닌 원소들의 최적 우선순위도 함께 관리하면 전체 최솟값을 루트에서 바로 얻을 수 있다.

확정되는 상태 수는

$$(m_2+1)(m_3+1)+(m_1+1)(m_3+1)+(m_1+1)(m_2+1)=O(N^2)$$

이다. 각 상태는 상수 번의 구간 갱신과 점 삭제를 발생시키므로 시간 복잡도는 $O(N^2\log N)$, 메모리 복잡도는 $O(N^2)$이다.

Solution written by GPT5.6