백준27400 Restore Array

작성일 | In

문제 링크

  • http://icpc.me/27400

사용 알고리즘

  • 벨만 포드

시간복잡도

  • $O(N(N+M))$

풀이

배열의 누적 합 $S_i = \sum_{k=1}^{i} A_k$를 생각해 봅시다. $[l, r]$ 구간에서 $k$번째로 작은 값이 0일 때와 1일 때로 나눠서 볼 것입니다.
만약 $v = 0$이면 $[l, r]$ 구간에서 1의 개수가 최대 $(r-l+1) - (k+1) + 1$개가 됩니다. 따라서 $S_r - S_{l-1} \leq r-l-k+1$이 성립해야 합니다.
반대로 $v = 1$이면 $[l, r]$ 구간에서 1의 개수가 최소 $(r-l+1) - k + 1$개가 됩니다. 따라서 $S_r - S_{l-1} \geq r-l-k+2$가 성립해야 합니다.

이런 꼴의 연립 부등식은 그래프의 최단 거리로 모델링할 수 있음이 잘 알려져 있습니다. 식을 조금 변환하면 $v = 0$일 때 $S_r \leq S_{l-1} + (r-l-k+1)$, $v = 1$일 때 $S_{l-1} \leq S_r-(r-l-k+2)$를 얻을 수 있습니다.
이 부등식 말고 필요한 부등식이 더 있는데, $S_i$가 $S_{i-1} + 0$ 또는 $S_{i-1} + 1$이라는 것을 보장하기 위해 $S_i \leq S_{i-1} + 1$과 $S_{i-1} \leq S_i$가 필요합니다.

간선 $O(N+M)$개를 잘 만들었다면 벨만 포드 알고리즘을 이용해 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

ll N, M, D[5050];
vector<pair<int,int>> G[5050];
inline void AddEdge(int s, int e, int w){ G[s].emplace_back(e, w); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) AddEdge(i-1, i, 1);
    for(int i=1; i<=N; i++) AddEdge(i, i-1, 0);
    for(int i=0; i<M; i++){
        int l, r, k, v; cin >> l >> r >> k >> v; l++; r++;
        if(v == 0) AddEdge(l-1, r, r-l+1-k);
        if(v == 1) AddEdge(r, l-1, -(r-l+1-k+1));
    }
    memset(D, 0x3f, sizeof D); D[0] = 0;
    for(int iter=0; iter<=N; iter++){
        bool change = false;
        for(int i=0; i<=N; i++) if(D[i] != INF) for(auto [j,w] : G[i]) if(D[j] > D[i] + w) D[j] = D[i] + w, change = true;
        if(iter == N && change){ cout << -1; return 0; }
    }
    for(int i=1; i<=N; i++) cout << D[i] - D[i-1] << " ";
}