산 밀어버리기

각 위치 $i$를 덮는 사용된 폭탄의 수를 $C_i$라고 하자. 폭탄을 모두 사용한 뒤 $i$번째 높이가 $0$이 되기 위한 필요충분조건은 $C_i \geq A_i$이다. 따라서 각 폭탄을 최대 한 번 선택하면서 모든 구간 덮기 하한을 만족하는 최소 비용 부분집합을 구하면 된다.

정점 $0,1,\ldots,N$으로 이루어진 최소 비용 유량 그래프를 만든다.

• 각 $i$ ($1 \leq i \leq N$)에 대해 간선 $i-1 \rightarrow i$를 용량 $M-A_i$, 비용 $0$으로 추가한다.
• 각 폭탄 $j$에 대해 간선 $L_j-1 \rightarrow R_j$를 용량 $1$, 비용 $W_j$로 추가한다.

정점 $0$에서 정점 $N$으로 정확히 $M$의 유량을 보내는 최소 비용을 구한다. $A_i>M$인 위치가 있으면 용량 $M-A_i$를 만들 수 없으므로 즉시 불가능하다.

위치 $i$에 대응하는 컷을 생각하자. 이 컷은 정점 $0,1,\ldots,i-1$과 정점 $i,i+1,\ldots,N$을 나눈다. 그래프의 모든 원래 간선은 번호가 작은 정점에서 큰 정점으로 향하므로, 값이 $M$인 유량은 이 컷을 정확히 $M$만큼 통과한다.

간선 $i-1 \rightarrow i$가 운반할 수 있는 유량은 최대 $M-A_i$이다. 따라서 나머지 유량 중 최소 $A_i$는 폭탄 간선을 통해 컷을 건너야 한다. 폭탄 간선 $L_j-1 \rightarrow R_j$가 이 컷을 건너는 것은 정확히 $L_j \leq i \leq R_j$일 때이다. 그러므로 유량이 사용하는 폭탄 간선들은 위치 $i$를 적어도 $A_i$번 덮는다.

반대로 조건을 만족하는 폭탄 부분집합이 있다고 하자. 선택한 각 폭탄에 서로 다른 하나의 유량 경로를 배정한다. 그 경로는 $0$에서 $L_j-1$까지 비용 $0$ 간선을 지나고, 폭탄 간선 $L_j-1 \rightarrow R_j$를 지난 뒤, 다시 비용 $0$ 간선을 따라 $N$으로 간다. 선택하지 않은 나머지 경로는 모든 비용 $0$ 간선을 지난다.

위치 $i$의 비용 $0$ 간선을 지나는 경로 수는 $M-C_i$이다. $C_i \geq A_i$이므로 $M-C_i \leq M-A_i$이며 모든 용량 제한을 만족한다. 따라서 모든 가능한 폭탄 선택은 같은 비용의 값 $M$ 유량으로 표현할 수 있다.

모든 용량이 정수이므로 최소 비용 유량의 최적해도 정수 유량으로 얻을 수 있다. 용량이 $1$인 폭탄 간선에 유량이 흐르는지를 해당 폭탄의 선택 여부로 해석하면 된다. 두 방향의 대응에서 비용도 정확히 보존되므로 최소 비용 유량의 값이 정답이다.

정점 수는 $N+1$, 간선 수는 $O(N+M)$이다. 잠재치를 사용하는 다익스트라 기반 연속 최단 경로 알고리즘으로 최대 $M$번 증강하면 시간 복잡도는 $O(M(N+M)\log N)$이고, 공간 복잡도는 $O(N+M)$이다.

Solution written by GPT5.6