Codeforces Round #696 (Div. 2) A ~ C

codeforces.com/contest/1474

Dashboard - Codeforces Round #696 (Div. 2) - Codeforces

 

 

풀은 문제: A, B

못 풀은 문제: C, D, E, F

풀이만 보고 풀은 문제: C
풀이와 코드를 보고 풀은 문제:

 

 

난이도

A - 800

B - 1000

C - 1700

D - 2200

E - 2500

F - 3000

 

 

 

문제 제대로 읽은줄 알았는데 왜 C번에서 큰 숫자로 바꾼다는 내용을 까먹었을까. 문제를 두 숫자중에 하나를 선택하는걸로 기억하고 계속 풀이를 생각했었다.

대회가 끝나고 학회분들께 풀이를 들어도 왜 무조건 큰 수를 선택하는지 이해가 안되서 문제를 다시보니 큰 숫자로 바꾼다고 하더라 ㅋㅋ

40분정도 남기고 도저히 풀이가 생각이 안나서 다른거 하고 있었는데, 문제를 제대로 이해한게 맞는지 다시 읽어볼걸 그랬다

 

 

 

 

A. Puzzle From the Future

 

숫자들이 서로 연속되지 않게 나오면서도 무조건 큰 수를 나오게 해야하므로 경우의 수를 나눠서 풀 수 있다.

b[i]가 1일 경우

앞의 숫자가 2일 때 a[i] = 0으로 1을 만들어야하고

앞의 숫자가 1이나 0일 때 a[i] = 1로 2를 만들면 된다.

 

b[i]가 0일 경우

앞의 숫자가 2나 0일 때 a[i] = 1로 1을 만들어야하고

앞의 숫자가 1일 때 a[i] = 0으로 0을 만들어야한다.

 

이걸 그대로 구현하면 된다.

 

def main():
    for _ in range(int(input())):
        n = int(input())
        b = input()
        D = []
        ans = []
        for i in range(n):
            if b[i] =='1':
                if len(D) == 0:
                    D.append(1)
                    ans.append(2)
                else:
                    if ans[-1] == 1:
                        D.append(1)
                        ans.append(2)
                    elif ans[-1] == 2:
                        D.append(0)
                        ans.append(1)
                    else:
                        D.append(1)
                        ans.append(2)
            else:
                if len(D) == 0:
                    D.append(1)
                    ans.append(1)
                else:
                    if ans[-1] == 0:
                        D.append(1)
                        ans.append(1)
                    elif ans[-1] == 1:
                        D.append(0)
                        ans.append(0)
                    else:
                        D.append(1)
                        ans.append(1)
        print(''.join(map(str,D)))

 

 

 

 

 

B. Different Divisors

 

처음에는 [1, 1+d, 1+2*d, (1+d)*(1+2*d)]가 바로 생각이 날 것이다.

그래서 d = 3일 때를 생각하면 1 4 7 28로 답이 28이 나오는데 28은 1 2 4 6 12 28이라 d = 1이므로 틀린 답이다.

이거 때문에 1의 다음수가 1+d이상인 소수인 것을 알아챌 수 있다.

 

그래서 에라토스테네스의 체로 소수를 저장한 배열을 구하고, while문 2개를 이용하여 두번째 값와 세번째 값을 각각 구하면 된다.

두번째 값은 1+d이상인 소수

세번째 값은 (두번째 값) + d 이상인 소수

를 구하면 된다. 그런다음 두번째 값과 세번째 값을 곱하면 답이 나온다.

 

def main():
    def primelist(n):
        s = [True] * (n + 1)
        for i in range(2, int((n) ** 0.5) + 1):
            if s[i]:
                for j in range(i + i, n + 1, i):
                    s[j] = False
        return [i for i in range(2, n + 1) if s[i]]
    D = primelist(2*10**5+1000)
    for _ in range(int(input())):
        d = int(input())
        x = 0
        while 1:
            if D[x] - 1 >= d:break
            x += 1
        y = x
        while 1:
            if D[y] - D[x] >= d:break
            y += 1
        print(D[x]*D[y])

 

 

 

 

C. Array Desturction

 

배열이 주어지고 어떠한 수 x가 있을 때

1. 배열에 있는 숫자를 두 개 선택하여 합이 x이면 삭제한다.

2. 삭제하였으면 x의 값을 선택한 두 숫자중 큰 값으로 변경하고 모든 배열을 삭제할 때까지 1을 반복한다.

이렇게해서 배열을 모두 삭제할 수 있는지 여부를 판단하고, 삭제할 수 있으면 처음 x값과 숫자 두 개를 어떻게 선택하였는지 차례로 출력하면 된다.

 

 

일단 배열을 전부 삭제해야하므로 선택하는 두 수중에 하나는 무조건 남아있는 배열에서 제일 큰 수여야 한다.

왜냐하면 선택한 두 수중에 하나가 남아있는 배열중 가장 큰 값이 아니라면 남아있는 배열중 가장 큰 수는 음수랑 더해야하는데, 문제에서는 배열에 음수가 없으므로 삭제를 못하게 된다.

 

그럼 이제 프로그램을 돌려보면 처음 배열에서 가장 큰 수(x)와 어떠한 수(y)를 삭제한다.

그 이후로는 가장 큰 수에 맞춰서 하면 되니까 남아있는 배열중 가장 큰 수(a)와 x-a를 삭제해줘야하는데, 여기서 x-a가 배열에 남아있는지 확인해주면 된다.

그다음 남아있는 배열중 가장 큰 수(b)와 a - b를 삭제해줘야하는데, 여기서 a - b가 배열에 남아있는 숫자인지 확인해주면 된다.

이것을 반복하면 된다.

 

그럼 이제 y를 골라야 하는데 이건 어떻게 골라야할지 모른다. 근데 n=1000이므로 배열의 크기는 2000이니 브루트포스를 해주면 된다.

 

파이썬은 defaultdict(lambda: 0)을 사용하면 된다.

 

from collections import defaultdict

def main():
    for _ in range(int(input())):
        n = int(input())
        k = defaultdict(lambda: 0)
        a = sorted([*map(int,input().split())])[::-1]
        for i in range(2*n):
            k[a[i]] += 1
        for i in range(2*n):
            k_copy = defaultdict(lambda: 0)
            k_copy[a[0]] += 1
            if k_copy[a[i]] < k[a[i]]: k_copy[a[i]]+=1 # i = 0일 경우를 대비해서 if문
            else:continue
            ans = [a[i]+a[0],[a[i],a[0]]]
            flag = True
            for j in range(2*n):
                if k_copy[a[j]] >= k[a[j]]: continue #남은 배열에 a[j](위에서 언급한 a, b값)가 없을 경우
                else:
                    nx = max(ans[-1]) - a[j] #위에서 언급한 x-a, a-b 값을 nx라고 해줌
                    k_copy[a[j]] += 1
                    if k_copy[nx] < k[nx]: #남은 배열에 nx가 들어있을 경우
                        k_copy[nx] += 1
                        ans.append([a[j],nx])
                    else:
                        k_copy[a[j]] -= 1
                        flag = False
                        break
            if flag:
                print('YES')
                print(ans[0])
                for j in range(1,len(ans)):
                    print(ans[j][0],ans[j][1])
                break
        else:print('NO')

 

For - else문은 for문 내부의 break로 인해 강제로 for문을 탈출하지 않고, for문을 전부 돌려서 탈출하는 경우 else문이 실행된다.

 

k_copy는 원래 k를 복사해서 숫자를 하나씩 빼려다가, 복사하면 시간초과가 나길래 복사하지 않는 방법으로 만들었다.