Codeforces Round #802 (Div. 2) ABC

[6번째 Contest]

A는 너무 쉬웠고 B도 간단했는데 절고, C 못 풀어서 2솔 마무리

A. Optimal Path

가로 N, 세로 M 그리드가 주어진다. 가로 2, 세로 3 그리드라면, 아래와 그림과 같다. (1, 1)에서 (N, M)으로 가는 경로 중 숫자 합이 가장 작은 경로의 숫자 합은?

풀이

최적 경로는 다음과 같다.
(1, 1) -> (1, M) -> (N, M)

코드

def solve():
    n, m = map(int, input().split())
    ans = sum(range(1, m+1)) + sum(range(2*m, n*m+1, m))
    print(ans)
 
for __ in range(int(input())):
    solve()

B. Palindromic Numbers

길이가 $N$인 정수 $s$가 입력된다. 길이가 $N$인 정수 $a$를 구해야 한다. $a+s$는 펠린드롬이어야 한다. $a$의 첫번째 수는 $0$일 수 없다.

풀이

$s$의 첫번째 수가 $9$라면, $s+a$는 길이가 $n+1$이고 첫번째 수는 $1$이다. 간단하게 $a+s$를 $1$로 구성된 길이 $n+1$인 수라고 가정하면 $a$는 간단하게 구할 수 있다.

정당성 증명: $a[0] > 0$이므로 $a+s$는 반드시 길이 $n+1$이다. $a$와 $s$가 아무리 커도 두 수를 더했을 때, $a+s$의 첫번째 수는 반드시 $1$이다. $a+s$를 $1$로 구성된 길이 $n+1$인 수인 가정은 반드시 성립한다. 앞자리만 떼어놓고 생각하면, $s[0] = 9$, $(a+s)[:2] = 11$ 이다. $s[1]$은 최대 $9$이므로 $a$의 첫번째 수가 $1$보다 작아질 일이 없다.

$s$의 첫번째 수가 $9$가 아니라면, $a+s$를 $9$로 구성된 길이 $n$인 수라고 가정하면 된다.

정당성 증명: $s$가 $899$라고 해도 $a+s$가 $999$라서 $a$의 첫번째 수는 $1$이다.

코드

def solve():
    n = int(input())
    s = input()
    
    if s[0]=='9':
        print(int('1'*(n+1))-int(s))
    else:
        print(int('9'*n)-int(s))
    
for __ in range(int(input())):
    solve()

C. Helping the Nature

길이가 $n$인 배열 $a$가 입력된다. 아래 세가지 작업을 최소한으로 사용해서 배열 내 모든 숫자를 $0$으로 만들어야 한다.

1. $i$를 정하고 $a[1,...,i]$ 값을 $1$씩 감소
2. $i$를 정하고 $a[i,...,n]$ 값을 $1$씩 감소
3. $a[1,...,n]$을 $1$씩 증가

풀이

스위핑 풀이:

$a$ 안에 있는 모든 숫자를 동일하게 만들어 줘야 한다.
$a[x] < a[x+1]$라면, $a[x]$와 $a[x+1]$ 차만큼 2번째 작업$(i=x+1)$을 해주면 된다.
$a[x] > a[x+1]$라면, $a[x]$와 $a[x+1]$ 차만큼 1번째 작업$(i=x)$을 해주면 된다.
위 작업을 다하고 나면, $a$의 모든 값이 하나의 값으로 통일되는데 그 값만큼 3번째 작업을 해주면 된다.

수학적 풀이:

$a$ 안에 있는 모든 숫자를 0 이상이 되도록 맞춰준다. $a$의 최솟값이 0보다 작다면, 3번 작업을 그 수의 절댓값만큼 적용한다. $a$의 모든 수가 0이상이므로, 우리가 할 일은 $a$의 수를 전부 0으로 만들어주는 거다.
$a[i]$를 1 감소시키는 방법은 1번 작업을 i퀴리로 적용하고 2번 작업을 i쿼리로 적용하고 3번 작업을 하면 된다. 각 숫자에 대해서 위 작업을 해주면 되는데, 이 경우에 불필요한 작업이 발생하게 된다. 이 작업을 빼줘야 하는데, 1번 작업을 i쿼리로 하고 2번 작업을 i+1쿼리로 한 경우에 3번 쿼리까지 해주면 전체 원소를 1감소시켰다고 1증가시키는 거라 불필요한 작업이다. 이 경우를 세서 빼주면 된다.

코드

# 스위핑 풀이
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    ans = 0
    a, b = 0, 0 
    for i in range(n-1):
        ans += abs(arr[i]-arr[i+1]+b)
        t = min(arr[i], arr[i+1]-b)
        if arr[i] < arr[i+1]-b:
            b += abs(arr[i]-arr[i+1]+b)
        arr[i+1] = t
    print(ans+abs(arr[-1]))


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

# 수학적 풀이
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    dp = [[0]*2 for __ in range(n+1)]
    
    ans, cnt = 0, 0
    pmin = min(arr)
    if pmin < 0:
        cnt -= pmin
        for i in range(n):
            arr[i] -= pmin
    
    for i in range(n):
        dp[i][0] += arr[i]
        dp[i][1] += arr[i]
        cnt += arr[i]
    dp[-1] = [int(1e20)]*2

    for i in range(-1, n):
        pmin = min(dp[i][0], dp[i+1][1], cnt)
        cnt -= pmin
        dp[i][0] -= pmin
        dp[i+1][1] -= pmin
        
    ans = cnt
    for i in range(n):
        ans += sum(dp[i])
    print(ans)
    
 
for __ in range(int(input())):
    solve()