[코드포스] Educational Codeforces Round 95 (Rated for Div. 2)

(이번 대회는 대회 중간에 문제 오류로 인하여 Unrated 판정 공지가 나왔다. 그래서 A번과 B번만 풀었다.)

 

대회 링크: codeforces.com/contests/1418

A번 문제: codeforces.com/contest/1418/problem/A

 

  하나의 횃불(Torch)을 만들기 위해서는 1개의 막대(Stick)와 1개의 석탄(Coal)이 필요하다.

 

  우리는 처음에 1개의 막대기를 가지고 시작하며, 두 종류의 연산을 사용할 수 있다.

 

  1번) 1개의 막대기를 x개의 막대기로 교환

  2번) y개의 막대기를 1개의 석탄으로 교환

 

  이때 총 k개의 횃불(Torch)을 만들기 위해 필요한 최소 연산 횟수를 구하면 되는 문제다.

 

[ 문제 해설 ]

 

  우리는 먼저 1개의 막대기에서 시작한다. 따라서 1번 연산을 많이 사용해서 막대기의 개수를 최대한 늘린 뒤에, 그 다음에 2번 연산을 많이 사용해서 석탄을 얻어서 결과적으로 횃불을 만들면 된다.

 

  우리가 막대기를 처음에 증가시킬 때, 연산 1번을 사용할 때마다 막대기를 (x - 1)개씩 증가시킬 수 있다.

 

  k개의 횃불을 만들기 위해서는 k개의 막대기와 k개의 석탄이 필요하다. 이때 k개의 석탄을 만들기 위해서는 y * k개의 막대기가 필요하다. 즉, k개의 횃불을 만들기 위해서는 (y + 1) * k개의 막대기가 필요한 것이다.

 

  그렇다면 (y + 1) * k개 이상의 막대기를 얻기 위해 1번 연산을 얼마나 사용해야 할까? 바로 다음의 부등식을 만족시키는 한에서 최소한으로 사용해야 할 것이다.

 

  ▶ 필요한 1번 연산의 횟수 * (x - 1) + 1 >= (y + 1) * k

 

  따라서 다음의 코드를 통해서 1번 연산의 횟수의 최솟값을 구할 수 있다.

 

if ((y + 1) * k - 1) % (x - 1) == 0:
    one = ((y + 1) * k - 1) // (x - 1)
else:
    one = ((y + 1) * k - 1) // (x - 1) + 1

 

  이제 2번 연산을 k번 수행하면 최종적으로 k개의 횃불을 만들 수 있다. 따라서 최종적인 코드는 다음과 같다.

 

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    if ((y + 1) * k - 1) % (x - 1) == 0:
        one = ((y + 1) * k - 1) // (x - 1)
    else:
        one = ((y + 1) * k - 1) // (x - 1) + 1
    two = k
    print(one + two)

 

B번 문제: codeforces.com/contest/1418/problem/B

 

  N개의 정수를 담고 있는 수열이 있다. N개 중에서 몇 개의 원소는 고정되어(Locked) 위치를 변경할 수 없다. 반면에 고정되어 있지 않은(Unlocked) 원소들은 위치를 서로 변경할 수 있다.

 

  이때 누적 합(Prefix Sum)이 0 미만인 인덱스(index) 중에서 최솟값(Miminum)인 k를 계산해야 한다. 만약 누적합이 0 미만인 인덱스가 없다면 k = 0가 된다.

 

  예를 들어 [-8, 4, -2, -6, 4, 7, 1]이 있다고 해보자. 여기에서 밑줄이 쳐진 원소들은 고정된 원소들이다. 이 경우 [-8, 4, 1, -2, 4, 7, -6]로 수열을 바꾸게 되면, 누적합은 [-8, -4, -3, -5, -1, 6, 0]이다. 이때, 누적합이 0 미만인 인덱스 중에서 최솟값은 k = 5가 된다. (인덱스를 1부터 센다고 했을 때)

 

[ 문제 해설 ]

 

  이 문제는 위치가 고정된 원소를 제외하고, 남은 원소들만 내림차순 정렬을 시켜주면 된다. 그때가 바로 누적 합(Prefix Sum)의 모든 원소가 가장 크게 형성되는 때라고 볼 수 있다.

 

from collections import deque

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    flag = list(map(int, input().split()))
    
    # 고정되지 않은 원소만 담아서 내림차순 정렬
    temp = []
    for i in range(n):
        if flag[i] == 0:
            temp.append(data[i])
    temp.sort(reverse=True)

    # 최종 결과 리스트 만들기
    result = []
    temp = deque(temp)
    for i in range(n):
        # 고정되지 않은 위치에는 내림차순으로 하나씩 넣기
        if flag[i] == 0:
            result.append(temp.popleft())
        # 고정되어 있다면 그대로 가져오기
        else:
            result.append(data[i])

    # 최종 결과 리스트 출력
    for x in result:
        print(x, end=' ')
    print()