PS 일지 #2

BOJ 11744 Jump

정답 스트링 $S$를 찾기 위해서는, 일단 $Jump(Q) = n/2$인 상황을 어떻게든 만들어야 한다. $S$에서 $0$의 개수를 $a$라고 하고, $1$의 개수를 $b$라고 하면 $a+b=n$이기 때문에 $min(a, b) \le n/2 \le max(a, b)$가 성립한다. 즉, $Q=00...00, Q=10...00, Q=11...00, \cdots, Q=11...10, Q=11...11$을 모두 질문하면, $Jump(Q) = n/2$인 경우를 무조건 얻을 수 있다. 즉 $N+1$번의 질문으로 $Jump(Q_m) = n/2$를 만족하는 String $Q_m$을 찾을 수 있다. 이제 $Q_m$을 조금씩 만지면서 $Jump$값의 변화를 살피면 $S$를 알아낼 수 있을 것이다. 조금 생각해 보면, $i \neq j$를 만족하는 $i, j$에 대해  $Q_m$의 $i$번째 bit와 $j$번째 bit를 toggle한 string $Q_{ij}$를 질문하면, $S$의 $i$번째 bit와 $j$번째 bit가 같은지, 혹은 다른지를 알 수 있다. toggle 한 번에 $Jump$의 값이 $+1$ 혹은 $-1$만큼 변화하기 때문에, 만약 $Jump(Q_{ij}) = n/2$라면 $Q_m$의 $i, j$번째 bit 중 하나는 맞고 하나는 틀렸다는 것이고, $Jump(Q_{ij}) = 0$이라면 둘 다 맞았거나 둘 다 틀렸다는 의미이다. 두 경우 모두 어쨌든 두 비트의 가능한 $4$가지 조합 중 $2$가지 조합을 제거해 주고, 그것이 $00, 11$ 혹은 $01, 10$이 된다. 즉, 두 bit가 같은지, 다른지 알 수 있다. 이제 $Q_{12}, Q_{13}, \cdots, Q_{1n}$을 모두 질문하면 $S_1=0$인 경우의 $S$와 $S_1=1$인 경우의 $S$를 구할 수 있다. 두 가지 경우를 모두 질문해 보면, $S$를 얻을 수 있다.

 

...그런데 여기까지 생각하고 나니 도저히 쿼리 횟수를 획기적으로 줄일 수 있을 여지가 안 보였다. 설마 랜덤 스트링을 날리면 되나? 라는 생각이 들어서 $(1-\binom{1000}{500}/2^{1000})^{500}$을 울프람알파에 돌려 보니 $10^{-6}$ 스케일의 수가 나왔다.... 그러니까 그냥 랜덤 스트링 날리면 높은 확률로 $Q_m$이 잘 찾아진다. 괜히 $n/2$이 아닌데 생각보다 알아내는 데 오래 걸렸다 ㅠㅠ 수에 대한 직관이 있으면 이게 바로바로 보일텐데, 쉽지 않은 것 같다.

 

 

BOJ 20986 Group Photo

부분 점수를 받았던 문제인데, 기억이 안나서 코드를 보니 $O(N^2)$ 코드가 시간초과가 나 있었다. 좀 최적화를 했는데도 계속 시간 초과가 나서, 풀이를 다시 떠올리고 상수를 줄인 코드를 짰다.

 

$a_i < a_{i+1} + 2$라는 조건은 $a_i = a_{i+1} + 1$ or $a_i < a_{i+1}$로 풀어 쓸 수 있다. 즉 키가 증가하거나, 자신보다 키가 1 작은 사람이 와야 한다. 결국에는 $N$명의 사람이 적당한 $K$개의 그룹으로 쪼개지고, 각 그룹은 연속된 키를 가지고 있는 사람들로 구성되며, 큰 사람이 먼저 서 있는 형태를 띄게 된다.

 

이제 DP를 생각할 수 있다. $D[i] =$ (i번째 위치까지 설 사람들이 정해졌을 때, 최소 연산 횟수)라고 하면, Transition은 그룹을 하나 추가하는 걸 생각하면 된다. $[l, r]$ 구간을 추가할 때의 Cost는 $[l, r]$ 구간에서의 역인버전? 개수와 $[1, l-1]$과 $[l, r]$의 인버전 개수를 DP 비슷하게 $O(N^2)$에 미리 전처리해서 구할 수 있다. 즉, 전체 DP를 $O(N^2)$ 시간에 해결할 수 있다.

 

 

BOJ 21848 The short shank; Redemption

$t_i > T$인 죄수를 막을 수 있는 죄수라고 부르자. 반대로 막을 수 없는 죄수도 정의할 수 있다. 우리의 목표는 매트리스를 잘 설치해서, 막을 수 있는 죄수들을 최대한 많이 막는 것이다. 일단 죄수들이 탈출하는 걸 시간 축과 위치 축을 이용해서 평면상에 예쁘게 Plot할 수가 있다. 세로 축을 시간으로, 가로 축을 위치로 생각하자. 막을 수 없는 어떤 죄수 $u$의 탈출을 점으로 표현할 수 있고, 다른 죄수들을 탈출시키는 건 그 점에서 오른쪽 위 45도 방향으로 직선을 그리면 표현할 수 있다. 단, 지나가는 위치에 매트리스가 설치되어 있다면 그 직선은 그곳에서 멈춘다.

 

이제 막을 수 있는 어떤 죄수 $v$에 대해서, 집합 $S_v$를 다음과 같이 정의하자. (위치 $x$에 매트리스가 설치됨) $\rightarrow$ ($v$가 탈출할 수 없음)이 성립하면, $x \in S_v$이다. 잘 생각해 보면, 각각의 집합 $S_v$는 구간을 이룬다. 왼쪽 끝은 나한테 영향을 미치는 가장 오른쪽에 있는 직선의 시작 위치일 것이고, 오른쪽 끝은 현재 위치이다. 단, 나한테 영향을 미치는 직선이 없다면 $S_v = [1, N]$이다.

 

이 구간을 어떻게 구할까? 왼쪽 위치부터 스위핑하면서 '현재 위치에 영향을 미치는 직선 중에 가장 오른쪽에 있을 가능성'이 있는 직선들을 스택으로 관리할 수 있다. 말은 복잡하지만, 어떤 직선이 들어 오면 그냥 스택에 들어 있는 직선 중에서 이 직선보다 위쪽에 있는 직선들을 pop하고, 새로 들어온 직선을 push하면 된다. 새 직선보다 위쪽에 있다는 건 그 직선이 커버할 수 있는 범위가 새 직선보다 좁다는 것이고, 심지어 새 직선보다 왼쪽에 있으니 '어떤 위치에 영향을 미치는 직선 중에 가장 오른쪽에 있을 가능성'이 없어졌다는 뜻이다. 스택에서 빼 버려도 문제가 없다. 이제 가장 오른쪽에 있는 직선은 그냥 스택의 맨 위에 있는 직선을 가져오면 바로바로 구할 수 있다. 구현은 $i$번째 기둥의 높이가 $h_i = t_i - i$인 히스토그램을 생각하면 편할 것이다.

 

또한 윗 문단의 스위핑 알고리즘에서 구간에 대한 추가적인 관찰을 할 수 있는데, 바로 구간들이 트리 관계를 이룬다는 것이다. 임의의 $a < b < c < d$에 대해서, $[a, c]$와 $[b, d]$ 구간이 동시에 존재할 수 없다. 왜냐하면 $b$가 스택에 들어가야 하는데, 그러면 스위핑 과정에서 $c$를 볼 때 스택의 맨 위에 있는 원소가 $b$여야 하기 때문이다. 모순이므로 이런 경우는 존재할 수 없고, 두 구간은 서로소이거나 하나가 다른 하나에 포함되어야 한다. 즉, 트리 관계를 이룬다.

 

이제 구간을 모두 구했으니, 이 중에 $D$개의 위치를 골라서 그 위치를 포함하는 구간의 수를 최대화하는 문제로 바뀌었다. 트리로 문제를 바꿔 주면 트리에서 정점을 $D$개 색칠해서, 색칠된 정점을 자손으로 가지는 정점의 수를 최대화하는 문제가 된다. 2차원 DP를 생각하자. $D[u][k] = $($u$를 루트로 하는 서브트리에서 정점을 $k$개 색칠했을 때 답)이라고 하면, $O(N^2)$ 시간에 문제를 해결할 수 있다. DP 값을 합치는 부분을 보면 결국 위로 볼록한 두 함수에 대한 $(\max, +)$-convolution이다. Slope Trick 문제를 많이 풀어 봤다면 인접한 DP값의 차이를 Heap 같은 자료구조에 관리하면서 Small to Large로 합쳐 주는 테크닉을 써봤을 것이다. cost를 더하는 것은 가장 큰 원소에 1을 더해 주면 된다. 디테일은 아마 'boj 17517'를 구글링하면 자세히 설명한 글들이 나올 것이다. 이 테크닉을 사용해서 DP를 계산하면, $O(N log^2 N)$으로 시간복잡도를 줄일 수 있다. Heap 대신 벡터를 사용하고, 가장 큰 원소를 벡터의 맨 앞에 관리해주면 이를 $O(N log N)$으로도 줄일 수 있다.

 

 

BOJ 15941 TV 동물 농장

2차원 격자에 인접행렬처럼 문제를 표현하자. 인접한 두 칸을 골라서 적힌 글자가 같으면, 두 칸을 모두 flip하는 연산을 사용할 수 있을 때, 목표 격자로 바꾸는 최소 연산 횟수를 구하는 문제가 된다. 근데 이 연산의 성질을 좀 관찰해보려고 해도... 답이 없다. 이럴 때는 연산 자체를 바꿔볼 수 있을까라는 생각을 하면 도움이 되는 경우가 있는 것 같다. 모든 가능한 연산이 똑같은 변화를 가져야 하므로, 체스판에서 검은 칸만 flip해보자는 생각을 할 수 있다. 이러면 적힌 글자가 다를 때, 두 글자를 바꾸는 연산이 된다. 문제가 깔끔해졌다! 연산을 아무리 많이 해도 글자의 수는 변하지 않고 격자에서 동전을 원하는 위치로 옮기는 문제가 되었다.

 

일단 플로우 알고리즘으로 답의 하한을 구할 수 있다. 각각의 동전에서 목표 위치까지의 거리를 구해 두면 최소 코스트 매칭 문제가 된다. 헝가리안 알고리즘을 쓰든 MCMF를 쓰든 해서 최소 코스트를 구하면 이게 답의 하한이 된다. 그런데 사실 이게 답 그 자체일 수도 있지 않을까? 다음의 역추적 알고리즘으로 그것이 사실임을 알 수 있다.

 

매칭된 결과를 바탕으로 각각의 동전에 다음에 가야할 곳을 스택으로 저장하자. 문제는 다음에 가야할 곳에 다른 동전이 있는 경우이다. $clear(x, y)$라는 함수를 정의하자. $(x, y)$가 다음에 가야 하는 곳인데, 이미 다른 동전이 그 위치를 차지하고 있다면 $clear(x, y)$를 호출해서 그 동전을 치워버리자. $clear(x, y)$가 호출되면, 그 동전의 스택의 맨 위 원소를 뽑아서, 다음에 가야할 곳으로 가면 된다. 만약에 그곳에도 다른 동전이 있다면, $clear()$ 함수를 또 호출하면 된다. 이게 문제가 되는 경우는 사이클이 생기는 경우인데, 조금 생각해보면 그런 경우가 발생할 수 없다는 것을 알 수 있다. 사이클이 생겼다고 가정하고, 그 사이클에 속한 '움직임'들을 그냥 답에서 제거해 버려도 valid한 움직임 집합이 남는다. 그런데 이건 플로우 알고리즘보다 나은 답을 구했다는 거니까, 모순이다.

 

아직 문제가 되는 경우가 하나 더 남아 있다. $clear(x, y)$를 호출하려고 했는데 그 위치에 스택이 비어 있는 동전이 남아 있는 경우이다. 이럴 때는 현재 동전의 스택과 그 동전의 스택을 그냥 swap해버리면 된다. 그러고 나서 $clear(x, y)$를 호출하고, 현재 동전을 그 위치로 옮기면 된다. 또한 윗 문단의 사이클이 생기지 않는다는 논리는 여전히 유효하다.

 

위 알고리즘은 플로우 알고리즘으로 구한 답과 정확히 같은 수의 연산을 사용한다. 역추적하는 방법도 알아내었으니 이제 이걸 구현하면 AC를 받을 수 있다. 구현할 때 주의할 점은 중간에 스택을 swap하기 때문에 이미 스택이 비었다고 확인한 동전도 다시 스택이 찰 수 있어서 모든 동전의 스택이 비었는지 확실히 체크해주어야 한다는 것 정도가 있을 것 같다.