Codeforces Round #545 (Div. 2) A ~ D

codeforces.com/contest/1138

Dashboard - Codeforces Round #545 (Div. 2) - Codeforces

풀은 문제: A, B, C

못 풀은 문제: D, E, F

풀이만 보고 풀은 문제:

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

 

난이도

A - 900

B - 1800

C - 1600

D - 1600

E - 2500

F - 2400

 

 

어제 코포 라운드가 있었는데 오늘 수강신청하는 날이라 괜히 늦잠잘까봐 안했다.

 

등수가 꽤 높다했더니 난이도보니까 B에서 다들 막혔나보다.

모든 문제를 한 번에 통과할 경우 퍼포먼스가 퍼플이 나올 수 있을 것 같아서 좀 아쉽다

 

 

A - Sushi for Two

 

[2,2,2,1,1,1]

[1,1,2,2]

처럼 1이 연속적으로 k개 나오고 2가 연속적으로 k개가 될 때만 답이 k가 될 수 있는 문제이다.

for문으로 [1,2] 혹은 [2,1]인 부분을 찾은다음 while문을 이용하여 [1]+[1,2]+[2], [1,1] +[1,2] +[2,2] 이렇게 연속적으로 나오는 범위를 구한다.

 

def main():
    n = int(input())
    t = [*map(int,input().split())]
    ans = 0
    for i in range(n-1):
        if (t[i] == 2 and t[i+1] == 1) or (t[i] == 1 and t[i+1] == 2):
            x,y = i,i+1
            z = 2; ans = max(ans,z)
            while 1:
                x-=1;y+=1
                if 0<=x<n and 0<=y<n:
                    if t[x] == t[i] and t[y] == t[i+1]:
                        z+=2
                        ans = max(z,ans)
                    else:break
                else:break
    print(ans)

 

 

 

 

B. Circus

 

규칙

- 각 예술가는 한 개의 공연만 할 수 있다.

- 두 공연에서 활동하는 예술가의 수 각각 n/2로 같다.

- 첫번째 공연에서 광대로 활동하는 예술가의 수는 두번째 공연에서 곡예사로 활동하는 예술가의 수와 같다

 

n=5000이므로 공연에 각각 최대 2500명씩 들어갈 수 있으므로 브루트포스로 구현해볼 수 있다는 것을 확인할 수 있다.

브루트 포스는 광대로 활동하는 수에 맞춰서 첫번째 공연에서 1명이 광대로 활동할 때, 2명이 광대로 활동할 때, .... , 2500명이 광대로 활동할 때로 맞춰두고, for문을 전부 통과하면 공연을 할 수 없으므로 -1을 출력하게 만든다.

 

그럼 이제 광대의 수를 맞춰줘야하는데 예술가들은 네 부류로 나뉘는 것을 확인할 수 있다.

1. 광대, 곡예사 전부 할 수 있는 예술가

2. 광대만 할 수 있는 예술가

3. 곡예사만 할 수 있는 예술가

4. 둘 다 하지 못하는 예술가

 

우리는 광대의 수를 맞춰주면서 두번째 공연에서의 곡예사의 수도 맞춰줘야하므로 1번 부류의 예술가부터 해치워야한다는 것을 알 수 있다.

왜냐하면 2순위부터 해치웠을 때, 광대의 수가 이미 k명이 나왔고 1번의 값이 k를 초과하면 두번째 공연에서 곡예사로 활동하는 사람이 1번, 3번 부류의 예술가 이기 때문에 무조건 안된다고 나온다.

하지만 1번 부류부터 해치워서 k명의 광대를 구했으면, 2번 부류의 사람은 전부 두번째 공연에서 활동하게 만들면 된다.

 

1번부터 처리해야하는 아이디어를 생각해냈으면 그다음부터는 구현만 하면 된다.

 

def main():
    n = int(input())
    c = input()
    a = input()
    D = [0,0,0,0]
    S = [[] for _ in range(4)]
    A = []
    for i in range(n):
        if c[i] == '0' and a[i] == '0':D[0]+=1;A.append(0);S[3].append(i)
        if c[i] == '1' and a[i] == '0':D[1]+=1;S[0].append(i);A.append(1)
        if c[i] == '0' and a[i] == '1':D[2]+=1;S[1].append(i);A.append(2)
        if c[i] == '1' and a[i] == '1':D[3]+=1;S[2].append(i);A.append(3)
    for t in range(n//2+1):
        ans = []
        x, y = 0, D[2]+D[3]
        for i in range(len(S[2])): #1번부류
            if x != t and len(ans) != n//2 and y > t:
                ans.append(S[2][i]+1);x+=1; y-=1
        for i in range(len(S[0])): #2번부류
            if x != t and len(ans) != n//2:
                ans.append(S[0][i]+1);x+=1
        for i in range(len(S[1])): #3번부류
            if y > t and len(ans) != n//2:
                ans.append(S[1][i]+1); y-=1
        if len(ans) != n//2 and len(S[3]) >= n//2 - len(ans): #공연자의 수가 n/2가 안될 때
            for i in range(n//2-len(ans)):                    #4번부류 사람들을 넣어줌
                ans.append(S[3][i]+1)
        if x == t and y == t and len(ans) == n//2:
            print(*sorted(ans));exit()
    print(-1)

 

 

C. Skyscrapers

 

x행 y열이 있을 때 x행의 건물들을 높이 순서대로 순위를 배정하고, y행의 건물들을 높이 순서대로 순위를 배정할 때 x행,y열 건물들의 높이 순위의 최대값을 구하는 문제이다.

 

여기서의 핵심 아이디어는 x행과 y열이 교차하는 x행y열부분의 처리방법이다.

만약 5x5 건물이 주어지고 3행3열 부분을 확인할 3행의 높이는 [1, 2, 3, 4, 5]이고, 3열의 높이는 [4, 5, 3, 6, 7] 이면

3행의 높이 순의는 [1, 2, 3, 4, 5] 이지만 3열의 높이 순위는 [2, 3, 1, 4, 5]로 3행3열의 순위가 각각 3과 1로 다르다.

이러면 3행의 순위를 낮추거나 3열의 순위를 높여야하는데, 3행의 순위는 더이상 낮게 잡을 수가 없고, 3열의 순위에 전부 2를 더해서 [4, 5, 3, 6, 7]을 만들어 줄 수 밖에 없다. 그러면 3행3열의 값은 7이 된다.

 

이런 방법을 이용하여 행 따로 열 따로 순위를 메겨본다음 2중 for문을 이용하여 윗방법과 똑같이 값을 정해주면 된다.

 

def main():
    n,m = map(int,input().split())
    a = [[*map(int,input().split())] for _ in range(n)]
    col = [defaultdict(lambda:0) for _ in range(m)]
    row = [defaultdict(lambda:0) for _ in range(n)]
    col_num = [0]*m #i번째 열에 나올 수 있는 값의 최대값
    row_num = [0]*n #i번째 행에 나올 수 있는 값의 최대값
    ans = [[0]*m for _ in range(n)]
    for i in range(n): #행 순위 정하기
        D = set()
        for j in range(m):
            D.add(a[i][j])
        D = sorted(list(D))
        z = 1
        for x in D:
            if row[i][x] == 0: row[i][x] = z; z+=1
        row_num[i] = z-1
    for j in range(m): #열 순위 정하기
        D = set()
        for i in range(n):
            D.add(a[i][j])
        D = sorted(list(D))
        z = 1
        for x in D:
            if col[j][x] == 0: col[j][x] = z; z+=1
        col_num[j] = z-1
    for i in range(n):
        for j in range(m):
            z = abs(row[i][a[i][j]] - col[j][a[i][j]]) #(i,j)에서의 순위 차이
            if row[i][a[i][j]] >= col[j][a[i][j]]:
                ans[i][j] = max(row_num[i],col_num[j]+z)
            else:
                ans[i][j] = max(col_num[j],row_num[i]+z)
    for i in range(n):
        print(*ans[i])

 

 

 

 

D. Camp Schedule 

입력값이

1110000

101

라면

1010100 라는 답이 나와야한다.

왜냐하면 겹치는 것 포함해서 101이 3개 나오므로 최대인 것이다.

그러므로 이것은 KMP알고리즘을 이용하여 t문자열의 접두사와 접미사가 똑같은 문자열을 구한다.

그다음 t를 한 번 넣고 그 이후엔 t에 겹치는 접두사를 빼고 남은 길이에서 필요한 0의 개수와 1이 개수만큼 s에 나온 1의 개수와 0의 개수를 최대한 사용하여 문자를 계속 더해주면 된다.