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

codeforces.com/contest/1478

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

 

풀은 문제: A, B, C

못 풀은 문제: D, E, F

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

 

 

 

난이도

A - 800

B - 1100

C - 1700

D - 1800

E - 1900

F - 2200

 

 

 

 

C번 예외처리할게 좀 많아서 코드 보는 나도 헷갈렸다. 바로 맞을 수 있는 문제였는데 코드 한 줄을 착각해서 2번 틀리고 통과했다. 중요한 내용은 메모장에 기록해두고 코드 제출할 때 확인해야할 것 같다.

 

 

 

A - Nezzar and Colorful Balls

 

번호가 많이 언급된 숫자를 선택하여 해당 숫자가 몇 번 나왔는지 제출하면 된다.

 

def main():
    for _ in range(int(input())):
        n = int(input())
        a = [*map(int,input().split())]
        ans = [0]*(n+1)
        for i in range(n):
            ans[a[i]]+=1
        print(max(ans))

 

 

 

B - Nezzar and Lucky Number

 

숫자들 안에 d가 있으면 그것을 럭키넘버라고 한다.

어떤 수 a[i]를 럭키넘버들의 합으로 표현할 수 있는지 여부를 구하는 문제이다.

 

만약 d = 7인 럭키넘버는 7, 17, 27, ... , 70, 71, ... 과 같이 7이 들어있는 숫자들이다.

 

여기서 제일 중요한 아이디어는 a[i]에서 숫자를 바꿔서 d의 배수로 나타내야한다는 생각이 필요하다.

 

숫자를 바꾸려면 어떤 수를 빼는게 좋다.

어떤 수를 빼서 d의 배수로 만드는 방법은 a[i]를 d로 나눴을 때 나머지가 k라면 럭키넘버중에 나머지가 k인 럭키넘버에서 가장 작은 수를 빼면 d의 배수로 나타낼 수 있다.

 

그래서 for문 i=0 ~ 9를 이용하여 10*i + d와 10*d + i로 나머지가 0부터 d-1인 숫자들중 가장 작은 숫자들을 Dict에 저장해둔다.

 

그다음 a[i]가 만약 나머지가 k일때 Dict[k]의 값이 a[i]보다 큰지 작은지 확인하면 된다.

a[i] >= Dict[k]면 a[i] - Dict[k]는 d로 나눴을 때 나머지가 0이 나와서 d의 합으로 구할 수 있고

a[i] < Dict[k]면 무슨 짓을 해도 나머지가 0이 안나와서 답을 구할 수 없다.

 

def main():
    for _ in range(int(input())):
        q, d=  map(int,input().split())
        a = [*map(int,input().split())]
        Dict = defaultdict(lambda: 0)
        for i in range(10):
            if Dict[(i*10+d)%d] != 0: break
            Dict[(i*10+d)%d] = i*10+d
        for i in range(10):
            if Dict[(d*10+i)%d] == 0:
                Dict[(d*10+i)%d] = d*10+i
        for i in range(q):
            z = a[i] % d
            if Dict[z] > a[i]:print('NO')
            else:print('YES')

 

 

C. Nezzar and Symmetric Array

 

예외처리를 해줘야할 것이 있다.

1. 홀수면 안된다는 것

2. a[i]와 같은 값인 a[j]가 있어야할 것

3. a[i]와 같은 값이 단 하나만 존재해야할 것

 

오름차순으로 정렬을 한 뒤, 위에 있는 예외처리를 다 해주면 a[i]와 같은 값이 하나밖에 없고, 짝수만 있는 배열이 나온다.

그다음 중복 숫자를 제거하여 다른 arr이라는 배열을 만들어준다.

그리고 이리저리 굴리다보면 규칙성이 나온다.

답 배열중에서 음수를 제외한 양수를 오름차순한 배열을 ans라고 가정하자

 

arr[0]의 값은 (배열 ans의 합)*2 라는 값이 나오고

(arr[1] - arr[0])  // 2 는 ans[1]과 ans[0]의 값 차이(만약 왼쪽 식이 3이라면 첫번째 값은 x이고, 두번째 값은 x+3임)

(arr[2] - arr[1]) // 3 은 ans[2]과 ans[1]의 값 차이(왼쪽식이 4가 나온다면 ans[0] = x, ans[1] = x+3 일때 ans[2] = (x+3)+4 = x+7 가 나온다)

(arr[3] - arr[2]) // 4 는 ans[3]과 ans[2]의 값 차이(왼쪽식이 12가 나온다면 ans[2] = x+7일 때, ans[3] = x+19가 된다)

 

이런 규칙성이 나온다.

이것을 이용하면 n*x + @ = arr[0]//2라는 공식이 나온다.

그래서 arr[0]//2에 (arr[i] - arr[i-1]) // i+1을 빼주면 arr[0]//2 - @가 나오는데 이 값이 n으로 나누어 떨어지는지 확인한다. 이때 @가 arr[0]//2보다 작아야한다. 

그리고 문제에서 숫자들이 겹치면 안된다고 했으므로 arr[0]//2 - @ = 0이 나오면 답 배열에 0이 2개나 나오므로 답이 안된다.

 

def main():
    for _ in range(int(input())):
        n = int(input())
        a = sorted([*map(int,input().split())])
        Dict = defaultdict(lambda: 0)
        arr = []
        flag = False
        for i in range(2*n):
            if a[i]%2:flag=True
        if flag:print('NO');continue

        for i in range(0,2*n,2):
            arr.append(a[i])
            if a[i] != a[i+1]:flag = True
        if flag:print('NO');continue

        for i in range(0,2*n,2):
            Dict[a[i]]+=1
            if Dict[a[i]] > 1:flag=True
        if flag:print('NO');continue
        ans = arr[0]//2
        val = [0]
        for i in range(1,n):
            if (arr[i]-arr[i-1])%(i*2): flag = True;break
            val.append(val[-1]+(arr[i]-arr[i-1])//(i*2))
        if flag:print('NO');continue
        ans -= sum(val)
        if ans > 0 and ans % n == 0: print('YES')
        else:print('NO')