Codeforces Round #783 (Div. 2) ABC

[7번째 Contest]

빠르지 않은 3솔, D는 넘사로 어렵다

A. Direction Change

$n*m$ 크기 그리디가 주어진다. $(1, 1)$에서 $(n, m)$으로 이동하는데, 상하좌우 모두 움직일 수 있다. 두 번 이상 같은 방향으로 이동할 수 없다. $(n, m)$으로 이동하는 최소횟수를 구하라.

풀이

$n$과 $m$이 $2$ 이상이면 어떻게든 $(n, m)$으로 이동할 수 있다. $n==m$면 계단 모양으로 이동하면 된다. 그 외의 경우엔, 계단 모양으로 맨 아래 층까지 이동하고 남은 거리를 지그재그 모양으로 움직이면 된다.

코드

def solve():
    n, m = map(int, input().split())
    
    if n>m:
        n, m = m, n
    if n==1 and m>=3:
        print(-1)
    else:
        print((n-1)*2+(m-n)//2*4+(m-n)%2)
    
 
for __ in range(int(input())):
    solve()

B. Social Distance

$m$개의 의자가 있고, $n$명의 사람이 있다. 크기가 $n$인 배열 $a$가 입력된다. $i$번째 사람은 좌우로 최소 $a[i]$만큼의 공석이 있길 바란다. 모두가 원하는 대로 배치할 수 있는가?

풀이

$i$번째 사람의 왼쪽 공석 자리 수는 $max(a[i-1], a[i])$이고 오른쪽 공석 자리 수는 $max(a[i], a[i+1])$이다. 모든 사람에 대해서 위 작업을 실행하고 필요한 의자 갯수를 구할 수 있다. 필요 의자 갯수를 최소로 하기 위해서 a를 정렬할 필요가 있다.
(예: $a = [1, 2, 1, 4]$ 보다 $a = [1, 1, 2, 4]$의 경우에 필요한 의자 갯수가 적다.)

코드

def solve():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr.sort()
    
    ans = 0
    for i in range(n):
        ans += 1 + max(arr[i-1], arr[i])
   
    if ans>m:
        return 0
    return 1


for __ in range(int(input())):
    print('YES' if solve() else 'NO')

C. Make it Increasing

길이가 $n$인 배열 $a$가 입력된다. 배열 $b$는 길이가 $n$이고 모든 원소가 $0$으로 초기화된 배열이다. 우리가 할 수 있는 작업은 두가지 있다.

1. $b[i]=b[i]-a[i]$
2. $b[i]=b[i]+a[i]$

위 작업을 사용해서 배열 $b$를 증가하는 배열로 만들어야 한다. 이때, 최소 작업 갯수를 구하라.

풀이

$n=5000$이라서 $O(N^2)$ 풀이로 풀면 된다. 결과 배열 $b$가 있다고 하면, $b[i]=0$을 만족하는 $i$는 항상 존재한다. $b[i]=0$이라고 가정하고 모든 $i$에 대해서 $b[1,...,i-1]$은 첫번째 작업을 적절히 해주고 $[i+1,...,n]$은 두번째 작업을 적절히 해주면 된다.

코드

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    ans = int(1e20)
    for i in range(n):
        cnt = 0
        now = 0
        for j in range(i+1, n):
            d = (now+arr[j])//arr[j]
            cnt += d
            now = d*arr[j]
        now = 0
        for j in range(i-1, -1, -1):
            d = (now+arr[j])//arr[j]
            cnt += d
            now = d*abs(arr[j])
        ans = min(ans, cnt)
    print(ans)


solve()