ARC069 F. Flags

algorithm-ps ― [ 2-sat , algorithm-ps , atcoder ]

수직선상에 깃발 \(N\)개를 놓되, \(i\)번째 깃발은 \(x_i\) 또는 \(y_i\)에 놓아야 한다. 이 때 깃발들 사이의 최소 거리의 최댓값을 구하는 문제이다. 문제 링크

Solution sketch

일단 파라메트릭 + 2-SAT을 해야 한다는 것 까지는 자명한 관찰이다. 즉, “가장 가까이 있는 깃발이 \(d\) 이상 떨어져 있게 할 수 있는가?”에 관한 문제를 풀자. 그런데 2-SAT에 사용할 그래프 에지를 단순하게 만들면 \(O(N^2)\)개가 된다.

Idea 1. 2-SAT Segment Tree

편의상 \(x\)좌표들을 정렬된 순서대로 \(p_{1}, p_{2}, \cdots,\)라 두자. 앞으로 특별한 말이 없으면 “\(i\)번째 위치…”와 같은 말은 모두 \(p_{i}\)로 해석하면 된다.

Segment tree를 하나 빌드하는데, [s,e]의 노드는 “[s,e]번 위치에는 전부 깃발이 놓이지 않는다”라는 명제로 해석한다. [s,e] → [s,m] && [s,e] → [m+1,e]만 간선을 통해 강제하면 이 트리의 노드들을 자유롭게 쓸 수 있다.

Idea 2. Interval update

\(i\)번째 위치에 깃발이 놓이는 상황을 생각하면, \((p_{i}-d, p_{i}+d)\)에는 깃발이 놓일 수 없다. 따라서 해당 구간의 양 끝에 해당하는 인덱스 L, R을 lower/upper_bound로 결정해 주고, 세그트리에 update(L, i-1); update(i+1, R); 쿼리를 날려주자.

update(A, B) 쿼리 내부는 세그트리의 구간 업데이트와 비슷하게 생겼다. 이미 세그트리를 만드는 과정에서 리프들까지 정보가 전달되므로, [s,e][A, B]에 포함되면 [s,e]에 해당하는 노드에 간선을 잇고 빠져나오면 된다.

Analysis

세그트리는 “깃발이 없는” 쪽에만 만들면 충분하다. 여기서 노드가 \(8N\)개 정도 필요하다.

“깃발이 있다”를 표현하는 노드가 \(2N\)개 정도. 따라서 2-SAT에 들어가는 노드 개수는 약 \(10N\)개이다.

매번 간선이 \(O(N\log N)\)개씩 나오니까, 파라메트릭까지 합치면 \(O(N\log N\log X)\) 시간과 \(O(N\log N)\) 메모리로 문제를 해결할 수 있다.

Written on January 8, 2020