Codeforces Round 640 (Div. 4)

• 후기
• A. Sum of Round Numbers (00:04)
• B. Same Parity Summands (00:12)
• C. K-th Not Divisible by n (00:34)
• D. Alice, Bob and Candies (00:49)
• E. Special Elements (01:05)
• F. Binary String Reconstruction (01:33)
• G. Special Permutation (01:17)

후기

- 대회 링크: https://codeforces.com/contest/1352

- 전부 다 맞혀서 8솔로 마무리했다~

- 버츄얼 레이팅이 $1400$을 넘어버려서 결과가 반영될지 모르겠고 만약 반영되지 않는다면 앞으로는 Div. 4에 참여해도 의미가 없을테니 마지막 Div. 4가 되는 셈이었다. 그래서 대미를 장식하고자 최초의 Div. 4 대회에 참여했다

- Announcement를 보니까 문제 난이도를 Div. 3의 D 이하로 출제한다고 했다. 그렇다는 건 나는 모든 문제를 다 풀어야만 한다는 뜻이다. 다 못풀면 어쩌나 생각했는데 다행이 모든 문제를 다 풀 수 있었다

- 다 풀고 나서 보니까 확실히 최근에 열린 Div. 4보다 쉬웠다 (애초에 다 푼적도 처음이야). 근데 A, B, C번 문제가 생각보다 어려워서 매우 당황했다. C번 문제를 푸는 데 22분으로 가장 많은 시간을 사용했다. 하지만 뒷 번호의 문제는 안 어려울 테니까 여기서 조금 오래 걸려도 괜찮다고 상기하면서 멘탈을 잡았고 모든 문제를 다 풀 수 있었다

- 뒷 번호 문제의 경우 F, G번 문제는 constructive 문제였는데 나는 F번 문제의 난도가 더 높다 생각한다. F번 문제는 논리적으로 풀었고 G번 문제는 직관으로 풀었다. 근데 직관이 없으면 오히려 F번 문제보다 어려울 수도?? 나는 잘 모르겠다

- 근데 이거 레이팅에 반영되는데? Div. 4에 더 참여할지 Div. 3에 참여할지 고민을 해봐야겠다

A. Sum of Round Numbers (00:04)

- $n$의 $i(>1)$번째 자리의 값 $d_i$가 $0$이 아니라면 $d_i \cdot 10^{(i-1)}$를 항으로 가져야 한다. 현재 $n$에 대해 $d_i$는 $n$을 $10$으로 나눈 나머지이며 이후 $n$은 $\left\lfloor\frac{n}{10}\right\rfloor$로 $i$는 $i+1$로 갱신해주면 된다

- 코드 리팩토링 하면서 보니까 문자열로 바꿔서 푸는 게 더 쉬웠을 듯하다

def solve_testcase(n):
    i = 1
    nums = []
    while n:
        d_i = n % 10
        if d_i > 0:
            nums.append(d_i * 10**(i - 1))
        n //= 10
        i += 1
    return nums


def solution():
    t = int(input())
    for _ in range(t):
        n = int(input())
        answer = solve_testcase(n)
        print(len(answer))
        print(*answer)


solution()

B. Same Parity Summands (00:12)

- $a_i$는 최소 $1$이므로 $n < k$라면 정답은 NO이다

- $k$가 홀수라고 하자. 짝수를 홀수 번 더하면 짝수이고 홀수를 홀수 번 더하면 홀수이다. 따라서 $n$이 짝수면 $a_i$도 짝수이고 $n$이 홀수면 $a_i$도 홀수여야 한다

- $a_i$가 홀수라면 $k-1$개의 $1$과 $1$개의 $n - k + 1$로 배열을 구성하자. $a_i$가 짝수라면 $k-1$개의 $2$와 $1$개의 $n - 2k + 2$로 배열을 구성하자. 단, $n \ge 2k$여야 한다

- 이제 $k$가 짝수라고 해보자. 짝수를 짝수 번 더하면 짝수이고 홀수를 짝수 번 더하면 짝수이다. 따라서 $n$은 무조건 짝수여야 한다. $k-1$개의 $1$과 $1$개의 $n - k + 1$로 배열을 구성하면 된다

def solve_testcase(n, k):
    if n < k:
        return []
    if k % 2 == 1:
        if n % 2 == 1:
            return [1] * (k - 1) + [n - k + 1]
        if n < 2 * k:
            return []
        return [2] * (k - 1) + [n - 2 * (k - 1)]
    if n % 2 == 1:
        return []
    return [1] * (k - 1) + [n - k + 1]


def solution():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        array = solve_testcase(n, k)
        if array:
            print("YES")
            print(*array)
        else:
            print("NO")


solution()

C. K-th Not Divisible by n (00:34)

- $n$으로 나누어 떨어지지 않는 $k$번째 자연수를 출력하면 된다. $1$부터 시작해 $n$개씩 묶은 그룹을 생각해보자. 즉, $[1, 2, \dots, n], [n + 1, n + 2, \dots, 2n], \dots $

- 각 그룹에 대해 $n$으로 나누어 떨어지는 수는 $1$개뿐이다. 즉, 각 그룹마다 마지막 수를 제외한 $n-1$개의 수가 $n$으로 나누어 떨어지지 않는다

- $k = q(n-1) + r$로 놓자. 그럼 정답은 $q + 1$번째 그룹의 $r$번째 수인 $qn + r$이다. 단, $r=0$이면 정답은 $qn - 1$이 된다

def solve_testcase(n, k):
    q = k // (n - 1)
    r = k % (n - 1)
    if r == 0:
        return q * n - 1
    return q * n + r


def solution():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        answer = solve_testcase(n, k)
        print(answer)


solution()

- 매개 변수 탐색을 이용해서도 풀 수 있다고 한다 (wow)

- $x$ 이하의 자연수 중 $k$로 나누어 떨어지지 않는 수의 개수를 $f(x)$라 할 때 $f(x) = x - \left\lfloor\frac{x}{k}\right\rfloor$이며 단조 증가한다. 따라서 주어진 최적화 문제를 결정 문제로 바꾼 뒤 이분 탐색으로 로그 시간에 정답을 찾을 수 있다

- 이런 접근법을 써먹으려면 문제 타입을 인지하고 매개 변수 탐색을 사용하는 문제를 많이 풀어봐야 될 것 같다

D. Alice, Bob and Candies (00:49)

- 지문이 뭔가 이상한 것 같다. 나는 예시를 보고 문제를 이해했다

- 시뮬레이션 문제이므로 지문을 그대로 구현하면 된다. 단, Deque을 사용해서 popleft와 pop을 $O(1)$에 수행하도록 하자

from collections import deque


def alice_turn(array, prev):
    total = 0
    while array and total <= prev:
        total += array.popleft()
    return total


def bob_turn(array, prev):
    total = 0
    while array and total <= prev:
        total += array.pop()
    return total


def solve_testcase(array):
    array = deque(array)
    a, b = array.popleft(), 0
    prev = a
    n_moves = 1
    while array:
        if n_moves % 2 == 0: 
            total_size = alice_turn(array, prev)
            a += total_size
        else:
            total_size = bob_turn(array, prev)
            b += total_size
        n_moves += 1
        prev = total_size
    return n_moves, a, b


def solution():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        answer = solve_testcase(a)
        print(*answer)


solution()

E. Special Elements (01:05)

- $a_i$가 스페셜하다는 것은 길이가 $2$ 이상인 부분 합 중 $a_i$인 것이 존재한다는 의미이다 ($a_i \le n$이므로 부분 합도 $n$ 이하여야 한다)

- 임의의 $x$에 대해 $x=a_i$를 만족하는 $i$의 개수를 $c_x$라 하자. 만약 부분 합으로 $x$를 만들 수 있으면 스페셜한 원소는 $c_x$개 존재하는 것이다

- 이중 for문을 돌며 부분 합을 계산하자. 이때 누적 합 배열을 이용하면 $O\left(n^2\right)$에 계산할 수 있다. 따라서 전체 알고리즘의 시간 복잡도는 $O\left(n^2\right)$이고 누적 합 배열과 빈도수 배열의 크기가 $O(n)$이므로 공간 복잡도는 $O(n)$이다

from itertools import accumulate


def solve_testcase(array):
    n = len(array)
    prefix_sums = [0] + [*accumulate(array)]
    counts = [0] * (n + 1)
    for a in array:
        counts[a] += 1
    count = 0
    for i in range(2, n + 1):
        for j in range(i - 1):
            s = prefix_sums[i] - prefix_sums[j]
            if s <= n and counts[s] > 0:
                count += counts[s]
                counts[s] = 0
    return count


def solution():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        answer = solve_testcase(a)
        print(answer)


solution()

F. Binary String Reconstruction (01:33)

- 길이가 $k$인 이진 문자열 $s$에 대해 길이가 $2$인 부분 문자열은 $k-1$개이다. 그리고 이들이 도출하는 경우의 수는 3개뿐이다 ($\texttt{0}$의 개수가 $0,1,2$ 중 하나)

- $n_1$과 $n_3$인 경우를 세고자 $s$를 연속한 원소들의 그룹으로 쪼개보자. 그러면 이런 형식이다 $[\texttt{0}\dots \texttt{0}], [\texttt{1} \dots \texttt{1}], \dots$ (물론 시작이 $\texttt{0}$이 아니고 $\texttt{1}$일 수도 있음)

- 각 그룹의 크기를 $c_i$라 할 때 $\texttt{0}$인 그룹이라면 $n_1$에 $c_i-1$만큼 기여하고 $\texttt{1}$이라면 $n_3$에 $c_i-1$만큼 기여한다. 그리고 그룹의 개수는 $n_2 + 1$이 된다. 즉, 그룹의 개수에서 $1$을 빼면 $n_2$이다

- 그룹을 $n_2 + 1$개 만들어두자. 그리고 각 그룹에 원소를 하나씩 넣을건데 $\texttt{0}$부터 시작해 번갈아가며 넣을 것이다. 그럼 $n_2$ 조건은 충족시켰다

- 이제 $n_1,n_3$ 조건만 충족시키면 된다. 어차피 개수만 맞추면 되니까 첫 번째 그룹에 $\texttt{0}$을 $n_1$개 추가하고 두 번째 그룹에 $\texttt{1}$을 $n_2$개 추가하자. 최종적으로 완성된 그룹을 연결하기만 하면 정답이다

- 근데 $n_2 = 0$인 경우 $n_1$ 또는 $n_3$가 $0$이니 예외 처리 해주자. $n_2 > 0$이면 $n_1, n_3$도 $0$보다 크므로 예외 처리할 경우는 더 이상 없다

def solve_testcase(n1, n2, n3):
    if n2 == 0:
        if n1 > 0:
            return "0" * (n1 + 1)
        return "1" * (n3 + 1)
    groups = [[str(i % 2)] for i in range(n2 + 1)]
    groups[0].extend(["0"] * n1)
    groups[1].extend(["1"] * n3)
    s = "".join([b for group in groups for b in group])
    return s


def solution():
    t = int(input())
    for _ in range(t):
        n1, n2, n3 = map(int, input().split())
        answer = solve_testcase(n1, n2, n3)
        print(answer)


solution()

G. Special Permutation (01:17)

- F번 문제보다 G번 문제를 더 많이 풀었길래 나도 이걸 먼저 풀었다

- 길이 $n$의 순열을 생각하자. 인접한 원소 간의 차이가 $2$ 이상 $4$ 이하인 순열을 만들면 된다. 없으면 대신 $-1$을 출력하자

- 그냥 배치를 봤을 때 수가 올라갔다가 내려가면 안 되나?

- $n$이 홀수: $1, 3, 5, \dots n, n - 1, n - 3, \dots, 4, 2$

- 이게 문제가 $n$과 $n-1$은 차이가 $1$이라 안 된다. 둘을 바꾸면? $\dots, n, n - 3, n - 1, n -5, \dots$이니까 성립한다!

- $n$이 짝수: $2, 4, 6, \dots n, n - 1, n - 3, \dots, 3, 1$

- 이것도 $n$과 $n-1$을 바꾸면 성립한다!

- $n \le 3$인 경우를 제외하면 조건을 만족하는 순열은 항상 존재하며 형태는 위와 같다

def solve_testcase(n):
    if n <= 3:
        return [-1]
    start = 1 if n % 2 == 1 else 2
    return [*range(start, n + 1, 2)] + [n - 3, n - 1] + [*range(n - 5, 0, -2)]


def solution():
    t = int(input())
    for _ in range(t):
        n = int(input())
        answer = solve_testcase(n)
        print(*answer)


solution()