[Python] 28346번 XOR Necklace

 

 

 

https://www.acmicpc.net/problem/28346

28346번: XOR Necklace

---

 

23/11/28

 

 

비트 연산의 성질을 이용한 애드혹 문제이다. 다른 방법으로는 제한 시간이 널널하기 때문에 3차원 DP로도 풀 수 있다는데, 그 방법은 해보지 않았다.

---

 

문제 접근 방식:

 

 

처음에 이 문제를 보고 XOR의 변형된 식을 생각해보았다.

 

XOR과 AND 연산자에 대하여, 다음과 같은 식이 성립함은 유명한 사실이다.(여기서 이에 대한 증명은 따로 다루지 않겠다.)

 

$$a \oplus b = a + b -2(a \wedge b)$$

$$a \wedge b = a + b - (a \vee b)$$

 

이를 이용하면, 기존 배열의 XOR 합에 대한 식을 다음과 같이 나타낼 수 있음을 확인할 수 있다.

$$\textrm{Sum original}$$

$$=\sum_{i=1}^n (A_i \oplus A_{i+1})$$

$$= A_1 + A_2 + \cdots + A_{i-2} + A_{i-1} + A_{i-1} + A_{i} + \cdots + A_n + A_1$$

$$-2((A_1 \wedge A_2) + \cdots + (A_{i-2} \wedge A_{i-1}) + (A_{i-1} \wedge A_{i}) + \cdots + (A_n \wedge A_1))$$

 

마찬가지로, 우리는 배열의 $i$번째 원소를 없앴을 때의 합 또한 구할 수 있다.

 

$$\textrm{Sum when }i\textrm{th element removed}$$

$$= A_1 + A_2 + \cdots + A_{i-2} + A_{i-1} + A_{i-1} + A_{i+1} + \cdots + A_n + A_1$$

$$-2((A_1 \wedge A_2) + \cdots + (A_{i-2} \wedge A_{i-1}) + (A_{i-1} \wedge A_{i+1}) + \cdots + (A_n \wedge A_1))$$

 

처음에 생각한 방식은 기존 배열의 합과 배열의 $i$번째 원소를 없앴을 때의 합을 비교해서 $i$번째 원소를 없앴을 때가 더 크다면, 그리디적으로 그 원소를 없애서 합을 늘리면 될 것이라고 생각했다.

 

즉, $\textrm{Sum original} - \textrm{Sum when }i\textrm{th element removed}$의 값을 구해서 이 값이 음수라면 $i$번째 원소를 없앴을 때의 합이 더 큰 것이므로, 기존 배열의 합에서 저 값의 절댓값만큼을 더해주면 된다고 생각했다.

 

식 정리를 하면, 이 값은 다음과 같이 나온다.

 

$$\textrm{Sum original} - \textrm{Sum when }i\textrm{th element removed}$$

$$=2A_i - 2((A_{i-1} \wedge A_i) + (A_i \wedge A_{i+1}) - (A_{i-1} \wedge A_{i+1}))$$

 

이를 토대로 구현을 했고, 맞았습니다를 받을 수 있었다.

 

사실 우리는 저 차이가 항상 $0$이거나 양수임을 증명할 수 있다.

 

즉, 배열의 특정 원소를 빼는 행위는 항상 손해라는 사실을 증명할 수 있다. 따라서 답은 그냥 $\textrm{Original sum}$이 된다.

 

저 차이가 음수인지 양수인지만 따져주면 되므로, 공통으로 들어있는 $2$를 제외하고 생각해보자.

 

즉, $A_i - (A_{i-1} \wedge A_i) - (A_i \wedge A_{i+1}) + (A_{i-1} \wedge A_{i+1})$의 값을 생각해보자.

 

편의상 $A_{i-1}, A_i, A_{i+1}$를 $a, b, c$라고 하자.

 

$b + (a\wedge c) - (a\wedge b) - (b\wedge c)$를 생각하자.

 

위의 AND연산의 식을 이용하여 OR이 들어간 식으로 고치면 다음과 같다.

 

$$(a\vee b) + (b \vee c) - b - (a \vee c)$$

 

각 비트별로 생각해보자. 즉, 하나의 숫자를 하나의 집합으로 간주하는데, 이 숫자의 $2^0$자리가 $1$이라면 $0$이라는 원소를 가지고 있고, $2^1$자리가 $1$이라면 $1$이라는 원소를 가지고 있고, 마찬가지로, $2^i$자리가 $1$이라면 $i$라는 원소를 가지고 있다고 생각해보자.

 

또한, 여기서 사용하는 집합은 중복을 허용하는 집합이라고 해보자.(그러면 더하기 연산이 쉽게 정의된다.)

 

이때, $p\vee q$는 집합 $p$에 들어있는 원소와 집합 $q$에 들어있는 원소를 중복을 포함하지 않고 모아 놓는 연산, 즉, 중복을 생각하지 않는 집합의 교집합 연산이라고 생각할 수 있다.

 

또한, $p + q$는 집합 $p$에 들어있는 원소와 집합 $q$에 들어있는 원소를 모두 합하는, 즉, 중복을 포함하는 집합의 합집합 연산이라고 생각할 수 있다.

 

그러면 $(a \vee b) - b$를 생각해보면, 집합 $a$와 집합 $b$를 중복을 포함하지 않고 모아놓은 후에, 집합 $b$에 해당하는 부분만 제외하는 연산이라고 생각할 수 있다.

 

즉, 중복을 생각하지 않는다면 $a - b$에 해당한다고 생각할 수 있다.

 

또한, 거기에 $b \vee c$는 집합 $b$에 해당하는 원소과 집합 $c$에 해당하는 원소 모두를 중복을 포함하지 않고 모아놓은 것이므로, $(a \vee v) - b + (b \vee c)$는 집합 $b$와 $c$에 해당하는 모든 원소를 중복을 포함하지 않고 모은 후에, 집합 $a$에 해당하는 원소를 중복을 포함하여 다 모아놓은 상황이라고 할 수 있다.

 

이후 $a \vee c$를 뺀다는 뜻은, 집합 $a$와 집합 $c$에 해당하는 모든 원소를 중복을 포함하지 않고 모은 집합을 기존 집합에 뺀다는 뜻이다.

 

집합 $a$와 집합 $c$에 해당하는 원소는 $(a \vee v) - b + (b \vee c)$에 항상 존재하므로 우리는 위의 집합연산이 잘 정의됨을 확인할 수 있다.

 

즉, 비트로 생각하자면 음수가 나오지 않고 적어도 $0$보다 크거나 같음을 확인할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 28346번 XOR Necklace
# 수학? 그리디
'''
접근 방법:
a xor b = a+b - 2(a and b)임을 이용해보자.
a and b = a+b - (a or b) 
기존 합
a1 + a2 + a2 + a3 + ... + ai-2 + ai-1 + ai-1 + ai + ai + ai+1 + ... + an + a1
-2(a1 and a2 + a2 and a3 + ... + ai-2 and ai-1 + ai-1 and ai + ai and ai+1 + ... + an and a1)
i번째를 없앤 후의 합
a1 + a2 + a2 + a3 + ... + ai-2 + ai-1 + ai-1 +           ai+1 + ... + an + a1
-2(a1 and a2 + a2 and a3 + ... + ai-2 and ai-1 + ai-1 and ai+1 + ...             + an and a1)
기존합 - i번째를 없앤 후의 합
2ai - 2(ai-1 and ai + ai and ai+1 - ai-1 and ai+1)
= 2(ai - ai-1 - ai + (ai-1 or ai) - ai - ai+1 + (ai or ai+1) + ai-1 + ai+1 - (ai-1 or ai+1))
= 2((ai-1 or ai) + (ai or ai+1) - ai - (ai-1 or ai+1))
-> a or b + b or c - b - a or c
이게 양수면 기존합이 큰거임 이건 항상 양수임 없애는게 손
이게 음수면 i번째를 없앤 후의 합이 큰거임
'''
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().rstrip().split()))
    original = 2*sum(A)
    for i in range(N):
        original += -2*(A[i] & A[(i+1)%N])
    for i in range(N):
        K = A[i] - A[(i-1)%N]&A[i] - A[i]&A[(i+1)%N] + A[(i-1)%N]&A[(i+1)%N]
        if K < 0:
            original -= K
    print(original)