Problem Solving Diary #21

BOJ 15986. &+ +&

먼저 모든 $A[i] \wedge B[j]$의 합을 구해 보자. $Acnt[x]$를 $A$의 원소들 중 $2^x$의 비트가 $1$인 것의 개수라고 하고, 마찬가지로 $Bcnt[x]$를 정의하자. 비트별로 따로따로 생각하면 답이 $\sum Acnt[i] Bcnt[i] 2^i$임을 쉽게 알 수 있다.

 

다음으로 모든 $A[i] + B[j]$의 AND 값을 구해 보자. 이것도 역시 비트별로 생각할 것이다. 즉, 모든 $A[i] + B[j]$ 값에 $2^i$의 비트가 켜져 있는지를 검사할 것이다. 먼저 $i=0$일 때부터 시작해 보자. $2^0$의 비트가 켜져 있으려면 $A$는 모두 홀수, $B$는 모두 짝수거나 그 반대여야 한다.

 

$i$가 더 커지는 경우에는 어떻게 검사할 수 있을까? 어떤 수 $v$에서 $2^i$번째 비트가 켜져 있다는 것은 $v$를 $2^{i+1}$로 나눈 나머지가 $2^i$ 이상이라는 것이다. 편의상, $A$와 $B$ 두 배열을 모두 $2^{i+1}$로 나눈 나머지 상태로 생각하자. 다음 사실이 자명하게 성립해야 한다.

• $2^i$의 비트가 켜져 있으려면, $A$의 모든 수를 적당한 구간 $[a, a+k]$ ($k \le 2^i$) 안에 넣는 $a$와 $k$가 필요하다. (단, $a+k \ge 2^{i+1}$일 경우 mod를 취해 생각한다.) $B$도 마찬가지이다.

위와 같은 구간이 존재하지 않는다면, $B$의 수를 아무거나 하나 잡았을 때, 해당 수와 $A$의 어떤 수를 더해 $2^{i+1}$로 나눈 나머지가 $2^i$ 이상이어야 하므로 이 조건을 만족할 수 없음을 알 수 있다.

 

다음과 같은 방식으로 문제를 해결할 것이다.

• $A$의 원소들 중 $2^i$ 미만인 것들을 집합 $A_1$로 놓고, $A_1$의 최댓값과 최솟값을 각각 $A_{1, min}$, $A_{1, max}$라 하자. 또한 $2^i$ 이상인 것들을 집합 $A_2$로 놓고, 그 최댓값과 최솟값을 각각 $A_{2, min}$, $A_{2, max}$라고 하자. $B$에 대해서도 비슷하게 정의를 하자.
• $A$의 위 네 개 값과 $B$의 위 네 개 값에 대해서만 테스트해 보아도 충분하다. 이 16개의 조합 중 나머지가 $2^i$ 미만인 것이 없다면, $i$번째 비트는 최종 답에서도 켜져 있다.

이렇게 하면 문제를 $O(30N + 30 \times 16)$ 에 문제를 해결할 수 있다.

 

위 알고리즘이 동작하는 이유는 대충 이렇다. 일단 위 알고리즘을 통해 $2^i$ 미만의 나머지를 찾았다면, 당연히 답은 불가능이다. 역으로, 위 16개의 값만 보면 충분한 이유를 설명해 보자. 만약 위 16개의 값이 모두 $2^i$ 이상인데, $2^i$ 이하인 $A_i + B_j$가 존재한다고 해 보자. 그렇다면 해당 $A_i$와 $B_j$는 각각 $A_1$ 또는 $A_2$, $B_1$ 또는 $B_2$의 집합에 속하게 된다. 일반성을 잃지 않고 $A_1$과 $B_1$ 집합에 속한다고 가정하자. 아래 사실들을 차례로 증명할 수 있다.

• $A_{1, min} + B_{1, min} \ge 2^i$, $A_{1, min} + B_{1, max} \ge 2^i$이므로, $B_{1, min} \le x \le B_{1, max}$인 모든 $x$에 대해 $A_{1, min} + x \ge 2^i$이다.
  • 증명의 방식은 $B_{1, max} - B_{1, min} < 2^i$라는 점을 이용하면 된다.
• 위 결과에 $x=B_j$를 대입하면 $A_{1, min} + B_j \ge 2^i$이다. 위와 같은 방식으로 잃지 않고 $A_{1, max} + B_j \ge 2^i$임을 증명할 수 있다.
• 이제 위의 증명 방식을 다시 이용해 $A_{1, min} \le x \le A_{1, max}$인 모든 $x$에 대해 $x + B_j \ge 2^i$임을 보일 수 있고, 따라서 $A_i + B_j \ge 2^i$이다.

결과적으로 위의 풀이의 정당성을 증명할 수 있다.

BOJ 25563. AND, OR, XOR

일단 배열 $cnt[x]$를 만들자. $cnt[x]$는 $arr[i] = x$인 $i$의 수이다.

 

이 배열의 값을 바탕으로 가장 쉽게 찾을 수 있는 것은 XOR의 개수이다. $i \oplus j = k$인 $j$의 값은 $i$와 $k$가 정해지면 하나로 고정되기 때문이다.

 

AND와 OR의 경우는 조금 더 복잡하다. OR는 AND와 대칭적이므로 AND만 보자. 어떤 $i$에 대해 $i \wedge j = k$일 $j$의 조건을 찾아보자. 먼저 $i$가 $k$의 모든 비트를 포함하는 경우, 즉 $i \wedge k = k$인 $i$들만 남겨도 상관이 없다. 이제 새로운 배열 $cnt_{and}[x]$를 따로 만드는데, 이것은 $x \wedge k = k$인 $x$들만 고려하는 배열로 생각하자. 편의를 위해, 이러한 $x$에서 $k$의 값을 뺀 채로 생각하기로 하자. 즉, 원본 배열 $arr$에 대해, $arr_i \wedge k = k$인 경우에만 $cnt_{and}[arr_i - k]$에 1을 더한다고 생각하면 좋다.

 

이제 우리는 $\sum_i \sum_{j , (i \wedge j = 0)} cnt_{and}[i] cnt_{and}[j]$를 구하면 된다. (만약 $i \wedge j$가 $0$이 아니었다면, 원본의 $i + k$와 $j+k$ 값의 AND 값도 $k$가 아니었을 것이다.) 이것을 구하는 방법은 SOS DP를 이용하면 된다.

 

마찬가지로 OR를 구하는 경우, $i \vee k = k$인 $i$에 한해 $cnt_{or}[i] = cnt[i]$를 그대로 정의하고, $\sum_i \sum_{j , (i \vee j = k) cnt_{or}[i] cnt_or[j]}$를 계산하면 된다. 그런데 여기서 $j$의 조건은 $j$의 비트가 $k-i$의 비트를 포함하면 된다. 이것 역시 SOS DP로 처리 가능하다.

 

결과적으로 문제를 $O(N + 20 \times 2^{20})$에 해결할 수 있다. 아무래도 $i < j$ 조건이 있기 때문에 위에서 구한 답에 적당한 처리를 더 해 줘야 할 것이다. $i = j$인 경우를 제거하고 $2$로 나누면 충분하다. 또 $k=0$인 경우 XOR의 개수를 따로 처리해 줘야 한다.

BOJ 19651. 수열과 쿼리 39

이 문제에서 처리하는 쿼리는 다음과 같다.

• $l \le i \le r$인 $A[i]$에 $xi+y$ 더하기
• $s \le l < r \le e$인 $(l, r)$ 중 $l \le i \le r-2$인 모든 $i$에 대해 $A_{i+1} - A_{i} = A_{i+2} - A_{i+1}$인 $(l, r)$들에 대해 $r-l+1$ 최댓값 구하기

이 형태로는 쿼리를 처리하는 것이 쉽지 않다. 문제의 상황에 대한 관찰을 하게 되면 $B_i = A_{i+1} - A_{i}$로 정의하는 것이 좋다는 것을 알 수 있다. 이렇게 문제를 나타냈을 때 업데이트와 쿼리가 모두 단순화되기 때문이다. 이제 $B$를 이용해 문제를 다시 써 보면,

• $l \le i \le r$인 $A[i]$에 $x$ 더하기 (맨 앞과 맨 뒤 원소의 값은 따로 바꿔 줘야 하는데, 이것도 이 업데이트로 가능하다.)
• $s \le l \le r \le e$인 $(l, r)$ 중 $B_l = B_{l+1} = \cdots = B_r$인 $(l, r)$에 대해 $r-l+2$의 최댓값 구하기

하지만 이것도 여전히 어렵다. $C_i = B_{i+1} - B_i$로 치환학고 다시 써 보면 문제를 다음과 같이 변형할 수 있다.

• $C_i$의 값을 바꾸기
• $s \le l \le r \le e$인 $(l, r)$ 중 $C_l = \cdots = C_r = 0$인 $(l, r)$에 대해 $r-l+3$의 최댓값 구하기

이 쿼리는 std::set 등을 이용해 쉽게 처리할 수 있고, 문제를 $O(Q \log N)$에 해결할 수 있다. 실제로 $C_i$의 정의는 $A_{i+2} - 2A_{i+1} + A_i$가 되고, $C_l = \cdots = C_r = 0$인 구간이 없는 경우 $2$가 답이 됨에 주의해야 한다.

BOJ 31726. Fish 3

일단 문제를 $O(NQ)$에 해결하는 알고리즘을 생각해 보자. 우리가 할 수 있는 행동은 다음 둘 중 하나다.

• $A_i$를 $D$ 증가시키거나,
• $A_i, A_{i+1}, \cdots, A_N$을 $1$씩 증가시킨다.

목표는 첫 번째 연산을 최소 횟수로 사용하여 (두 번째 연산의 횟수는 상관없다.) $A_i = C_i$로 만드는 것이다. 불가능한 경우 불가능함을 판별해야 한다. 우리는 두 번째 연산을 사용해서 $A$를 단조증가수열로 만들 수 있다. 따라서, 우리가 구해야 하는 것은 기존 수열에서 특정 수를 골라 $D$만큼 빼는 작업을 반복해 (이 과정에서 수가 음수가 되면 안 된다) 단조 증가 수열을 만들 수 있는 작업의 최소 횟수를 구하는 것이다. 그리고 이것은 수를 뒤부터 보면서 그리디하게 해 주면 쉽게 해결할 수 있다.

 

이제 이것을 쿼리 형태로 해결하는 부분이 어려운 부분이다. 나이브 풀이가 뒤에서부터 보는 그리디라는 점에서 착안해, 이런 시도를 생각해볼 수 있다: 쿼리의 끝점을 오른쪽으로 한 칸씩 늘려간다. 현재 끝점이 $x$일 떄, $x$에서부터 왼쪽으로 이 그리디를 시행해 $y \le x$인 모든 칸 $y$에 대해 이 수열을 단조증가로 만들기 위해 $A_y$에서 $D$를 빼야 하는 최소 횟수를 자료구조로 관리한다. 이 횟수를 $C_y$라 하자. $x$가 증가함에 따라 $C_y$가 함께 증가할 수 있는데, 이것을 관리하자. 어떤 쿼리 $[l, r]$에 대한 답은 $x=r$일 때 $\sum _{l \le i \le r} C_i$를 구해 해결할 수 있다.

 

실제로 이 $C_i$를 관리하기 위해서는 $A_i - D \times C_i$라는 값을 대신 관리하는 것이 더 쉽다. 이 값을 $V_i$라고 하자. $V_i$는 어떤 경우에도 항상 단조감소하는 값이 되어야 한다. $x = i$인 시점에서 $[l, i]$ 에 대한 쿼리가 불가능이 답이 아닌 최소의 $l$이 존재할 것이다. 이때, 이 $l$보다 작은 왼쪽 끝점을 가지는 쿼리는 항상 답이 불가능일 것이므로 무시해도 된다. 각 $i$에 대해 이러한 $l$을 $lim_i$라고 하자.

 

$x = i$인 시점에서 $V_{lim_i} \le V_{lim_i + 1} \le \cdots \le V_{i-1} \le V_i$가 성립할 것이다. 여기서 $x$를 $i+1$로 늘려 보자. 만약 $V_i \le A_{i+1}$이라면 그대로 $V_{i+1}$은 $A_{i+1}$이 되고 아무런 변화도 일어나지 않는다. 그러나 만약 $V_i > A_{i+1}$이라면 $A_{i+1}$의 값을 고려해 어떤 $V_i$들에서 적당히 $D$의 배수만큼을 빼 줘야 할 것이다. 정확히 어떤 $i$의 값들에서 $D$의 몇 배만큼 빼줘야 하는가?

 

이것을 구하는 방법은 간단하다. 그 방법을 이해하기 위해서는 다음 관찰을 해야 한다.

• 어떤 구간 $V_l \le \cdots \le V_r$에서 $V_{i+1} - V_i < D$가 항상 성립한다면, 이후에 ($V_l$이 음수가 되기 전까지) 모든 연산에서 $V_l, \cdots, V_r$에서 같은 양만큼을 빼게 된다.

조금만 생각해 보면 위 사실이 왜 성립하는지에 대한 직관을 얻을 수 있다. 위 사실이 참이라고 가정하면, 다음과 같은 알고리즘으로 문제를 풀 수 있다.

• 먼저 위 성질을 만족하는 $V_l, \cdots, V_r$에 대해 $[l, r]$ 구간을 set들로 관리한다.
• 아직 음수가 되지 않은 $V_i$에 대해 $i$의 최솟값 $S$를 관리한다. 위에서 정의한 set의 구간들은 다음 성질을 만족해야 한다: $[S, x]$ 범위의 모든 수가 정확히 하나의 구간에 들어가 있어야 한다.
• 새로운 수 $A_{x}$가 추가되었을 때, $V_x$ 이전의 $V$ 값들을 $V$ 이하로 만들어주기 위해 $D$를 빼야 하는 횟수를 구한다. 이 과정에서 set의 구간들이 적당히 합쳐질 수 있다. 이 부분은 레이지 세그트리로 구현할 수 있다.
• 위 과정에서 $V_i$가 음수가 된 값이 추가될 수 있다. 이 값은 항상 prefix 부분을 이루므로, $S$를 1씩 늘려가면서 $V_S$가 음수가 되었는지를 판별하면 된다.
• 마지막으로, $x$를 끝점으로 하는 모든 쿼리의 답을 구한다.

시간 복잡도는 $O(Q \log N)$이다.