Codeforces Round #635 (Div. 2) 후기 및 풀이 (A~D)

결과

망 했 다!

 

 

B까지는 A한번 실수로 틀린거 빼면 기분좋게 10분컷 냈는데, C 보자마자 머리가 하얘져버렸다..

대략 1시간정도 C 잡고 있다가 때려치고 hack이나 하러 갔었는데, 조금만 더 했으면 C,D 둘다 풀 수 있었을텐데 하는 아쉬움이 남아 있다.

 

다음 Div3 대회가 곧 있으니까 그거 하려고 일부러 블루 안간거임 ㅎㅎ 아무튼 그런거임 ㅠㅠ

 

 

 

아무튼 간단하게 풀이나 해보겠다.

 

 

https://codeforces.com/contest/1337/problem/A

Problem - A - Codeforces

A. Ichihime and Triangle

 

a,b,c,d를 입력받고, a<=x<=b<=y<=c<=z<=d를 만족하고 각각 x,y,z를 변의 길이로 하는 삼각형이 존재하도록 x,y,z를 출력하는 문제였다.

 

이 문제는 사실 삼각형의 존재 조건(중학수학)만 알면 쉽게 풀린다.

가장 긴 변의 길이가 다른 두 변의 길이보다 작아야 한다는 조건 말이다.

그런데, 이걸 어떻게 x,y,z에 적용할까?

 

물론 여러 가지 방법이 있을 수 있지만, 가장 확실하고 적절한 방법은 가장 긴 변을 두개를 만드는 것이다.

가장 긴 변의 개수가 두개라면 무조건 삼각형이 만들어지기 때문이다. (1, 100, 100으로도 삼각형이 만들어진다.)

 

그러면 이제 문제풀이는 끝났다. y<=c<=z이므로, y==z==c로 놓는다면 x는 a<=x<=b를 만족하는 어떤 수를 고르더라도 x,y,z로 무조건 삼각형이 만들어진다.

즉, 간단하게 a,c,c 또는 b,c,c를 출력하면 정답이다.

 

 

 

 

https://codeforces.com/contest/1337/problem/B

Problem - B - Codeforces

B. Kana and Dragon Quest game

 

 

적 몬스터의 체력 h가 주어지고, Void Absorption 스킬의 사용횟수 n, Lightning Strike 스킬의 사용횟수 m이 주어진다.

이 때, 최대 n,m번 스킬을 사용하여 적 몬스터를 죽일 수 있는지 (h<=0으로 만들 수 있는지) 여부를 출력하는 문제이다.

 

Void Absorption 스킬은 적 체력을 반으로 깎고, 10을 회복시켜준다. (h = h/2 + 10)

Lightning Strike 스킬은 적 체력을 10만큼 깎는다. (h = h - 10)

 

 

우선, 어떤 순서로 스킬을 사용해야 최적의 스킬 사용일지를 생각해 보아야 한다.

체력을 반으로 줄이는 것은 상대방의 체력이 높을수록 효과적이므로, 적의 체력을 반으로 줄이는 것은 최대한 먼저 실행해야 한다.

 

두 번째로 생각할 점은, Void Absorption 스킬은 적의 체력을 회복시켜 줄 수도 있다는 것이다.

그렇다면 어떤 경우에 Void Absorption 스킬로 적 체력이 회복될까?

간단한 식으로 보자면, h < h/2 + 10, h/2 < 10, h < 20 즉 체력이 20 미만인 경우 Void Absorption 스킬을 사용하게 되면 적의 체력을 회복시킬 수도 있다는 것이다.

 

그리고 결국 적의 체력을 최대한 줄이는 것이 중요하므로, 적의 체력을 회복시키는 것은 결코 최적의 움직임이 될 수 없으므로, h<20인 경우에는 Void Absorption 스킬을 사용하면 안된다.

 

정리하자면, h>20인 경우에는 Void Absorption 스킬을 최대한 많이 사용하고, 그 뒤에 Lightning Strike 스킬을 최대한 많이 사용해 주면 된다.

 

 

코드로 나타낼 때는, 다음과 같이 나타내면 된다.

while (h>20 && n>0) h = h/2 + 10, n--;

if (h - m*10 <=0) printf("YES");

else printf("NO");

 

 

여담으로, 이 문제를 hack을 해보려고 여러 코드를 살펴봤는데, 문제가 워낙에 간단해서 hack을 하기가 힘들었다.

실제로, "먼저 n번 나누고 그 후에 m번 뺀 값"과 "먼저 m번 뺀 값" 중 하나만 0 이하이면 정답이라는 코드도 pass하게 되니..

 

https://codeforces.com/contest/1337/problem/C

Problem - C - Codeforces

 

C. Linova and Kingdom

 

위 결과에서 보면 알겠지만, 대회 시간 안에 못풀었다.. ㅠㅠ

풀만했던 문제였는데 트리를 다루는게 아직 미숙해서 못푼 것 같다. 앞으로 좀 더 연습해야겠다 

 

 

 

아무튼 풀이를 해 보도록 하겠다. (대회 끝나고 바로 다음날 일어나서 풀었다)

 

간단하게만 문제 설명을 해 보자면,

n개의 도시와 n-1개의 도로가 주어지고, 모든 "산업 도시"에서 수도로 사람이 올 때, 각각의 사람이 지나가는 "관광 도시"의 개수의 합의 최대값을 구해야 한다.

 

이 때, 산업 도시는 k개이고 나머지 모든 도시 (즉, n-k개의 도시)는 관광 도시이다.

 

 

사실 풀이는 설명만 들어보면 무척 간단하다.

 

일단, 1번 도시가 최종 목적지이므로 1번 노드가 루트인 트리를 만들어 준다.

(1번째 input 예)

일단 처음엔 간단하게, 단 하나의 산업 도시만을 고른다고 생각해 보자.

그럴 경우, 어떤 도시를 산업 도시로 골라야 할까?

그렇다. 1번 도시로 가는 길이 가장 긴 도시를 고르면 된다.

즉, 부모 노드의 개수가 가장 많은 노드들을 고르면 된다는 뜻이다.

위 예시에서는, 5, 6, 7중 하나만 고르면 될 것이다.

그리고 그렇게 산업 도시를 3개까지 고르면 5, 6, 7을 고르면 될 것이다.

 

그러나 4번째 산업 도시를 고를 때, 고려해야 하는 것이 하나 더 있다는 것을 알게 된다.

만약 3번 도시를 고르게 되면, 이미 골랐던 5번, 6번 도시에서 1번 도시로 가는 데 만나는 관광 도시의 개수가 하나 줄어들어 버리기 때문이다.

그리고, 어떤 노드를 고르게 되면 최대로 얻을 수 있는 점수는 해당 노드의 자식 수 만큼 줄어들게 된다.

(즉, 3번 노드를 고르게 되면 자식 노드의 개수인 2만큼 최대 점수가 줄어들게 된다.)

반면에 2번 도시를 산업 도시로 고르게 되면, 2번 노드는 자식 노드가 없으므로, 가장 최적의 상태가 완성된다.

 

또한, 어떤 노드의 자식 노드가 산업 도시가 아니라면, 해당 노드를 고르는 대신 무조건 자식 노드를 골라야 최적의 점수를 얻을 수 있다.

(조금 더 쉽게 말하면, 우리는 무조건 산업 도시를 리프 노드 근처부터 시작해서 천천히 루트 노드에 가까운 쪽으로 골라야 한다는 것이다.)

이는 자명한데, 만약 어떤 산업 도시의 자식 노드가 관광 도시라면, 해당 도시의 자식 노드를 산업 노드로 만들면 1점 더 높은 점수를 얻을 수 있기 때문이다.

 

따라서, 우리는 그리디하게 (부모 노드 개수 - 자식 노드 개수) 가 가장 큰 도시부터 하나씩 골라가면 된다.

 

 

이제 어떻게 해야할지는 알았으니, 이를 구현하면 된다.

우선, DFS를 사용하여 각각 노드의 부모 노드 개수와 자식 노드 개수를 구한다.

그런 뒤, (부모 노드 개수 - 자식 노드 개수)를 한 배열을 내림차순으로 정렬하여 앞에서부터 k개를 더하면, 그게 정답이다.

 

 

//여기서부턴 여담임 ㅎ

사실 대회 시간에 풀 때, 여러 문제점들이 있었다.

우선, 가장 처음 생각한 풀이는 그냥 부모 노드의 개수만을 생각한 풀이였다.

사실 그래서 그냥 나한테 조금 더 익숙한 BFS 방식으로 훑으면서 부모 개수를 채웠다.

그러고 나서 봤더니, 자식 노드에도 신경을 써야한다는 사실을 그제서야 깨닫게 되었고, 뇌절이 시작되었다;;

 

일단 "그리디하게 짜면 안되지 않을까?" 라는 생각으로 고민을 엄청 했었다.

그리고, "우선 리프 노드를 고른 뒤 해당 노드의 모든 부모 노드를 돌면서 점수를 1씩 깎자"라는 매우 비효율적인 생각을 하게 되었고,

당연히 n<=100000인 조건 안에서는 TLE가 뜰 것이 분명했기에, 문제를 던지기에 이르렀다.

 

차라리 그냥 처음부터 DFS로 짰으면 더 쉽게 풀었을 것도 같은데, 아쉽다.. ㅠ

 

 

https://codeforces.com/contest/1337/problem/D

Problem - D - Codeforces

D. Xenia and Colorful Gems

 

솔직히, 얘가 C보다 훨씬 쉬웠던 것 같다.

 

사실 대회 시간엔 얘를 볼 생각을 딱히 못했는데, 대회 다음날 금방 답이 나와서 허탈했다...

다음부터 뇌절오면 그냥 다음 문제로 거르는 습관을 들여야 되는건가? 싶기도 하다..

아무튼! 풀이나 하도록 하자.

 

 

우선 red, green, blue 각각의 색깔의 보석의 개수 nr, ng, nb가 주어진다.

그리고 나서, 각각의 보석의 크기가 순서대로 nr, ng, nb개씩 주어진다.

각 색의 보석을 하나씩 고른 것을 순서대로 x, y, z라고 할 때, (x-y)² + (y-z)² + (z-x)²의 최소값을 구하는 문제이다.

(아래에서는 편의상 그냥 위 연산을 '거리'라고 하도록 하겠다.)

 

 

일단 r, g, b 배열을 오름차순으로 정렬을 해 놓고, ans를 r[0], g[0], b[0]의 거리로 놓는다.

그 뒤 r[1], g[0], b[0]의 거리, r[0], g[1], b[0]의 거리, r[0], g[0], b[1]의 거리 중 가장 작은 놈을 찾고, ans를 ans와 해당 값중 작은 값으로 바꿔주고, 가장 작았던 색의 index값을 1 올려서 위를 반복한다.

즉, 가장 거리가 작은 경우를 그리디하게 하나씩 골라주면서 진행하는 것이다.

 

말이 좀 어려운데, 그냥 대충 예시를 하나 들어서 설명을 하는게 나을 것 같다.

 

입력은 input case 1의 예시와 동일한,

2 2 3

7 8

6 3

3 1 4

로 하도록 하겠다.

 

우선 각각을 오름차순 정렬을 해 준다.

r : 7 8

g : 3 6

b : 1 3 4

 

그 뒤, ans = (7-3)^2 + (3-1)^2 + (1-7)^2 = 16 + 4 + 36 = 56으로 설정해 두자.

 

r[1], g[0], b[0] : (8-3)^2 + (3-1)^2 + (1-8)^2 = 25 + 4 + 49 = 78

r[0], g[1], b[0] : (7-6)^2 + (6-1)^2 + (1-7)^2 = 1 + 25 + 36 = 62

r[0], g[0], b[1] : (7-3)^2 + (3-3)^2 + (3-7)^2 = 16 + 0 + 16 = 32

 

그러므로, ans = min(ans, 32) = 32가 되고, b의 index를 1 올려준다.

 

다음 단계로 넘어가 보면,

r[1], g[0], b[1] : ...

r[0], g[1], b[1] : ...

r[0], g[0], b[2] : ...

 

이런 식으로 계속 진행하다 보면, 결국 nr+ng+nb번 반복 후에는 끝나게 된다.

그리고, 그렇게 나온 ans의 값이 최적의 해가 된다.

 

 

그런데, 어째서 이렇게 하면 정답이 도출될까? 저 알고리즘의 반례가 없을까?

오랜만에 그림판을 켜서 그림을 그려서 설명해 보도록 하겠다.

 

퍼펙트한 손그림 ㅋㅋㅋ

보석의 크기를 위치로 변환해서 그린 수직선이다.

위 그림을 보면 어느 정도 직관적으로 이해가 되지 않는가?

 

약간의 부연설명을 해 보도록 하겠다.
우리의 목적은, 저 중에서 각각의 색의 점 하나씩을 골라 가장 거리가 가까운 조합을 찾아야 하는 것이다.

알고리즘을 진행시키다 보면, 조금씩 더 점들이 밀집하게 된다.

그리고 임계점을 넘어가게 되면, 즉 더 이상 현재까지 구한 최적해보다 최적의 값을 찾을 수 없다면, ans값은 다시 조금 커진다.

그리고 나서 다시 ans를 최적에 맞게 줄이고, 어느 순간 또 커지고 ... 를 반복하게 된다는 것이다.

따라서, 위 방식으로  그리디하게 수행해 나가면, 최적해를 찾을 수 있게 된다.

 

 

하지만 직관을 도저히 믿을 수 없다면, 조금 엄밀하게 증명을 해 보도록 하겠다.

 

최적해가 위 알고리즘을 통해 나오지 않기 위해서는, 아래 두 조건을 만족하는 r,g,b가 존재해야 한다.

1) b[x],g[y+1],r[z]의 거리가 b[x],g[y],r[z]의 거리, b[x+1],g[y],r[z]의 거리, b[x], g[y], r[z+1]의 거리보다 더 작다.

2) b[x+1], g[y], r[z+1]의 거리가 b[x+1], g[y+1], r[z+1]의 거리보다 작다. (즉, g가 더 작은 값에서 더 최적의 값이 존재한다.)

 

이런 경우가 존재한다면, 그리디하게 선택했을 경우 최적해를 보장할 수 없다.

하지만, 이런 경우가 과연 존재할까?

 

2)번 조건이 만족하기 위해선, 1)에 의하여 b[x+1], g[y], r[z+1]의 거리는 무조건 b[x+1],g[y],r[z]의 거리보다 작아야 한다.

    (b[x+1], g[y], r[z+1]의 거리 < b[x],g[y+1],r[z]의 거리 < b[x+1],g[y],r[z]의 거리)

그리고, r[z+1]은 r[z]보다 무조건 크기 때문에, r[z]는 b[x], g[y], r[z] 중 가장 큰 수는 아니어야만 한다.

 

또한, b[x+1], g[y], r[z+1]의 거리는 b[x], g[y], r[z+1]의 거리보다도 작아야 한다.

마찬가지로, b[x+1]은 b[x]보다 무조건 크기 때문에, b[x]는 b[x], g[y], r[z]중 가장 큰 수는 아니어야 한다.

 

따라서, g[y]가 b[x], g[y], r[z] 중 가장 큰 수가 되어야 한다.

 

그런데, 이는 1) 조건인 "b[x],g[y+1],r[z]의 거리가 b[x],g[y],r[z]의 거리보다 작아야 한다"에 위배된다.

 

따라서, 위 조건을 만족하는 r,g,b의 값은 존재하지 않고, 따라서 최적해는 위 알고리즘을 통해 항상 구할 수 있다.

 

 

 

사실 이걸 이렇게까지 엄밀하게 증명하고 풀었던 것은 아니라, 증명하는데 꽤 애먹은 것 같다 ㅎㅎ;

이렇게 했는데도 아직 좀 꺼림칙하다면, 에디토리얼의 풀이를 보기를 권한다.

사실 본질적으로 동일한 풀이이긴 하지만, 이해하기는 더 도움이 될 것이다.

 

 

 

 

이렇게 Codeforces Round #635 (Div. 2)의 A~D풀이를 끝내도록 하겠다.

E,F는 언젠가 실력이 되면 그때나 풀어보도록 하고 ㅎㅎ...

다음 Div3에서 꼭 블루 갔으면 좋겠다. 위 C 문제 덕에 DFS, 트리 공부도 더 할 수 있게 되기도 했고 말이다.