Codeforces Round #803 (Div. 2) ABCD

[11번째 Contest]

오늘 껀 너무 쉬웠다. 다만, C에서 5 WA 맞고 개같이 멸망할 뻔하고, D도 잘못 해석해서 20분 버리고. 그래도 4솔에 블루 퍼포니까 만족.

A. XOR Mixup

길이가 $n-1$인 배열 $a$가 있다. $a$의 모든 원소를 $xor$ 연산한 결과를 $x$라고 하자. $a$에 $x$를 추가하고 무작위로 $a$를 섞었다. $x$를 구해라.

풀이

브루트포스 $O(N^2)$

$n\leq100$이므로 $O(N^2)$으로 풀면 된다. $a_i$가 $a_i$를 제외한 모든 원소에 대해 $xor$ 연산을 한 결과와 동일하면 바로 출력하면 된다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    for i in range(n):
        x = 0
        for j in range(n):
            if i==j:
                continue
            x ^= a[j]
        if x==a[i]:
            print(a[i])
            return
    
    
for __ in range(int(input())):
    solve()

풀이

그리디를 이용한 O(N)

$a$의 모든 원소를 $xor$하면 $0$이다. 이 말은 $a$의 어떤 원소 $a_i$를 제외하고 $xor$한 결과는 $a_i$라는 뜻이다. 모든 원소가 정답이 될 수 있다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    print(a[0])
    
    
for __ in range(int(input())):
    solve()

B. Rising Sand

길이가 $n(1\leq n \leq2*10^5)$인 배열 $a$가 주어진다. 정수 $k(1\leq k \leq n)$도 주어진다. $a_i > a_{i+1} + a_{i-1}$를 만족하는 $i$에 대해 $tall$ 하다고 말할 수 있다. 아래 작업을 무수히 반복해서 만들 수 있는 최대 $tall$ 갯수를 구해라.

• 연속된 $k$개의 배열 요소에 대해 모두 $+1$를 한다.

풀이

$k=1$이라면, 작업을 무수히 해서 $(n-1)/2$ 개의 $tall$을 만들 수 있다. $a_1, a_3, a_5, ..., a_{(n-1)/2}$ 을 $tall$하게 만들 수 있다.

$k\geq2$라면, 작업을 하면 손해다. 작업을 통해서 $tall$하지 않은 $a_i$는 $tall$해질 수 없다. $a_i$를 증가시키려면 $a_{i+1}$ 또는 $a_{i-1}$도 같이 증가하기 때문이다.

코드

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    if k==1:
        print((n-1)//2)
    
    ans = 0
    for i in range(1, n-1):
        if a[i] > a[i-1]+a[i+1]:
            ans += 1
            
    print(ans)

    
for __ in range(int(input())):
    solve()

C. 3SUM Closure

길이가 $n$인 배열 $a$가 입력된다. 서로 다른 $i, j, k$를 선택했을 때, $a[i]+a[j]+a[k]$가 배열 $a$ 안에 있는지 확인한다. 모든 $i, j, k$에 대해서 단 하나라도 없으면 "NO", 모두 있으면 "YES"를 출력하라. $a[i]+a[j]+a[k]$를 $3sum$이라고 하겠다.

풀이

구성적 풀이

$n$의 길이에 따라 나눠진다.

$n \leq 4$라면, 모든 경우를 계산해보면 된다.

$n \geq 5$라면, 특정 경우에만 "YES"가 출력된다. 예시를 들어 설명해보겠다.

$a=[0, 0, 1, 2, 3]$ 라면, 성립하지 않는다. 같은 부호를 갖는 수가 $2$개 이상 있으면 항상 $max(a)$보다 큰 $3sum$이 존재하기 때문이다. 부호가 반대일 때도 성립한다.

$a=[0, 0, 0, 0, 0, 4]$ 라면, 성립한다. 같은 부호를 갖는 수가 $1$개 밖에 없고 나머지는 $0$이다. $3sum$은 $0$ 또는 $4$이다.

$a=[-3, 0, 0, 0, 3]$ 라면, 성립한다. 부호가 서로 다른 수가 단 2개 존재하기 절댓값이 같기 때문이다. $3sum$은 $0$ 또는 $-3$ 또는 $3$이다.

이와 같은 예시를 만들어서 예외케이스 처리하면 된다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    if n<=4:
        for x in C(a, 3):
            if sum(x) not in a:
                return 0
        return 1
    else:
        b = [x for x in a if x]
        if len(b)>2:
            return 0
        if len(b)<=1:
            return 1
        if b[0]+b[-1]==0:
            return 1
        return 0

    
for __ in range(int(input())):
    print('YES' if solve() else 'NO')

브루트포스 풀이

풀이

에디토리엄 해설이 더 깔끔해서 정리해봤다.

같은 부호를 갖는 수가 $3$개 이상이라면, 항상 "NO"를 출력한다. 같은 부호를 같은 수들의 $3sum$ 중 $max(a)$보다 큰 수가 항상 존재하기 때문이다.

이외의 경우에 브루트포스를 돌리면 된다. 여기서 주의해야 하는 건, 브루트포스 돌리는 $a$의 길이를 $3$ 이상으로 최소가 되게 해야 한다.

코드

from itertools import combinations as C
 
 
def solve():
    n = int(input())
    a, b, c = [], [], []
    for x in map(int, input().split()):
        if x>0:
            a.append(x)
        if x<0:
            b.append(x)
        if x==0 and len(c)<2:
            c.append(x)
            
    if len(a)>2 or len(b)>2:
        return 0
    
    c += a+b
    for x in C(c, 3):
        if sum(x) not in c:
            return 0
    return 1

    
for __ in range(int(input())):
    print('YES' if solve() else 'NO')

D. Fixed Point Guessing

길이가 $n$($n$은 홀수)인 배열 $a=[1, 2, ... , n]$가 있다. $2$개씩 $(n-1)/2$개의 원소 쌍을 고르고 한 쌍의 원소를 $swap$해주었다. $a$의 단 하나의 원소만 원래 자리를 유지하고 있는 상황이다. 다음 쿼리를 사용해서 그 원소를 구하라.

• $l, r$ 쿼리를 날리면, $[a_l, ... , a_r]$이 정렬된 상태로 주어진다.

풀이

눈치채야 할 게 있다. $n \leq 10^4$이고 사용할 수 있는 쿼리 수는 $15$다. 얼추 $log\;n=query$ 이니까 $binary\;search$를 하면 되는 게 보인다.

$left=1, right=n$으로 초기화하고 $mid=(left+right)/2$로 초기화한다. $left$와 $mid$를 퀴리로 날리면 반환값에 의해 값이 어디있는지 알 수 있다. $a[left:mid]$ 값을 $a_i$라고 하자. $a_i$가 구간 안에 있는 수인지 세야 한다. 즉, $left \leq a_i \leq mid$인 갯수를 구해야 한다.

갯수가 홀수라면, 정답은 구간 $[left:mid]$에 있다. 항상 $2$개 원소를 $swap$을 하는데 갯수가 홀수면 해당 구간에 혼자 남는 원소가 있다는 뜻이고 그 수가 정답이다.

갯수가 짝수라면, 위와 동일한 이유로 정답은 $[mid+1: right]$에 있다.

코드

def query(a, b):
    print('?', a, b, flush=True)
    return list(map(int, input().split()))
 
 
def solve():
    n = int(input())
    
    left, right = 1, n
    while left < right:
        mid = (left+right)//2
        ret = query(left, mid)
        cnt = 0
        for x in ret:
            if left <= x <= mid:
                cnt += 1

        if cnt%2:
            right = mid
        else:
            left = mid+1
    return left

 
for __ in range(int(input())):
    print('!', solve(), flush=True)

E. PermutationForces II