Educational Codeforces Round 103 (Rated for Div. 2) A ~ C

codeforces.com/contest/1476

Dashboard - Educational Codeforces Round 103 (Rated for Div. 2) - Codeforces

풀은 문제: A, B

못 풀은 문제: C, D, E, F, G

풀이만 보고 풀은 문제: C

코드와 풀이를 보고 풀은 문제:

 

난이도

A - 1000

B - 1300

C - 1600

D - 1700

E - 2300

F - 3000

G - 3100

 

오늘 너무 못했고 너무 아쉬웠다.

A번에 30분이나 쓰고, B번엔 1시간이나 썼다.

 

B번은 나눗셈을 이용하여 ceil로 소수점이 있으면 올림으로 풀려고 했는데, 어디에서 삑사리가 났는지 풀이자체가 틀린줄 알고 다른 풀이를 찾아보다가 시간을 너무 많이 썼다. 다른 풀이가 생각이 안나서 포기하려다가 혹시나 소수점 때문에 문제가 생긴줄 알고 몫과 나머지로 풀어보니까 맞았더라

 

C번은 아이디어는 맞았으나 시간이 없어서 제출을 못했는데, 제출해보니까 틀린 코드라서 통과를 못했을 것 같다.

 

 

 

A. K-divisible Sum

 

n칸인 배열에 아무 숫자를 넣어 배열의 합을 k배수로 만들어야하는데, 배열의 합을 최소로 하여 k배수를 만들 때 배열에 들어가는 숫자의 최대값을 구하는 문제이다.

 

일단 아이디어는 k가 n의 배수일 때 n = 4라면 k = 4일때 최대값은 [1,1,1,1]로 1, k = 8이면 [2,2,2,2]로 최대값은 2인 것을 알 수 있다.

그러면 k의 값이 4와 8사이의 값인 6이라면 [1,1,2,2]로 최대값은 2로 만들 수 있을 것이다.

그러므로 k>=n이면 k가 n의 배수일 때 k를 n으로 나눈 몫이고, 배수가 아니라면 몫에 1을 더해주면 된다.

 

그러면 k가 n보다 작을 때, 즉 k<n인 경우를 확인해보자

 

n이 k의 배수일 때

n = 10, k = 5이면 배열을 1로만 채워도 10이기 떄문에 5의배수가 나오므로 답은 1이다.

그런데 n이 k의 배수가 아니라면

 

n = 10, k = 4이면

배열이 1로만 채워져 있는 배열의 합 10과 배열이 2로만 채워진 배열의 합 20사이에 4의 배수인 12, 16, 20이 들어있으므로 최대값은 2가 될 수 있다.

마찬가지로 n = 50, k = 41을 하면

배열이 1로만 채워져있는 배열의 합 50과 배열이 2로만 채워져있는 배열의 합 100사이에 41의 배수인 82가 들어있으므로 최대값은 2가 될 수 있다.

그러므로 n > k일 때는 n이 k의 배수일 때 답은 1이고, n이 k의 배수가 아닐때의 답은 2이다.

 

def main():
    for _ in range(int(input())):
        n, k =map(int,input().split())
        if k >= n:
            if k%n: print(k//n+1)
            else:print(k//n)
        else:
            if n%k == 0:print(1)
            else:print(2)

 

 

 

 

B. Inflation

 

공식이 이렇게 있는데 배열의 값들을 변경하여 가격의 증가량이 k%를 초과하지 않도록 만들면 되는 문제이다.

 

아래 sum(a[0] .. a[i-1])을 val이라고 생각해보자

 

이렇게 생각할 수 있다.

그리고 가격의 증가량이 k%가 안넘어간다면 분모의 값이 충분하다는 것이기 때문에 넘어가주고, k%가 초과하는 것들은 비율이 k/100으로 맞춰주면 될 것이다.

 

그러면 a[i]의 값을 그대로 두고, val의 값을 늘려줘야하므로 늘려야할 값을 x라고 두자

 

이런 공식이 나온다.

이걸 정리하면

a[i], k, val의 값을 모두 알고 있으므로 x의 값을 바로 구할 수 있다.

하지만 나머지가 들어가기 때문에 k로 나누어 떨어지면 //를 이용하여 몫을 구하고, 나누어 떨어지지 않으면 x가 소수점이기 때문에 몫에 1을 더해주면 된다.

그런 값중에서 최대값을 찾아주면 된다.

 

def main():
    for _ in range(int(input())):
        n, k =map(int,input().split())
        p = [*map(int,input().split())]
        ans = 0
        val = p[0]
        for i in range(1,n):
            if p[i]*100 > val*k:
                x = (p[i]*100 - k*val)//k
                if (p[i]*100 - k*val)%k: x+=1
                ans = max(ans,x)
            val += p[i]
        print(ans)

 

 

C. Longest Simple Cycle

 

1번째 체인에는 연결되는 점이 1~2개가 나올 수 있고, 1번째부터 n-1번째 체인에서는 연결되는 점이 2~4개, n번째 체인에서는 무조건 2개가 나올 수 있다.

 

이 문제에서 고려해야할 것은 a[i] = b[i]일 때와 c[i-1]의 막대 길이부터 시작하는 것과 그동안 더한 길이 + c[i-1]에 해당하는 길이의 크기를 구분해줘야한다.

 

오른쪽에서 왼쪽으로 훑어보면 그동안 계산해온 길이를 z라고 할 때

체인을 이어야하므로 변이 선이 2개가 생기니 z += 2를 하고

ans = max(ans, z + abs(a[i]-b[i]))를 해준다.

 

그리고 a[i] != b[i]일 때는 z의 값을

1. z + c[i-1]에 해당하는 일부 길이

2.c[i-1]의 전체 길이

둘 중 큰 값을 가져온다.

2의 경우에는 그동안 싸이클이 없어서 더해온 길이 3에 c[i-1]의 일부 길이가 2이고, c[i-1]의 길이가 100이라면 c[i-1]막대부터 시작하는 싸이클을 찾으는게 더 이득이기 때문이다

 

a[i] = b[i]일 때는 z의 값을 c[i-1]의 전체 길이를 가져오면 된다.

그리고 ans를 출력하면 된다.

 

왼쪽에서 오른쪽으로 훑어보는 것도 마찬가지이다.

 

코드 구현은 아무거나 해도되는데 이 글에서는 오른쪽에서 왼쪽으로 훑는게 더 쉬워보이길래 해당 방법으로 코드를 구현하였다.

 

 

def main():
    for _ in range(int(input())):
        n = int(input())
        c = [*map(int,input().split())]
        a = [*map(int,input().split())]
        b = [*map(int,input().split())]
        z = c[-1]-1
        ans = 0
        for i in range(n-1,0,-1):
            z += 2
            ans = max(ans, z + abs(a[i] - b[i]))
            if a[i] != b[i]:z = max(z+min(a[i],b[i])-1+c[i-1]-max(a[i],b[i]),c[i-1]-1)
            else:z = c[i-1] -1
        print(ans)