Codeforces Round #541 (Div. 2) A, B, C, F

codeforces.com/contest/1131

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

 

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

못 풀은 문제: D, E, G

풀이만 보고 풀은 문제:

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

 

난이도

A - 800

B - 1400

C - 1200

D - 2000

E - 2300

F - 1700

G - 2700

 

 

 

F번은 유니온파인드인데 파이썬은 재귀로 풀면 메모리가 터져서 C++로 고쳐서 제출하느라 시간이 좀 걸렸다.

문제 아이디어는 바로 구했어서 더 높은 등수가 가능했는데 아쉬웠다.

 

 

Codeforces Anytime에서 블루까지 단 9점 남았다.

 

 

 

 

 

 

 

A. Sea Battle

 

첫번째 배의 왼쪽 아래는 (1,1)이고, 오른쪽 위는 (w1,h1)

두번째 배의 왼쪽 아래는 (1, h1+1)이고, 오른쪽 위는 (w2, h1+h2)

이므로 그림을 그려보면

 

이렇게 나온다.

빨간점 5개와 h1 * 2 + w1 + h2 * 2 + w2 + (w1 - w2) - 1을 더해주면 된다.

왜 끝에 -1이 붙냐면 h2와 (w1-w2)에 겹치는 부분이 한 칸 있어서 그렇다.

 

def main():
    h1,w1,h2,w2 = map(int,input().split())
    ans = 2*h1 + w1 + 2*h2 + w2 + (w1 - w2) + 4
    print(ans)

 

 

 

 

 

 

B. Draw!

 

경기의 기록 일부분이 남아있을 때, 경기중 동점 상황이 최대 몇 번 나올 수 있는지 구하는 문제이다.

 

예제2번처럼 같은 값이 여러번 나올 수 있으니 visit이라는 defaultdict를 만들어서 같은 값은 한 번만 계산하게 만들어준다.

 

풀이방법은

이전 기록에 나왔던 점수인 last_x와 last_y, 현재 보고 있는 기록인 x와 y를 이용하여

z = min(x,y) - max(last_x, last_y) + 1로 가능한 동점 횟수를 구한다. 그리고 이전기록이 동점이였으면 1을 빼준다.

 

이런 공식이 왜 나오냐면 현재 동점 기록이 가능한 방법은 x와 y중에서 작은 값만큼만 동점이 나올 수 있고, 이전 경기에서는 last_x와 last_y중 높은 값의 기록부터 동점이 나올 수 있기 때문이다.

그런데 last_x와 last_y가 같을 경우, 이미 이전에 계산을 해주었기 때문에 1을 빼줘야한다.

 

이걸 계속 ans에 더해주면 된다.

 

def main():
    D = [[*map(int,input().split())] for _ in range(int(input()))]
    visit = defaultdict(lambda:0)
    ans = 0
    last_x, last_y = 0,-1
    for i in range(len(D)):
        x, y = D[i]
        if min(x,y) >= max(last_x,last_y) and not visit[str(x)+'-'+str(y)]:
            z = min(x,y) - max(last_x,last_y) + 1
            if last_x == last_y: z-=1
            ans+=z
        visit[str(x)+'-'+str(y)] = 1
        last_x, last_y = x, y
    print(ans)

 

 

 

 

C. Birthday

 

이건 정렬하고 index 홀수값, 짝수값을 따로따로 나눠 리스트에 저장해준다음 홀수 리스트 + 뒤집은 짝수 리스트로 출력하면 된다.

왜냐하면 a[i]와 a[i+1]의 차이의 최댓값이 최소값이 되어야하는데, 학생들이 원을 그리기 때문에 첫번째 학생과 마지막 학생의 키 차이도 고려해야한다.

그러므로 정렬을 하면 a[i]와 a[i+1]의 값이 매순간 최소이지만, a[0]와 a[n-1]의 값도 최소여야하기 때문에 정렬된 상태에서 홀수 인덱스와 짝수 인덱스를 나누어서 저장하고, 홀수 + 뒤집은 짝수로 출력하면 된다. 혹은 짝수 + 뒤집은 홀수로 출력해도 상관없다.

 

def main():
    n = int(input())
    a = sorted([*map(int,input().split())])
    team1 = []
    team2 = []
    for i in range(0,n,2):
        team1.append(a[i])
    for i in range(1,n,2):
        team2.append(a[i])
    print(*(team1+team2[::-1]))

 

 

 

 

 

F. Asya and Kittens

 

예제 그림이 대놓고 유니온파인드라고 홍보하고 있고, 입력값도 인접할때만 주어진다고 나와있다.

 

그럼 이제 어떻게 출력하는지가 문제인데, 그림 예제를 가지고 아무렇게나 입력값 순서대로 한 숫자의 왼쪽이나 오른쪽에 나머지 숫자를 붙이고, 그러다가 겹치는 방향이 있을 때, 한 숫자의 방향을 뒤집어서 붙이다보면 어느방향으로 붙여도 상관없다는 것을 알 수 있다.

그럼 아무렇게나 붙여도 상관없으므로 그냥 유니온파인드를 이용하여 x, y라는 입력값이 주어지면 x의 부모노드와 y의 부모노드를 각각 nx, ny로 구하고 p[ny] = p[nx]로 바꿔준다음 cage[nx]에 ny라는 값을 저장해둔다. 그다음 재귀를 이용하여 출력해주면 된다.

 

이건 왼쪽에서 오른쪽으로 붙여주는 트리라고 생각해주면 편하다

만약 입력값이

0 1

0 2

3 4

이면 그림이 아래와 같이 나올 것이다.

그런다음 2 4를 입력값에 넣으면 2에 속하는 트리에 3과 4를 붙여주는 것이므로

2가 속한 트리의 루트노드인 0과, 4가 속한 트리의 루트노드인 3을 서로 합쳐주면 된다.

 

또 루트노드인 0에 속하는 트리의 숫자와 다른 숫자가 나온다면 3의 오른쪽에 붙여주면 된다.

 

그리고 아래 코드에 나온 go를 출력하면

0 1 2 3 4가 나오는데 직접 예제처럼 구해보면 해당되는 순서이기 때문에 답이 나온다.

 

1. C++(통과)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 150001

vector<vector<int>> cage;
int p[MAX] = {0,};
vector<int> ans;

int find(int u){
    if (u==p[u]) return u;
    return p[u] = find(p[u]);
}

void merge(int x, int y){
    x = find(x);
    y = find(y);
    p[y] = x;
}

void go(int x){
    ans.push_back(x);
    for(int i=0; i<cage[x].size(); i++)
        go(cage[x][i]);
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	for(int i=0; i<=n; i++){
	    vector<int> x;
	    cage.push_back(x);
	}
	for(int i=0; i<=n; i++) p[i] = i;
	for(int i=0; i<n-1; i++){
	    int x,y,nx,ny;
	    cin >> x >> y;
	    nx = find(x);
	    ny = find(y);
	    if(nx != ny){
	        merge(nx,ny);
	        cage[nx].push_back(ny);
	    }
	}

	go(find(1));

	for(int i=0; i<ans.size(); i++){
	    cout << ans[i] << " ";
	}

	return 0;
}

 

2. Python3(통과는 못하지만 1번과 똑같은 코드)

def main():
    def find(t):
        if (p[t] == t): return t
        p[t] = find(p[t])
        return p[t]
    def merge(x, y):
        x, y = find(x), find(y)
        p[y] = x
    def go(x):
        ans.append(x)
        for nx in cage[x]:
            go(nx)
    n = int(input())
    p = [i for i in range(n+1)]
    cage = [[] for i in range(n+1)]
    for i in range(n-1):
        x,y = map(int,input().split())
        nx,ny = find(x),find(y)
        if nx != ny:
            merge(nx,ny)
            cage[nx].append(ny)
    ans = []
    go(find(x))
    print(*ans)