[PS/CP 공부기록] 02. System of Difference Constraints

※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.

 

이전 공부기록에 이어서, 그래프에서의 relaxation 개념과 더욱 친숙해지고자 이 주제를 고르게 되었다.

 

개요

 

이번 글에서 살펴볼 주제는 System of Difference Constraints이다.

일반적으로 LP(Linear Programming; 선형계획법)은 PS/CP의 범위에서 쉽게 해결하기 어렵다. 그러나 몇몇 형태의 LP 문제는 풀기 쉬운 다른 형태의 문제로 변형할 수 있다.

 

이 글에서는 해결하기 쉬운 LP 문제의 형태 중 하나인 system of difference constraints를 알아보자.

 

System of Difference Constraints

 

System of Difference Constraints는 변수 \(x_1\), \(x_2\), \(\cdots\), \(x_n\)와 상수 \(c_1\), \(c_2\), \(\cdots\), \(c_m\)에 대하여 \(x_j-x_i\le c_k\)꼴의 여러 부등식으로 구성된 연립부등식을 말한다. \(c_k\)는 음수일 수도 있다.

 

변수와 부등식의 개수가 많아지면 주어진 연립부등식의 해가 존재하는지조차 빠르게 판단하기 어려워진다. 따라서, system of difference constraints를 푼다는 것은 일반적으로 (1)해의 존재성을 판단하고, 해가 존재한다면 (2) 실제로 가능한 해를 하나 구하는 것을 뜻한다.

 

Constraints Graph

 

다음과 같이 system of difference constraints에 대응되는 그래프인 Constraints Graph를 만들자. 이 그래프는 weighted directed graph이다.

 

(1) 각각의 변수 \(x_i\)에 대응되는 정점 \(v_i\)를 생성한다.

(2) 각각의 Difference Constraint \(x_j-x_i\le c_k\)에 대응되는 간선을 생성한다. 이 간선은 정점 \(v_i\)에서 \(v_j\)로 향하는 가중치 \(c_k\)의 간선이다.

 

두 정점 \(v_p\)와 \(v_q\)에 대하여 \(v_p\)에서 \(v_q\)로 향하는 경로 \(P\)에 대응되는 difference constraints를 나열하고 이들을 모두 합하면 \(\displaystyle x_q-x_p\le \sum c_k\)가 된다. 이 때 \(\displaystyle \sum c_k\)는 경로에 포함된 간선의 가중치의 합을 나타낸다.

 

위의 관찰에 따라, 서로 다른 두 변수 \(x_i\)와 \(x_j\)에 대하여 \(v_i\)에서 \(v_j\)로 도달 가능한 경로가 존재하는 경우, \(x_j-x_i\)의 값은 항상 \(v_i\)에서 \(v_j\)로의 최단 경로의 길이 이하임을 알 수 있다. 따라서 \(x_i\)들의 값은 constraints graph에서의 최단거리 제약을 만족해야 함을 알 수 있다.

 

한편, 위 constraints graph에 가상의 정점 \(v'\)을 하나 추가하고, \(v'\)에서 각각의 \(v_i\)로 가중치 0인 간선을 그어보자. 이 때, \(v'\)로부터 \(v_i\)까지의 최단거리는 앞서 살펴본 constraints graph에서의 최단거리 제약을 모두 만족함을 어렵지 않게 알 수 있다. (최단거리의 성질과 relaxation에 대해 잘 생각해보자.)

 

두 정점 사이에 최단경로가 존재하지 않는 경우는 두 가지가 있는데, 하나는 \(v_i\)에서 \(v_j\)로 도달 가능한 경로가 존재하지 않는 경우이고 다른 하나는 경로 중간에 negative cycle이 존재하는 경우이다. 경로가 존재하지 않는 경우, \(v_j-v_i\)에 대한 \(v_j-v_i\le c_k\)꼴의 제약이 없다는 뜻이므로 그 값은 어떤 값이 되어도 상관없다. 반면 negative cycle이 존재하는 경우, (엄밀한 표현은 아니지만) \(v_j-v_i\le -\infty\)가 성립한다는 뜻이므로 주어진 system of difference constraints는 해가 없음을 알 수 있다.

 

문제 특성상 가중치가 음수인 간선이 등장하고 negative cycle도 발견해야 하므로, 음수 간선이 있는 경우에도 효과적으로 동작하는 최단거리 알고리즘을 활용해야 한다. 일반적으로 PS/CP에서 system of difference constraints를 풀 때에는 Bellman-Ford를 이용한다.

 

식 정리 패턴

 

이 문단에서는 PS/CP에서 볼 수 있는 system of difference constraints 유형의 문제에서 식을 정리할 때 쓰이는 몇 가지 패턴을 소개한다. 각각만 놓고 보면 당연해 보이지만, 처음 보거나 익숙하지 않으면 떠올리기 어려울 수 있으니 유의하자.

 

(0) \(x_j-x_i\ge k\) 형태

위 부등식은 \(x_i-x_j\le -k\)와 같이 변형이 가능하다.

 

(1) \(x_j-x_i=c_k\) 형태, \(x_i=x_j\) 형태

종종 연립부등식으로 나타나는 조건과 함께 \(x_j-x_i=c_k\) 형태의 등식을 같이 만족시키는 해를 찾을 것을 요구하는 문제가 출제된다. 이 경우 해당 등식을 \(x_j-x_i\le c_k\)와 \(x_j-x_i\ge c_k\)의 두 부등식으로 나누어 생각해 조건을 difference constraints로 변형할 수 있다.

 

물론 \(x_i=x_j\) 또한 \(c_k\)가 0인 특수한 경우로 보고 똑같이 변형할 수 있다.

 

(2) \(x_i\le k\) 형태, \(x_j\ge k\) 형태

 0을 나타내는 가상의 정점 \(v\)를 하나 생각하면, \(x_i\le k\)는 \(x_i-0\le k\), \(x_j\ge k\)는 \(x_j-0\ge k\)이므로 \(v\)를 활용한 그래프 모델링을 생각할 수 있다.

 

(3) 구간합

\(x_i+x_{i+1}+\cdots+x_j\le k\) 꼴의 부등식으로 이루어진 연립부등식은 이 글에서 설명한 system of difference constraints의 형태는 아니다. 그러나 \(x_i\)의 prefix sum인 나타내는 \(p_i\)를 이용하면 위 연립부등식을 \(p_j-p_{i-1}\le k\) 꼴의 \(p_i\)에 대한 system of difference constraints로 변형할 수 있다.

 

(4) 로그

\(\frac{x_j}{x_i}\le c_k\)꼴의 연립부등식이 주어진다면 양변에 로그를 취해 \(\log x_j-\log x_i \le \log c_k\)의 형태로 변형할 수 있다. 이는 \(\log x_i\)들에 대한 difference constraints로 생각할 수 있다.

 

예시 문제: [LuoguP4926] 倍杀测量者

 

관련 문제

 

[BOJ2081] 저울추
직관적으로 system of difference constraints 문제임을 알 수 있다.

구한 저울추의 질량이 각각 1 이상 1000000 이하의 정수여야 한다는 조건까지 그래프 모델링에 포함시켜 구현하자.

 

[BOJ7634] Guessing Game

\(b'_i=-b_i\)로 설정하면 지문의 모든 제약을 difference constraints로 바꾸는 데에 어려움이 없다.

[BOJ4109] The Ninja Way
수직선에서 인접한 두 트리 사이의 위치관계와 크기순으로 인접한 두 트리 사이의 위치관계를 difference constraints로 표현할 수 있다.

가장 낮은 나무의 좌표를 \(x_l\), 가장 높은 나무의 좌표를 \(x_h\)라 하자. 이 때, \(x_l<x_h\)라면 \(x_l-x_h\)의 최댓값이 문제의 답이 되고, \(x_h<x_l\)이라면 \(x_h-x_l\)의 최댓값이 문제의 답이 된다.

[BOJ27400] Restore Array
prefix sum을 이용하면 구간의 정보를 difference constraints의 형태로 변형할 수 있다.

 

[BOJ29765] PAndOrA

정수의 and 및 or 연산의 결과는 각 비트마다 독립적이므로 비트별로 문제를 해결해도 상관없다.

각 비트 별로 주어진 구간 쿼리를 만족시키려면 켜져 있는 비트의 개수가 어때야 하는지에 대한 제약을 prefix sum에 대한 difference constraints로 나타내는 것으로 비트별 문제를 해결할 수 있다.

[BOJ7332] 편의점 알바
많은 문제가 그렇듯이, 단조성이 있다면 이분 탐색을 같이 활용할 수 있다. 이 문제에서는 \(x\)명을 고용해 필요한 알바 수를 충족시킬 수 있다면 더 많은(물론 \(N\) 이하) 알바를 고용해도 충족이 항상 가능할 것이고, \(x'\)명을 고용해서는 필요한 알바 수를 충족시킬 수 없다면 더 적은 알바를 고용해도 충족이 항상 불가능하다는 점을 활용하여 이분탐색을 진행할 수 있다.

 

[BOJ19153] Jordan
본문에 직접적으로 적힌 조건 중에는 이렇다 할 부등식 형태의 조건이 보이지 않는다. 그러나 이 문제 역시 prefix sum을 이용해 나타낸 difference constraints 형태로 나타내 해결할 수 있다.

단, 좌표압축 후에 각 정점이 원래 배열에서 무엇을 의미하는지에 유의하여야 한다.

 

참고 자료

 

CLRS 24.4