Google Kickstart 2019 Round D – ‘X or What’ 풀이 (코드포함)

이 포스팅에서는 Google Kickstart 2019 Round D ‘X or What’의 풀이와 코드를 제공합니다.
본 풀이는 공식적인 풀이와 완벽히 일치하지 않을 수 있으며, 온라인 Submission을 통과하였습니다.
공식 풀이 및 자세한 사항은 공식 페이지를 참조하시기 바랍니다.

---

Prob A ‘X or What’

문제 정보

문제 링크 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051061/0000000000161426
카테고리 : Bit manipulation, Heap
난이도 : 중간

문제 설명

테스트 케이스의 수 T가 주어진다.
그 다음 줄에는 배열의 길이 N과 쿼리의 수 Q가 주어진다.
그 다음 줄에는 배열의 원소인 정수 A_0, A_1, … , A_N-1이 입력된다.
그 다음 Q개의 줄에는 배열 인덱스와 새로운 값을 가리키는 P_i, V_i가 입력된다.
이 쿼리의 연산은 A[P_i]의 값을 V_i로 바꾸는 연산이다.
각 쿼리를 수행한 후, 배열 A의 SubArray 중 모든 원소를 Xor해서 2진수로 표현할 때 1이 짝수 개인 SubArray 중 가장 긴 것의 길이를 출력하여라.

예를 들어, 원래 배열이 3 3 3 3 3 3 3 3 3 3 이라고 하자.
여기서 쿼리 1 4 를 수행하면 3 4 3 3 3 3 3 3 3 3 의 배열을 얻는다.
여기서 가능한 가장 긴 SubArray는 인덱스 (2, 9)의 구간인 3 3 3 3 3 3 3 3 이다.
따라서 길이 8이 출력된다.
여기서 쿼리 2 4를 수행하면 3 4 4 3 3 3 3 3 3 3 을 얻는다.
여기서 가장 가능한 긴 SubArray는 인덱스 (0, 9)의 구간인 3 4 4 3 3 3 3 3 3 3 이다.
따라서 길이 10을 출력한다.

문제 풀이

2진수로 표현했을 때, 비트 수가 홀수 인 것을 odd, 짝수인 것을 even이라고 하자.
문제 해결의 핵심 아이디어는 odd와 odd를 xor하면 even이 된다는 점이다.
예를 들어 7(111)과 4(100)를 xor하면 3(11)이 된다. 증명은 간단하다.
두 수가 공유하는 1의 비트는 xor로 사라진다. 서로 공유하지 않는 1의 비트는 xor 결과에서 별개로 존재하므로 그 수를 각각 더해야한다.
공유하는 1의 비트가 짝수라면 서로 공유하지 않는 1의 비트는 각각 홀수개라 더하면 짝수가된다.
공유하는 1의 비트가 홀수개라도 남은 비트가 각각 짝수이므로 역시 더하면 짝수가된다.

즉, 결론은 다음과 같다.
쿼리를 수행한 이후에 배열의 odd가 짝수개 있으면 배열의 길이 자체가 답이된다.
만약 odd가 홀수 개 있다면, 배열의 가장 왼쪽이나 오른쪽의 원소까지를 제외한 나머지 길이 중 큰 것이 답이된다.

코드

import Queue

def countBit(N):
    ret = 0
    while N > 0:
        ret += (N % 2)
        N //= 2
    return ret % 2

def findMaxLength(Min_Q, Max_Q, Nums, N):
    left, right = None, None
    while not Min_Q.empty():
        idx, val = Min_Q.get()
        if Nums[idx] == val:
            left = [idx, val]
            Min_Q.put([idx, val])
            break
    
    while not Max_Q.empty():
        idx, val = Max_Q.get()
        if Nums[-idx] == val:
            right = [-idx, val]
            Max_Q.put([idx, val])
            break
    
    if N - left[0] - 1 > right[0]:
        return N - left[0] - 1
    else:
        return right[0]
        
        
T = int(input())
for case in range(1, T + 1):
    # Get Input
    N, Q = [int(x) for x in raw_input().split(' ')]
    Nums = [int(x) for x in raw_input().split(' ')]
    
    # Init Priority Queue
    Min_Q = Queue.PriorityQueue()
    Max_Q = Queue.PriorityQueue()
    oddCnt = 0
    
    # Calc initial state of array
    for i in range(N):
        if countBit(Nums[i]) == 1:
            oddCnt += 1
            Min_Q.put([i, Nums[i]])
            Max_Q.put([-i, Nums[i]])

    result = []
    # For each query, handle element according oddness of bits.
    for i in range(Q):
        idx, newVal = [int(x) for x in raw_input().split(' ')]
        if countBit(newVal) == 1:
            Min_Q.put([idx, newVal])
            Max_Q.put([-idx, newVal])
            if countBit(Nums[idx]) == 0:
                oddCnt += 1
        elif countBit(newVal) == 0:
            if countBit(Nums[idx]) == 1:
                oddCnt -= 1
        Nums[idx] = newVal
        
        # If number of oddbits is odd, calc max length.
        if oddCnt % 2 == 0:
            result.append(str(N))
        else:
            result.append(str(findMaxLength(Min_Q, Max_Q, Nums, N)))
    
    print "Case #" + str(case) + ": " + " ".join(result)

---

Competition Kickstart ‘X or What’