ICPC 2019 Seoul Regional E번 Network Vulnerability

문제 링크: https://www.acmicpc.net/problem/17972

17972번: Network Vulnerability

 

240402 수정) 3에서 풀이가 틀렸다. $(l_{i+1}, l_i)$에 구간이 존재하는 것 뿐만 아니라 구간들이 하나의 컴포넌트를 이루어야 한다. 내 솔브닥 레이팅 2점...

 

240404 수정) 풀이를 살렸다! 등호 하나를 부등호로 바꾸면 된다.

 

0. 몇 개의 구간을 제거해서 만든 interval graph가 아닌 몇 개의 구간을 선택해서 해당 구간으로 이루어진 interval graph를 살펴보자. 또한, 좌표압축을 통해 각 좌표의 범위를 $1$부터 $2N$ 사이로 하자.

 

1. 모든 $k$에 대해서 $c_k(G)$의 최댓값을 구하는 것은 쉽다. 구간 $N$개 끝점이 증가하는 순서로 정렬하고 앞에서부터 보면서 마지막에 선택한 구간의 끝점보다 현재 보는 구간의 시작점이 크면 선택하는 그리디한 전략으로 $O(NlogN)$에 구할 수 있다. 앞으로는 컴포넌트가 $p$개가 되도록 할 때 $1 \leq p \leq max(c_k(G))$를 만족하는 $p$에 대해서만 생각한다.

 

2. 컴포넌트가 $p$개가 되도록 구간을 선택하자. 어떤 $p \leq r_p$가 존재해서 구간 $i$개를 선택해서 컴포넌트가 $p$개가 되었다면 $i \in [p, w_p]$라는 것이다. 즉, 선택할 수 있는 구간의 개수는 구간을 이룬다. 증명은 다음과 같다.

 

컴포넌트가 $w_p$개가 되도록 구간들을 고르자. 그렇다면 각 컴포넌트는 연결 그래프를 이룬다. spanning tree를 잡은 뒤에 리프부터 하나씩 제거해 나가면 각 컴포넌트마다 연결성을 유지하면서 구간을 하나씩 제거할 수 있다. 최종적으로는 각 컴포넌트마다 정점이 하나씩 남아서 구간이 $p$개 밖에 안 남는다.

 

그렇다면 컴포넌트가 $p$개 이상이도록 구간을 $i$개 선택했다면 $i$는 $\bigcup_{i=p}^{max(c_k(G))} [i, r_i]$에 속한다. 우변에 있는 구간들의 합집합 역시 구간이다! 우변을 $[p, r_p]$로 정의하자.

 

3. 컴포넌트가 $p$개 이상이라는 것은 다음과 같다.

• 반정수(정수+0.5)꼴의 수 $l_0=\infty > l_1 > l_2 > \cdots > l_{p-1} > l_p=-\infty$가 존재해서 $(l_{i+1}, l_i)$에 포함되는 구간이 존재하고 $l_i$를 포함하는 구간은 존재하지 않는다.

따라서 우리는 $dp[i][j]$를

 

$l_j=i+0.5$인 경우 $[i+1, 2N]$에 포함되는 구간 중 어떠한 $l_k$도 포함하지 않는 구간의 개수

 

로 정의할 수 있다. $r_p=max_i(dp[i][p-1]+[1, i]$에 속하는 구간의 개수$)$로 구할 수 있다. dp값을 naive하게 구하면 $O(N^3)$에 구할 수 있다. 구체적인 전이 과정은 다음과 같다.

 

각 $i$에 대해서 $l_i$를 $[i+0.5, l_i+0.5]$에 포함되는 구간이 존재하는 최소 자연수 $l_i$를 정의하면,

$dp[i][j]=max_{l_i \leq k} dp[k][j-1]+$ $[i+0.5, k+0.5]$에 속하는 구간의 개수

로 구할 수 있다.

 

4. $i$를 감소시키면서 $arr[k][j]=(dp[k][j]+[i+0.5, k+0.5]$에 속하는 구간의 개수$)$ 인 2차원 배열 $arr$를 관리하자. 이를 segment tree로 관리하면 $O(N^2logN)$에 관리할 수 있다. 각 $dp$값당 arr 배열의 구간 쿼리로 구할 수 있기 때문에 dp 배열 역시 $O(N^2logN)$에 채울 수 있다. 

 

한 가지 알아두면 좋은 점은, $dp[i][j]$를 구하는데 $dp[i'][j-1]$ 꼴만 필요하다는 것이다. $j$에 따른 스위핑을 통해 메모리 $O(N)$에 문제를 해결할 수 있다.