Codeforces Round #405 (rated, Div. 2, based on VK Cup 2017 Round 1)

A. Bear and Big Brother

문제

Limak 와 Bob의 몸무게가 주어진다. Limak는 매년 3배씩 커지고 Bob은 2배씩 커진다. Limak가 Bob보다 커지기 위해서는 최소 몇 년이 지나야 하는지 구하는 문제이다.

문제 풀이

단순하게 1년 씩 늘리면서 2와 3을 각각 곱하고, Limak가 커질 때 출력하면 된다.

 

소스 코드

B. Bear and Friendship Condition

문제

친구 관계가 그래프로 주어진다. 한 컴포넌트내의 모든 정점이 서로 연결되어 있는지(완전 그래프)인지 판별하는 문제이다.

문제 풀이

각 정점마다 연결된 간선이 해당 정점이 포함된 컴포넌트 크기 - 1 인지 확인한다. 

 

소스 코드

C. Bear and Different Names

문제

N명의 군인이 있고, K명의 연속된 군인으로 이루어진 그룹이 N-K+1개 있을 때 해당 그룹에 어떤 이름이 2번 이상 존재하면 효과적이지 않은 그룹이다.(NO) 그룹 내에 모든 이름이 서로 다르다면 효과적인 그룹이다.(YES) 이러한 입력이 주어 졌을 때 가능한 군인들의 이름을 출력하는 문제이다. 

문제 풀이

먼저 최대로 YES가 들어올 때 사용할 50개의 이름들을 만들어 놓는다. 그 후 NO가 들어오는 경우에 어떤 이름끼리 중복이 되야 이후 또는 이전에 나온 YES나 NO에 영향을 주지 않을까? 하고 생각을 해보면, 맨 앞 그룹의 이름과 맨 뒤 그룹의 이름만 같다면 한 칸 뒤 그룹이나 한 칸 앞 그룹은 현재 만들어진 이름과 상관없이 이어 나갈수 있음을 알 수 있다. 따라서 먼저 K-1개의 이름을 만들고 YES가 나온다면 새로운 이름을 NO가 나온다면 현재 그룹의 가장 앞의 이름과 같은 이름을 할당하면 된다. 

 

소스 코드

D. Bear and Tree Jumps

문제

N개의 정점을 가진 트리가 있고 Limak는 최대 K만큼의 간선을 점프해서 이동 할 수 있다. 그때 모든 정점간의 점프수의 합을 구하는 문제이다.

문제 풀이

먼저 1번 정점을 루트로 하는 트리의 K=1 인 경우의 풀이를 생각해 보자. 1번 정점과 다른 모든 정점간의 점프수의 합은 0부터 시작하는 depth에 해당 하는 정점들의 수를 카운트해서 세고 더해주는 방식으로 쉽게 구할수 있다. 다음 \(cnt[i] = i를\:루트로\:하는\:서브트리의\:정점\:수\) 라고 정의 하였을 때 1번 정점에서 자식 정점인 there로 이동 한다고 하면 there정점을 루트로하는 서브트리의 정점들은 1번 정점으로 이동하는 것보다. 점프수가 1감소하고, 나머지 정점들은 1만큼 증가하게 된다. 따라서 dfs 과정에서 \(length[there]=length[1]-cnt[there]+(n-cnt[there]\) 과정을 반복하면서 모든 정점들의 정점간 점프수의 합을 구할 수 있다. K가 1이 아닌경우 에는 cnt 배열에 추가적으로 mod값을 저장해주고, \(parcnt[i][j]=i번\: 정점\: 부모\: 쪽으로 \:이동\: 수의\: mod\: k값이\: j인\: 정점들의\: 수\)라고 정의한 배열도 추가적으로 계산해 주면서 \(length[there]=length[now]-cnt[there][0]+(cnt[now][0]-cnt[there][k-1]+parcnt[0])\)값을 계산구하면 된다. 

 

소스 코드

E. Bear and Company

문제

N개의 길이를 가진 알파벳 대문자로 이루어진 문자열에서 이웃한 두 문자를 스왑할 수 있을 때 VK문자를 모두 없애는데 드는 최소 스왑 횟수를 구하는 문제이다.

문제 풀이

일단 V와 K를 제외한 모든 문자를 X로 생각하고 V,K,X들이 나타나는 위치들을 순서 대로 저장한 다음 i번 위치의 문자를 채워 넣을 때 3개중에 무엇을 사용할 지 결정하는 문제로 바꿔 생각한다. \(dp[i][v][k][x][type] = i번\: 째\: 위치의\: 문자을\: 결정하고자\: 할\: 때\: v,k,x번\: 째\: 문자\: 까지는 \:사용하였고,\: 이전\: 문자의\: 형태가\: type일\: 때\: 스왑\: 횟수의\: 최소값\) 이라고 정의 한다. 예를들어 이번에 v번째 V를 넣고자 한다면 이전 문자의 type는 상관이 없고 V[v]보다 작고 v보다 큰 V의 갯수 만큼, V[v]보다 작고 k보다 큰 K의 갯수 만큼, V[v]보다 작고 x보다 큰 X의 갯수 만큼 i와 v사이에 문자들이 남아있는 것이고 그만큼 더해주면서 최소값을 계산해주면 된다.

 

소스 코드