Codeforces Round #544 (Div. 3) A~D,F1

codeforces.com/contest/1133

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

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

못 풀은 문제: D, E, F2

풀이만 보고 풀은 문제: D

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

 

난이도

A - 1000

B - 1200

C - 1200

D - 1500

E - 1800

F1 - 1600

F2 - 1900

 

 

D번은 쉬운 문제였는데 문제를 읽었으면서 같은 index끼리 비교한다는 내용을 까먹고 정수론으로 뭐 어떻게 하는줄 알아서 걸렀는데 다시 읽어볼걸 그랬다 ㅠㅠ

이것만 풀었어도 퍼포먼스가 1800점대가 나오는거라 아쉽다

 

E번은 dp인데 해설을 봐도 어떻게 푸는지 모르겠다.

 

 

 

 

 

A. Middle of the Contest

 

파이썬은 그냥 split(':')로 나눠서 풀어주면 된다.

'0'*(2-len(h))은 출력 시간이 02일 때, 코드에서의 h는 2만 표현되므로 02로 출력하게 만든다.

def main():
    a,b = map(int,input().split(':'))
    c,d = map(int,input().split(':'))
    z = ((a+c)*60+b+d)//2
    h = str(z//60)
    m = str(z%60)
    print('0'*(2-len(h))+h+':'+'0'*(2-len(m))+m)

 

 

 

 

 

B. Preparation for International Women's Day

 

선물을 2개만 합칠 수 있으므로 나머지가 0인 것에서 2개씩, 나머지가 1과 나머지가 n-1인 선물, 나머지가 2이고 나머지가 n-2인 선물... 이렇게 합쳐주면 된다.

나머지가 k이고 나머지가 n-k인 선물중 작은 수의 개수만큼만 합칠 수 있다.

만약 k가 짝수 일 경우 나머지가 k/2, k/2인 선물들도 합칠 수 있다는 것도 기억하고 있어야한다.

 

def main():
    n,k = map(int,input().split())
    d = [*map(int,input().split())]
    a = [0]*k
    for i in range(n):
        a[d[i]%k]+=1
    ans = (a[0]//2)*2
    if k%2 == 0:ans += (a[k//2]//2)*2
    for i in range(1,(k+1)//2):
        ans += min(a[i],a[k-i])*2
    print(ans)

 

 

 

 

 

C. Balanced Team

n명의 학생이 있고 팀을 한 개 만들 때, 팀에서 가장 낮은 프로그래밍 실력을 가진 학생과 팀에서 가장 높은 프로그래밍 실력을 가진 학생의 차이가 5까지만 차이나게 만들 수 있다고 한다.

그러면 팀에서 사람을 최대 몇 명을 넣을 수 있는지 구하는 문제이다.

 

투포인터 기본 문제이다.

def main():
    n = int(input())
    a = sorted([*map(int,input().split())])
    x,y = 0,0
    ans = 1
    while y < n:
        if a[x] <= a[y] <= a[x] + 5:
            y += 1
            ans = max(ans, y-x)
        else:
            x+=1
            if y < x: y=x
    print(ans)

 

 

 

 

D. Zero Quantity Maximization

d*a[i] + b[i] = 0인 값을 몇 개 만들 수 있는지 푸는 문제이다.

해싱을 해야하는데 파이썬은 그냥 str형으로 분수를 만들어서 dict에 넣어주면 된다.

(fraction모듈을 이용하면 기약분수가 아닌 값이 나올 때가 있어서 사용하면 안된다.)

 

d = - b[i] / a[i]이다.

d를 기약분수 형태로 저장해야하므로 a[i]와 b[i]의 최대공배수를 구하고 나눠주면 된다.

그리고 a[i]와 b[i]가 같은 부호라면 앞에 -를 붙이고, 아니라면 아무것도 안붙인다.

 

그리고 추가로 알아하는 경우는 a[i] = 0이고, b[i] = 0일 때 어떤 수를 넣어도 만족하기 때문에 따로 변수를 만들어서 계산해준다.

 

from math import gcd
def main():
    n = int(input())
    a = [*map(int,input().split())]
    b = [*map(int,input().split())]
    d = defaultdict(lambda: 0)
    zero = 0
    for i in range(n):
        if a[i] == 0:
            if b[i] == 0:zero += 1
            continue
        k = gcd(abs(a[i]),abs(b[i]))
        if (a[i] > 0 and b[i] > 0) or (a[i] < 0 and b[i] < 0):
            d['-' + str(abs(a[i]) // k) + '/' + str(abs(b[i]) // k)] += 1
        else:
            d[str(abs(a[i]) // k) + '/' + str(abs(b[i]) // k)] += 1
    ans = 0
    for x in d.keys():
        ans = max(ans,d[x])
    print(ans+zero)

 

 

 

 

 

 

 

 

F1. Spanning Tree with Maximum Degree

n개의 정점과 m개의 엣지가 주어질 때, n-1개의 엣지로 가장 많은 차수를 가진 연결그래프를 만들 수 있게 엣지를 출력하는 문제이다.

 

n-1개의 엣지로 만드는 연결그래프는 트리가 있으므로 트리를 구현하면 된다.

가장 많은 차수를 구하는 방법은 그냥 m개의 엣지를 입력받고 가장 많은 차수를 가진 정점중에 하나를 고르면 된다.

왜냐하면 입력값에서 중복되는 엣지가 안들어온다고 나와있으므로 만약 가장 큰 차수가 k라면 k+1개의 노드가 연결되어 있다는 뜻이므로 중첩되는 정점이 없으므로 가능하다. 

 

그래서 루트노드를 가장 많은 차수로 설정하고 큐를 이용하여 엣지들을 출력하면 된다.

 

from collections import deque
def main():
    n,m = map(int,input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        u,v = map(int,input().split());u-=1;v-=1
        adj[u].append(v)
        adj[v].append(u)
    max_degree = [-1,-1]
    for i in range(n):
        if len(adj[i]) > max_degree[0]:
            max_degree = [len(adj[i]),i]
    visit = [0]*n
    q=deque([max_degree[1]])
    visit[max_degree[1]] = 1
    while q:
        x = q.popleft()
        for nx in adj[x]:
            if not visit[nx]:
                q.append(nx)
                visit[nx] = 1
                print(x+1,nx+1)