Codeforces Round #535 (Div. 3) A ~ E1

codeforces.com/contest/1108

Dashboard - Codeforces Round #535 (Div. 3) - Codeforces

 

풀은 문제: A, B, C, D, E1

못 풀은 문제: E2, F

 

 

난이도

A - 800

B - 1100

C - 1300

D - 1400

E1 - 1800

E2 - 2100

F - 2100

 

 

문제가 슉슉 잘풀려서 틀린거 없이 바로바로 풀었는데 퍼포먼스가 오렌지가 나왔다 ㅋㅋ

그리고 1시간 30분동안 랭킹 1페이지 공기를 맛보아서 행복했다.

 

E2는 n = 100000으로 늘어나고, m = 300 그대로인것을 보니 딱봐도 세그먼트 트리를 이용해서 시간복잡도를 줄이라는 말인 것 같다 

 

 

 

 

A. Two distinct points

 

l_1, r_1 과 l_2, r_2 값이 주어진다.

l_1과 r_1 사이의 숫자와 l_2와 r_2 사이의 숫자가 서로 같지 않게 출력하면 되는 문제이다.

 

def main():
    for _ in range(int(input())):
        l1, r1, l2, r2 = map(int,input().split())
        if l1 != l2: print(l1, l2)
        elif r1 != r2: print(r1, r2)
        else: print(l1, r2)

 

코드를 보면 l1과 l2의 값이 같지 않을 경우 l1과 l2의 값을 출력하고, l1과 l2의 값이 같은 경우 r1과 r2의 값이 다르면 r1과 r2의 값을 출력하고, 이마저도 같으면 l1 = l2, r1 = r2 이므로 l1과 r2의 값을 출력하였다.

 

 

 

 

B - Divisors of Two Integers

 

a의 약수와 b의 약수가 한 배열에 섞여 있으니 a와 b의 값을 구하라는 문제이다.

일단 배열을 오름차순으로 정렬시키면 가장 마지막에 있는 수는 약수이자 a와 b의 값중 값이 큰 수가 될 것이다.

이를 이용하여 배열에 max(a,b)의 약수를 전부 없애주면 남은 배열에서 가장 큰 수는 min(a,b)이므로 이 과정을 통해 min(a,b)와 max(a,b)를 출력하면 된다.

 

def main():
    n = int(input())
    D = sorted([*map(int,input().split())])
    Z = defaultdict(lambda: 0)
    for i in range(n):
        Z[D[i]]+=1
    for i in range(1,D[n-1]+1):
        if D[n-1]%i == 0: Z[i]-=1
    for x in sorted(Z.keys(),reverse=True):
        if Z[x] != 0:
            print(D[n-1],x)
            break

 

C - Nice Galand

각 색깔의 램프가 1번째 램프가 빨간색이면 4, 7, 10, 13,... 번째가 빨간 램프여야하고, 2번째 램프가 초록색이면 5, 8, 11, 14,.. 번째 램프의 색깔이 초록이여야한다. 그리고 나머지는 파란색 램프여야지 Nice하라고 말할 수 있다.

 

그래서 나는 주먹구구식으로 RGB, RBG, BRG, BGR, GRB, GBR 이렇게 6가지 방법을 전부 세어서 최소의 램프만 바꾸어서 nice로 만들 수 있는 방법을 출력하였다.

 

def main():
    n = int(input())
    s = input()
    RGB = [0,0,0]
    RBG = [0,0,0]
    BGR = [0,0,0]
    BRG = [0,0,0]
    GBR = [0,0,0]
    GRB = [0,0,0]
    x = 0
    while 1:
        if x == n: break
        if x % 3 == 0:
            if s[x] == 'R':RGB[0]+=1;RBG[0]+=1
            if s[x] == 'B':BGR[0]+=1;BRG[0]+=1
            if s[x] == 'G':GBR[0]+=1;GRB[0]+=1
        elif x % 3 == 1:
            if s[x] == 'R':BRG[1]+=1;GRB[1]+=1
            if s[x] == 'B':RBG[1]+=1;GBR[1]+=1
            if s[x] == 'G':RGB[1]+=1;BGR[1]+=1
        else:
            if s[x] == 'R':BGR[2]+=1;GBR[2]+=1
            if s[x] == 'B':RGB[2]+=1;GRB[2]+=1
            if s[x] == 'G':RBG[2]+=1;BRG[2]+=1
        x+=1
    ans = [float('inf'),'a']
    if n-sum(RGB) < ans[0]: ans = [n-sum(RGB),'RGB']
    if n-sum(RBG) < ans[0]: ans = [n-sum(RBG),'RBG']
    if n-sum(BGR) < ans[0]: ans = [n-sum(BGR),'BGR']
    if n-sum(BRG) < ans[0]: ans = [n-sum(BRG),'BRG']
    if n-sum(GBR) < ans[0]: ans = [n-sum(GBR),'GBR']
    if n-sum(GRB) < ans[0]: ans = [n-sum(GRB),'GRB']
    print(ans[0])
    for i in range(n):
        if i%3 == 0:print(ans[1][0],end='')
        if i%3 == 1:print(ans[1][1],end='')
        if i%3 == 2:print(ans[1][2],end='')

 

 

 

 

 

 

 

 

D - Diverse Garland

 

이번엔 R, G, B 램프를 색깔이 연속되지 않도록 만드는 문제이다.

일단 여기서 주의해야할점은 홀수개의 연속된 색깔의 램프가 있을 때, 홀수번째 램프의 색깔을 바꾸면 오답이 나올 수도 있다는 것이다.

만약 RRR이라는 램프가 나오면 두번째 R램프만 B로 바꾸어서 RBR로 만들면 되기 때문에 짝수번째 램프의 색깔을 바꿔야한다.

그리고 짝수개의 연속된 색깔의 램프가 있을 때는 홀수나 짝수번째의 램프 아무거나 바꿔도 상관없다.

RRRR이라는 램프가 있으면 두번째와 네번째 램프를 G로 바꿔서 RGRG로 바꾸나, 첫번째와 세번째 램프를 G로 바꾸어서 GRGR로 바꾸나 상관이 없기 때문이다.

그래서 짝수번째 램프로만 바꾸는 방법이 홀수개의 연속된 색깔이 있는 램프와 짝수개의 연속된 색깔이 있는 램프를 한번에 구할 수 있는 방법으로 짝수번째 램프로 바꾸는 방법을 선택하였다.

 

def main():
    n = int(input())
    s = input()
    val = 0
    ans = [s[0]]
    for i in range(1,n):
        if s[i] == ans[i-1]:
            val += 1
            if i != n-1:
                for x in ['R','G','B']:
                    if x not in [s[i+1],ans[i-1]]: #아래에 설명
                        ans.append(x)
                        break
            else:
                for x in ['R','G','B']:
                    if x != ans[i-1]: #아래에 설명
                        ans.append(x)
                        break
        else:
            ans.append(s[i])
    print(val)
    print(''.join(ans))

 

색깔을 파악할 때

                    if x not in [s[i+1],ans[i-1]]:
                    if x != ans[i-1]:

ans[i-1]과 s[i+1]에서 파악하는 이유는 색깔이 바뀌었을 수 있기 때문에 i-1번째에서 수정됐거나 그대로 넘어온 색깔 ans[i-1]과 다음 램프의 색깔 s[i+1]을 비교하는 것이다. 마지막 램프는 다음 램프가 없기 때문에 ans[i-1]의 색깔만 파악하면 된다.

 

 

 

 

 

E1 - Array and Segments (Easy version)

 

이 문제를 푸는 아이디어는 for문을 이용하여 i번째 값을 내릴 수 있는 쿼리들을 전부 적용하여 max(b) - min(b)를 구하면 답을 구할 수 있다.

i번째 값을 내릴 수 있는 모든 세그먼트를 찾는 방법은 미리 l, r의 범위를 받고 for문을 이용하여 세그먼트를 한개씩 불러와서 val[l]부터 val[r]까지 세그먼트 번호를 저장해둔다. 그러니까 예를 들어서 두번째 세그먼트의 값이 l = 0, r = 2이면 for문으로 리스트나 벡터를 이용해 val[0], val[1], val[2]에 2를 추가해주면 된다.

 

그리고 for문을 이용하여 i번째 값을 내릴 수 있는 쿼리들을 전부 적용하여 답을 구하면 된다.

n = 300, m = 300이라 주먹구구식으로 for문을 이용해 업데이트를 해도 O(n*m*n)이라서 전혀 문제가 없다.

 

def main():
    n,m=map(int,input().split())
    D = [*map(int,input().split())]
    seg = []
    for i in range(m):
        seg.append([*map(int,input().split())])
        seg[i][0]-=1
        seg[i][1]-=1
    if n == 1:print(0);print(0);print();exit()
    val = [[] for _ in range(n)]
    for i in range(m):
        x, y = seg[i]
        for j in range(x,y+1):
            val[j].append(i+1)
    ans = [-1,-1]
    for i in range(n):
        change = D+[]
        for j in val[i]:
            x, y = seg[j-1]
            for k in range(x,y+1):
                change[k]-=1
        a,b = max(change),min(change)
        if ans[1] < abs(a-b):
            ans = [i,abs(a-b)]
    print(ans[1])
    print(len(val[ans[0]]))
    print(*val[ans[0]])

 

 

 

E2 - Array and Segments (Hard version)

 

for i in range(n):
        change = D+[]
        for j in val[i]:
            x, y = seg[j-1]
            for k in range(x,y+1):
                change[k]-=1
        a,b = max(change),min(change)
        if ans[1] < abs(a-b):
            ans = [i,abs(a-b)]

E1에 있던 위 코드를 세그먼트 트리를 사용해서 O(log n)으로 업데이트하면 된다.

그러므로 O(n * m * log n)이라는 시간이 나와서 통과하게 된다.