Codeforces Round #542 (Div.2) A ~ D2

codeforces.com/contest/1130

Dashboard - Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) - Codeforces

풀은 문제: A, B, C, D1

못 풀은 문제: D2, E

풀이를 보고 풀은 문제: D2

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

 

난이도

A - 800

B - 1200
C - 1400
D1 - 1700

D2 - 1800

E - 2000

 

 

A번에서 2번이나 틀리고 맞췄다. A번은 빨리 풀고 넘겨야한다는 압박감 때문에 검토 안하고 바로바로 제출하는데 좀 아쉬웠다.

D1, D2같이 쉬운 버전/어려운 버전으로 나뉘는 문제에서 쉬운 버전은 보통 브루트 포스로 푸는 문제가 많길래 시간을 계산해보니까 통과할 것 같아서 주먹구구식으로 풀었는데 통과했다.

D2는 아이디어는 생각해냈는데 예외 처리를 한 줄 추가 안해줘서 시간내에 못풀었다.

 

Codeforce Anytime에서 블루를 달성했다.

방학 목표가 블루인데, 버츄얼은 달성했으니 목표의 50%는 성공한 것 같다.

 

 

 

A. Be Positive

 

n개의 배열이 있을 때, 어떤 수 d로 나누었을 때 [n/2]개 이상의 배열의 값이 양수로 만들 수 있는지 d를 구하는 문제이다.

일단 d의 범위는 0이 아닌 -1000에서 1000까지의 정수라고 하므로 음수로 나눠서 양수로 만들 수 있는 방법을 생각해볼 수도 있다.

 

그리고 어차피 양수를 양수로 나눠봤자 0이나 음수가 안나오고 양수가 나오기 때문에 양수의 개수와 음수의 개수를 세고, 양수의 개수가 [n/2]이상이면 1을 출력하고, 음수의 개수가 [n/2]이상이면 -1을 출력하고, 둘 다 아니라면 0을 출력하면 된다.

 

def main():
    n = int(input())
    a = [*map(int,input().split())]
    if n%2: k = n//2 + 1
    else: k = n//2
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if a[i] > 0: ans1 += 1
        if a[i] < 0: ans2 += 1
    if ans1 >= k:print(1)
    elif ans2 >= k:print(-1)
    else:print(0)

 

 

 

 

B. Two Cakes

 

Sasha와 Dima가 움직여서 케이크를 만드는 것이지, 케이크의 위치가 움직이지 않기 때문에 (현재 케이크의 위치 2개) - (이전 케이크의 위치 2개)를 빼서 나오는 최소값을 계속 구하면 된다.

 

def main():
    n = int(input())
    a = [*map(int,input().split())]
    D = [[] for _ in range(n)]
    for i in range(2*n):
        D[a[i]-1].append(i)
    ans = 0
    for i in range(n):
        if i==0:ans += sum(D[0])
        else:
            x,y = D[i-1]
            nx,ny = D[i]
            if abs(nx-x)+abs(ny-y) < abs(ny-x)+abs(nx-y):
                ans += abs(nx-x)+abs(ny-y)
            else:
                ans += abs(ny-x)+abs(nx-y)
    print(ans)

 

 

C. Connect

 

일단 플러드 필로 섬마다 숫자를 부여해준다.

그 후에는 만약 시작 위치와 도착 위치의 섬이 같은 숫자의 섬이라면 0이 나올 것이고, 아니라면 터널을 하나만 만들 수 있으니까 2중 for문을 이용하여 터널을 만드는 최소값을 구해주면 된다.

def main():
    n = int(input())
    r1,c1 = map(int,input().split());r1-=1;c1-=1
    r2,c2 = map(int,input().split());r2-=1;c2-=1
    D = [input() for _ in range(n)]
    fill = [[-1]*n for _ in range(n)]
    land = []
    z = 0
    for i in range(n):
        for j in range(n):
            if fill[i][j] == -1 and D[i][j] == '0':
                fill[i][j] = z
                q = deque([[i,j]])
                island = [(i,j)]
                while q:
                    x,y = q.popleft()
                    for k in range(4):
                        nx,ny = x+dx[k],y+dy[k]
                        if 0<=nx<n and 0<=ny<n and D[nx][ny]=='0' and fill[nx][ny] == -1:
                            q.append([nx,ny])
                            fill[nx][ny] = z
                            island.append((nx,ny))
                land.append(island)
                z += 1
    a = fill[r1][c1]
    b = fill[r2][c2]
    ans = float('inf')
    for x,y in land[a]:
        for nx,ny in land[b]:
            ans = min((x-nx)**2+(y-ny)**2,ans)
    print(ans)

 

 

 

D1. Toy Train(Simplified)

예제1을 풀어보면 i번째 정거장에 캔디가 여러개 있을 때, i번째 정거장에서 가장 멀리 배달해야하는 캔디부터 가져가면 된다는 것을 알 수 있다.

 

n=100, m=200이므로 위에있는 아이디어 가지고 그대로 시뮬레이션처럼 구현하면 된다.

from copy import deepcopy

def main():
    n,m = map(int,input().split())
    station = [[] for _ in range(n+1)]
    ans = [0]*(n+1)
    for i in range(m):
        a,b = map(int,input().split())
        station[a].append(b) #a정거장에 b로 배달해야할 캔디 추가
    for _ in range(1,n+1):
        sta = deepcopy(station)
        destination = [0]*(n+1)
        z=0
        flag = False
        while 1:
            for i in range(1,n+1):
                if i != _ and not flag: continue #for문 i가 1부터 시작하므로 _번째 정거장에서
                if i == _ and not flag: flag = True #출발하도록 만들어줌
                z += destination[i]
                destination[i] = 0
                if z == m: break
                if len(sta[i]):
                    p = [-1,-1] #거리가 가장 멀은 캔디를 구함
                    for nx in sta[i]:
                        if (nx+n-i)%n > p[0]:
                            p = [(nx+n-i)%n, nx]
                    sta[i].remove(p[1])
                    destination[p[1]]+=1
                ans[_]+=1
            if z==m:break
    print(*ans[1::])

 

 

D2. Toy Train

 

만약 n=5이고, 세번째 정거장에만 캔디가 5개가 있을 때

캔디가 전부 네번째 정거장에 도착해야한다면 4바퀴 + 1번의 시간이 걸릴 것이고

캔디가 전부 두번째 정거장에 도착해야한다면 5바퀴 - 1번 혹은 4바퀴 + 4번의 시간이 걸릴 것이다.

 

이걸 일반화시키면 x정거장에 캔디가 y개가 있다면 최소 n*(y-1) + 1번 이동하거나 최대 n*(y-1) + (n-1)번 이동한다는 것이다

 

이 방법을 이용하여 각 정거장마다 해당 정거장에 있는 캔디만 가지고 전부 배송하는데 시간이 얼마나 걸리는지 구한다.

그다음 2중 for문을 이용하여 i번째 정거장 출발하면 걸리는 최소 시간은

i번째 정거장과 j번째 정거장까지 걸리는 시간

+

j번째 정거장에서 출발한다고하면 j번째 있는 캔디를 전부 배분할 때 걸리는 시간

을 해주고 그중에 제일 큰 값을 구하면 된다.

 

def main():
    n,m = map(int,input().split())
    station = [[] for _ in range(n+1)]
    time = [0]*(n+1)
    ans = [0]*(n+1)
    for i in range(m):
        a,b = map(int,input().split())
        station[a].append((b+n-a)%n) #캔디를 배송하는데 걸리는 시간
    for i in range(1,n+1):
        station[i] = sorted(station[i])
    for i in range(1,n+1):
        if len(station[i]):
            time[i] = (len(station[i])-1)*n + station[i][0]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if time[j] != 0: ans[i] = max(ans[i],time[j]+(j+n-i)%n)
    print(*ans[1::])