Problem Solving Diary #18

BOJ 15481. 그래프와 MST

일단 원래 그래프의 MST를 구한다. 그리고 각 간선에 대해, 해당 간선의 양끝점을 잇는 경로에서 가장 큰 가중치를 가지는 간선을 빼 주고 해당 간선을 넣으면 이것이 가장 싼 MST가 된다. 구현은 LCA와 sparse table을 잘 이용하면 HLD + segment tree 없이도 할 수 있다. 시간 복잡도는 $\mathcal{O}(M \log N)$이다.

BOJ 30896. 두 팀으로 나누기

두 팀의 $\min(A_i)$와 $\sum B_i$를 각각 $a_1$과 $a_2$, $b_1$과 $b_2$라고 하자. $a_1$과 $a_2$ 중 하나는 $\min_{1 \le i \le N} A_i$이다. WLOG $a_1$이라고 하자. $a_2$를 정하는 방법은 최대 $100$가지가 있다. 모든 $100$가지 방법에 대해, $a_1 \le a_i < a_2$인 사람들은 1팀으로 들어가는 것이 확정된다. 이제 두 팀에 어떤 방식으로 실력을 나눠줄 수 있는지를 구하면 되는데, 비트셋을 이용한 냅색을 해 주면 된다. 시간 복잡도는 $\mathcal{O}(100^2 N^2 /w)$이다.

BOJ 30509. 그래서 나는 코딩을 그만두었다

먼저 다음을 관찰하자.

• 휴식은 맨 처음 몰아서 하는 게 이득이다.
• $x>0$이고, $x$번의 대결을 방학 중에 할 수 있다면, $x-1$번의 대결 역시 할 수 있다. 즉, $x$에 대한 parametric search를 쓸 수 있다.
• 만약 승리할 수 있는 학생이 있다면, 아무나 골라도 똑같다. 어차피 자신의 실력에는 변화가 없기 때문에, 누굴 먼저 골라도 최종적으로 쌓이는 멘탈에는 변화가 없다.
• 만약 승리할 수 있는 학생이 없다면, 더 이상 승리하는 것이 불가능하므로, 멘탈 수치 감소량을 최소화해야 한다. 되도록 실력이 높은 학생을 고르는 것이 이득이다.

위 전략으로 그리디하게 문제를 $\mathcal{O}(N \log^2 N)$ 또는 $\mathcal{O}(N \log N)$에 해결할 수 있다.

BOJ 30183. 히스토그램 K개 빼기

일단 답이 되는 직사각형이 어떤 형태인지를 생각해 보자. 직사각형이 있는 구간에서 가장 낮은 막대가 직사각형의 높이를 고정할 것이다. 또한, 그 막대 주변으로 어떤 막대들을 추가적으로 남겨 놓는지가 직사각형의 넓이와 $K$를 결정할 것이다. 구간에서 가장 낮은 막대의 위치를 $m$이라고 하고, 직사각형의 양 끝 막대를 $l$과 $r$이라고 하자. 그렇다면 $[l, r]$ 구간에서 $H_i < H_m$인 $i$들을 비활성화시키고 남은 막대들을 활성화시켜야 할 텐데, 이때 활성화된 막대의 수가 직사각형의 너비와 같다. 이 너비를 $r$이라고 하고, 그 사이에 비활성화된 막대들의 개수를 $d$라고 하자. $r$이 같다면 $d$를 최대한 줄이는 것이 이득이 된다.

 

$m$을 고정했기 때문에, $H_i < H_m$인지 아닌지 여부만 중요하다. 새로운 이진수열 $A$를 정의해, $H_i \ge H_m$이면 $A_i = 1$, 그렇지 않다면 $A_i = 0$이라고 하자. 목표는 모든 $K$에 대해, $m$을 포함하고 $A_i=1$인 $i$가 $K$개 이상 존재하는 구간 $[l, r]$의 길이의 최솟값을 구하는 것이다. $A_i = 1$인 $i$들만 모아 배열 $B$에 저장해 둔다면, 이는 $B_j - B_{j-K+1}$의 최솟값을 모든 $K$에 대해 구하는 문제가 된다. 만약 이 문제를 빠르게 푸는 방식으로 문제를 해결해야 한다면, 모든 $m$에 대해 한 번씩 해 봐야 하니 대략 $\mathcal{O}(N)$이나 $\mathcal{O}(N \log N)$ 정도의 시간에 풀어야 할 것이다. 그런데, 이 문제는 정말 풀기 어렵다. 아마 제곱 미만에 안 되는 것으로 알고 있다.

 

시간 복잡도를 줄이기 위해서는 문제를 조금 다른 시각에서 바라보아야 한다. 직사각형의 가장 왼쪽 막대 $l$과 가장 오른쪽 막대 $r$ 사이의 간격 $r-l=d$를 고정하자. 이제 모든 막대 $x$에 대해, $d$가 고정되었을 때 $[l, r]$ 사이에서 $H_i \ge H_x$인 $i$의 개수의 최댓값을 구하고자 한다. 이것은 $x$를 높이가 작은 것부터 늘려 가며, 모든 길이 $d$인 구간에 대해 $H_i \ge H_x$인 것의 개수를 담은 수열 $B$를 만든 뒤 $B$를 세그먼트 트리로 관리하면서 풀 수 있다. 이 과정은 $\mathcal{O}(N^2 \log N)$에 처리할 수 있다.

 

이 데이터를 바탕으로 답을 어떻게 만들 수 있을까? $d$와 $x$가 주어졌을 때 활성화 가능한 최대 기둥의 개수를 $f(d, x)$라고 하자. 이때 $c \in [f(d, x), n-(d+1)+f(d, x)]$ 인 구간에서 $ans(c)$의 가능한 후보로 $A_x f(d, x)$가 추가된 것이다. 스파스 테이블을 이용해 데이터를 저장해 놓고 나중에 세그먼트 트리를 쓰는 방식으로 $\mathcal{O}(N \log^2 N)$에 후반부 과정을 처리할 수 있다.

BOJ 23051. RMQ

두 2차원 배열 $P$와 $Q$를 생각하자. 정의는 다음과 같다.

 

먼저 첫 번째 관찰을 해 보자. $P$의 $i \le j$인 부분은 정확히 $N$개의 직사각형 구간으로 나눌 수 있다. 각 직사각형 내의 수들은 모두 같다. 방법은 간단한데, 카르테시안 트리를 잡고 루트부터 시작해 DFS를 돌며 어떤 노드 $x$에 대해 $i \le x$이고 $j \ge x$인 부분 중 아직 색칠되지 않은 부분을 $x$로 색칠한다고 생각하면 쉽다. 대충 아래 같은 형태이다.

 

 

자명하게도, $Q$도 같은 방식으로 $N$개의 직사각형 구간으로 나눌 수 있다. 이렇게 분할이 되니, 다음과 같은 생각이 가능하다: 스위핑을 하면서, 적당한 세그먼트 트리를 만들어, 온라인으로 업데이트와 구간 쿼리($\sum_{1 \le x \le i} \sum_{l \le y \le r} P_{x, y} \times Q_{x, y}$)를 빠르게 처리할 수 있다면, 문제를 빠르게 해결할 수 있을 것이다.

 

그런데 문제는 위 식에서도 보다시피 각 노드에 현재까지의 누적합을 정보로 담고 있는 세그먼트 트리를 만들어야 한다는 것이다. 그것도 두 배열에 있는 값의 곱을. 이게 어떻게 가능한가 싶겠지만, 일단 누적합을 구하는 것 자체는 그리 낯설지 않다. 잘 알려진 문제인지는 모르겠지만, Posters on the wall이 이러한 트릭을 사용하고, 핵심 아이디어는 누적 합을 시간에 대한 일차함수처럼 저장하는 것이다. (여기서 시간은 스위핑에서의 시간이라고 생각하면 좋다. 단순히 말하면 $i$좌표와 같다.) 그러면, 형태가 $P \times Q$와 같이 괴이한 꼴로 나와도, 마찬가지로 괴이한 형태의 노드 구조와 Lazy Propagation 메커니즘을 짜면 안될 건 없지 않을까?

 

이런 형태의 복잡한 Lazy Propagation 메커니즘을 짤 때는 한 번의 업데이트가 Lazy로 기록되는 과정과, 두 Lazy가 하나로 합쳐지는 과정을 모두 고려해야 한다. 먼저 이 문제에서 가능한 업데이트란 구간의 $P$나 $Q$값을 특정한 정해진 값으로 바꾸는 연산이고, 이때 시간에 따른 누적합 함수도 적당히 바꾸어 주어야 한다. Lazy Propagation에 대한 다음 성질을 상기해 보자:

• 어떤 부모의 Lazy $l_p$를 자식 노드의 Lazy $l_x$와 합칠 때, $l_x$의 업데이트는 시기상 모두 $l_p$보다 이른 것들이다.

위 사실을 이용해 세그먼트 트리의 노드 정보를 다음과 같이 구성할 수 있다.

• 두 정수 $A$와 $B$. 이는 시간 $t$에서의 노드의 누적합 $S_t = A + Bt$임을 나타낸다.
• 두 정수 $P_{sum}$, $Q_{sum}$. 이는 시간 $t$에서 노드 내 구간의 $P$값 합, $Q$값 합을 의미한다.
• Lazy Propagation을 위한 정보는 다음과 같다.
  • $upd$: 이 값은 Lazy에 있는 정보 중 가장 먼저 일어나는 업데이트의 시각을 나타낸다.
  • $P_{lazy}$, $Q_{lazy}$. 이 값은 업데이트 이후 구간의 $P$값과 $Q$값이 통일적인 어떤 수로 바뀌는지를 나타낸다.
  • 여섯 개의 정수 $A_{1}$, $A_{P}$, $A_{Q}$, $B_1$, $B_{P}$, $B_{Q}$. 이들은 각각 업데이트 후 $A$와 $B$의 값을 노드의 기존 $P$와 $Q$의 값에 대한 식으로 나타낸다. $A$는 $1$, $P_{sum}$, $Q_{sum}$과 계수들의 곱의 합으로 나타나고, $B$도 비슷하게 나타내어진다. 이때, 이 함수의 값은 최초의 변화 시점 $upd$ 이후의 누적합만 계산한 것임에 주의해야 한다.
    • 조금 커멘트를 하면, $A_1$과 $B_1$은 업데이트를 만드는 과정에서는 발생하지 않고, Lazy Propagation끼리의 업데이트를 합칠 때만 발생한다. $A_P$나 $A_Q$를 다른 Lazy Propagation 정보에 합칠 때, 해당 노드에 $P_{lazy}$나 $Q_{lazy}$가 존재할 경우 초기의 값이 아닌 새로운 값을 이용하기 위해 $A_1$과 $B_1$을 업데이트하게 되는 것인데, 이때 $A_1$에 더하는 부분에서 $(r-l+1)$을 더해 버리면 아래 노드로 전파될 때 문제가 생긴다. 따라서 일단 $A_1$에 반영할 때는 그대로 두고, $A$를 계산하는 파트(lazy 정보로 tree 정보를 알아내는 파트)에서 $(r-l+1)$을 곱해 줘야 한다.

이제 실제로 이 노드 구조를 어떻게 업데이트하는지에 대해 생각해 보자.

• 기본적으로 어떤 노드에서 시간 $t$의 누적합은, 해당 노드에 Lazy Propagation 업데이트가 쌓여 있지 않은 상태에서, $S_t = A + Bt$이다.
• 어떤 노드에 값을 바꾸는 업데이트가 들어왔다고 해 보자. 그러면 현재 이 노드의 $B$값에 해당하는 것은 행 하나에서의 가중치 합일 것이다. 이것을 $A$값에 반영하고, $B$값은 새로운 행 가중치로 업데이트해줘야 한다.
  • 예를 들어, $P$값이 $v$로 바뀌었다고 생각하자. 이때 기존 노드의 $Q_{sum}$을 이용하면 새로운 행별 가중치가 $v \times Q_{sum}$이 됨을 알 수 있다. 따라서 $B$는 $v \times Q_{sum}$으로 바뀌어야 할 것이다. 그리고 $A$는 $A + upd \times B - v \times upd \times Q_{sum}$으로 바뀌어야 할 것이다.
  • 실제로는 업데이트를 할 때 이런 값들을 참조하는 것이 아닌, 여섯 개의 정수 $A_{1}$, $A_{P}$, $A_{Q}$, $B_1$, $B_{P}$, $B_{Q}$를 참조하게 될 것이다. 이 값을 반영할 때, $B'=B_1 \times (r-l+1) + B_P \times P_{sum} + B_Q \times Q_{sum}$ 으로, $A' = A_1 \times (r-l+1) + A_P \times P_{sum} + A_Q \times Q_{sum}$ 으로 정의하자. 반영 뒤의 값은 $B$는 $B'$, $A$는 $A + B \times upd + A'$가될 것이다.
  • 자세한 Lazy Propagation 과정은 생략한다. 코드를 짜면서 엄청나게 힘든 과정을 겪었는데 그 과정을 다시 설명할 힘이 부족하다.

이걸 전부 짜면 $\mathcal{O}((N+Q) \log N)$에 문제를 풀 수 있다. 상수가 정말 크니 주의하자.