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

codeforces.com/contest/1117

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

 

풀은 문제: A, B

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

풀이만 보고 풀은 문제: 

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

 

 

난이도

A - 1100

B - 1000

C - 1900

D - 2100

E - 2200

F - 2500

G - 2500

 

 

 

C번 에디토리얼을 보니까 문자열 s를 몇바퀴 돌려야하는지 구하는 것에서 막혔는데 에디토리얼을 보니 이진 탐색이였다.

며칠전에도 백준에서 이진 탐색 문제를 못 풀었는데 이진 탐색에 많이 취약한 것 같다.

 

 

 

 

A. Best Subsegment

 

평균

[l, r]의 평균의 최대값을 만족하는 최대의 길이를 구하는 문제이다.

 

만약 a = [7,7,7,7,8,8]이라면 a[0] ~ a[4]까지의 평균은 7.xxx일 것이고, a[4]의 평균은 8이므로 연속되는 가장 큰 수의 길이를 구하면 되는 문제이다.

 

def main():
    n = int(input())
    a = [*map(int,input().split())]
    D = [[a[0],1]]
    for i in range(1,n):
        if D[-1][0] == a[i]: D[-1][1] += 1
        else: D.append([a[i],1])
    D.sort(key=lambda z:[-z[0],-z[1]])
    print(D[0][1])

 

 

B. Emotes

 

카드를 m번 선택하는데 한 카드를 최대 k번 연속 낼 수 있을 때, 최고점을 찾는 문제이다.

그러므로 배열을 내림차순 정렬하고 그 배열을 a라고하면 a[0]을 k번 내고, a[1]을 1번 내고, a[0]를 k번 내고, a[1]을 1번 내고,... 이렇게 반복하는 방법이 최고점이 된다.

 

그러므로 m을 k+1의 몫만큼 (a[0] * k + a[1]) 을 곱하고, 나머지만큼 a[0]를 곱해서 더해주면 된다.

 

def main():
    n,m,k = map(int,input().split())
    a = [*map(int,input().split())]
    a.sort(reverse=True)
    z = m//(k+1)
    ans = z*k*a[0] + z*a[1] + (m%(k+1))*a[0]
    print(ans)

 

 

C. Magic Ship

 

U, D, L, R로 방향이 불고 있는데 이때 배도 같이 상하좌우로 움직이거나 그대로 놔둘 수 있다.

배가 (x1, y1)에서 출발하여 (x2, y2)에 도달할 수 있는지 여부와 도달할 수 있으면 가장 빠른 도착시간이 며칠인지 출력하는 문제이다.

 

일단 prefix array를 이용하여 첫 날부터 i번째 날까지 이동한 바람의 변위를 구한다.

그리고 이분탐색을 이용하여 문자열 s를 몇바퀴 돌고 나서야 첫 날부터 i번째 날까지 이동해야 (x2, y2)로 이동할 수 있는지 구한다.

이분 탐색에 넣을 값은 l은 0이고, r은 (x1, y1) = (0, 0),  (x2, y2) = (10**9, 10**9)일 때 n = 10**5인데 첫 날부터 n번째 날까지 이동할 수 있는 변위가 (1,1)인 경우 10**5 * 10**9일만큼 걸릴 수도 있다. 그러므로 r은 10**14 + 1로 해야 ans의 값이 10**14이하일 때는 갈 수 있다는 뜻으로 설정할 수 있고, 10**14 + 1이면 못간다는 뜻으로 설정할 수 있다.

 

def main():
    def dir(v):
        if v=='U': return [0,1]
        if v=='D': return [0,-1]
        if v=='L': return [-1,0]
        if v=='R': return [1,0]
    x1,y1 = map(int,input().split())
    x2,y2 = map(int,input().split())
    n = int(input())
    s = input()
    move = [[0,0] for _ in range(n+1)]
    for i in range(1,n+1):
        nx, ny = dir(s[i-1])
        move[i] = [move[i-1][0]+nx, move[i-1][1]+ny]
    ans = 10**14+1
    l,r = 0, 10**14+1
    while l <= r:
        mid = (l+r)//2
        week = mid//n
        day = mid%n

        x = x1 + move[day][0] + week*move[-1][0]
        y = y1 + move[day][1] + week*move[-1][1]

        if abs(x-x2) + abs(y-y2) <= mid:
            ans = min(ans,mid)
            r = mid - 1
        else:l = mid + 1
    print([ans,-1][ans==10**14+1])