Codeforces Round #792 (Div. 1 + Div. 2)

AB 무난하게 풀고 C가 좀 오래 걸렸지만, D를 10분만에 풀어서 커버쳤다.. D 풀때, 직관 미쳤다.. 이번 라운드는 프리텟이 너무 약해서 시스텟에서 BC 터진 사람이 수백명 ㄷㄷ.
난 숙청의 칼날에서 무사히 살아남아 퍼플 퍼포 뽑아내고 블루 갔지롱~

A. Digit Minimization

0이 포함되지 않은 정수 N이 주어진다. 다음 과정을 반복한다. N의 숫자 두개를 고르고 위치를 바꾼다. N의 맨 오른쪽 숫자를 지운다. 이 과정을 반복하면 1개 숫자만 남게 되는데, 이 수가 가장 작은 수가 되게 하라.

풀이

손으로 몇 번 써보면 알 수 있다.

코드

for __ in range(int(input())):
    n = input()
    if len(n)==2:
        print(n[-1])
    else:
        print(min(list(n)))

B. Z mod X = C

$a, b, c$ 가 주어졌을 때, $x, y, z$를 구하는 문제다.

풀이

간단한 코드로 푸는 방법을 고민해봤다.

위 수식으로 우리가 알 수 있는 건 다음과 같다.

각각 몫을 1이라고 가정하면,

첫번째, 두번째 수식에 따르면, $x > y$ 이고 $y > z$ 인데, 세번째 수식에 따르면 $z > x$가 되서 성립하지 않는다.

이럴 때, 세번째 수식의 몫을 0으로 설정해주면 $z=c$가 된다.

따라서 $x = a+b+c, \; y = b+c,\; z = c$ 이다.

코드

for __ in range(int(input())):
    a, b, c = map(int, input().split())
    print(a+b+c, b+c, c)

C. Column Swapping

$N*M$ 크기의 배열이 주어진다. 배열의 두 열을 단 한 번만 swap해서, 각 행을 단조 증가 상태로 만들 수 있지 확인하는 문제다.

풀이

주어진 배열을 $A$라 하자. $A$의 각 행이 정렬된 배열 $B$를 만든다.

$A$과 $B$의 각 원소를 비교하며, swap이 발생한 column을 $v$에 저장한다.

$v$의 길이가 2보다 크면, 3개 이상의 column을 swap 해야 하므로 $-1$을 리턴한다.

v의 길이가 0이라면, swap할 필요가 없으므로 $1, 1$을 리턴한다. 남은 건 $v$의 길이가 2일 때이다.

$v$의 두 원소 $ans1, ans2$는 swap할 column의 번호다.

$A$의 $ans1, ans2$ column을 swap 했을 때, 결과가 동일하다면 $ans1, ans2$가 정답이다.

그렇지 않으면 swap할 방법이 없으므로 $-1$을 리턴한다.

코드

import sys
input = sys.stdin.readline


def solve():
    n, m = map(int, input().split())
    A = [list(map(int, input().split())) for __ in range(n)]
    B = []
    for i in range(n):
        B.append(list(sorted(A[i])))
    
    v = []
    for j in range(m):
        for i in range(n):
            if A[i][j] != B[i][j]:
                v.append(j)
                break
    
    if len(v) > 2:
        return [-1]
    
    if len(v) == 0:
        return [1, 1]
    
    ans1, ans2 = v
    
    c1, c2 = [0]*n, [0]*n
    for i in range(n):
        c1[i] = B[i][ans1]
        c2[i] = A[i][ans2]
    
    if c1==c2:
        return [ans1+1, ans2+1]
    return [-1]


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

D. Traps

1부터 N까지 길에 함정이 N개 있다. $i$번 길을 지나면, $a_i$ 피해를 입는다. 점프를 하면 해당 길을 지나칠 수 있다. 최대 $K$번 점프를 할 수 있다. 점프를 할 때마다, 점프 후에 받는 피해가 $1$씩 커진다. 길을 지나갈 때, 받는 최소 피해를 구해라.

풀이

$n, k \leq 2*10^5$ 이므로 $O(n)$ 풀이나 $O(n log n)$ 풀이를 사용해야 한다.

dp로 할까 했지만, dp의 경우 $O(n^2)$ 라서 안되고, 이건 무조건 $O(n)$으로 풀어야 하고 문제 특성상 그리디라 생각했다.

난 점프를 할 때 증가하는 가중치가 단조 증가라는 걸 보고 $a_i+i$를 기준으로 정렬하면 될거라 생각했다.

우선, 점프는 전부 써야 정답이 최소가 된다.

같은 점프도 최대한 늦게 쓸 수록 정답이 최소가 된다.

점프를 쓸 때마다 추가 피해는 증가하고, 이는 단조 증가 함수 형태를 띈다.

해당 위치가 정렬 기준에 있어서 유의미한 가중치가 될거라 생각해서,, 그리고 정답이었다.

여기서부터는 증명이다.

$i$번째에서 점프를 하면 그 점프로 인해 받는 피해는 총 $N-i$ 이다. 남은 $N-i$ 동안 $1$의 피해를 계속 받으므로..

여기서 문제는 앞으로 지나갈 곳을 $N-i$ 개라고 생각한 거다.

우리는 점프 횟수를 모두 쓸 거기 때문에 $N-i$에 남은 점프 횟수를 빼야 한다.

첫 점프에서 $N-i$ 피해를 입는다고 가정하면, 우리는 $K-1$ 만큼의 피해를 더 입은 거다. 실제로 받는 피해는 $(N-i)-(K-1)$ 이다.

총 K번의 점프에서 우리가 받는 초과 피해는 $K-1, K-2, ... , 0$으로 총 ${K*(K-1)} \over{2}$이다.

여기서 생각해보면, 우리가 받는 모든 피해는 $i$에만 국한된다.

각 단계에서 받는 피해는 $a[i]-(n-i)$ 이다.

$a[i]+i$를 기준으로 정렬해서 그리디하게 풀어주면 된다!

코드

import sys
input = sys.stdin.readline 
 
 
def solve():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    a = [(arr[i]+i, i) for i in range(n)]
    a.sort()
    
    ans = []
    for i in range(n-k):
        ans.append(a[i][1])
    ans.sort(reverse=True)
    
    w = 0
    ret = 0
    for i in range(n):
        if not ans:
            break
        if i==ans[-1]:
            ret += w+arr[i]
            ans.pop()
        else:
            w += 1
        
    return ret
 
 
for __ in range(int(input())):
    # solve()
    # print('YES' if solve() else 'NO')
    print(solve())