Codeforces Round #781 (Div. 2)

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

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

간만에 적어본다.

앞으로 가급적이면 꾸준히 적어보려고 한다.

 

A. GCD vs LCM

최대공약수와 최소공배수와 관련된 문제이다.

문제에 적혀있는 그대로, 숫자 N이 하나 주어졌을 때, a + b + c + d = N 을 만족하면서 GCD(a,b) = LCM(c,d) 를 만족하는 숫자 a,b,c,d를 찾으면 된다.

 

아마 눈치챘겠지만, 코포 A번 특성이 발견된다.

조건을 만족하는 경우가 여러 개 있는 경우, 쉽게 해결 할 수 있는 경우 하나만 출력해주면 된다.

이 문제의 경우 1,1,1, N-3 을 하면 문제의 조건을 GCD와 LCM이 항상 1이 되어서 조건을 무조건 만족한다.

나는 눈치는 챘지만 약간 헤매다가 +8분에 풀어서 제출했다.

 

B. Array Cloning Technique

우리는 처음에 주어지는 하나의 array로부터 array의 모든 원소가 같은 숫자인 array를 만들어야 하며,

매 턴 마다, 다음 두 가지 작업 중 하나를 할 수 있다.1. 기존에 잇던 array를 복제한다.2. 두 array 간의 원소들을 swap한다. 위치나 갯수는 마음대로 할 수 있다.

 

당연하지만, 처음 주어지는 array에서 가장 많이 존재하는 원소를 타겟으로 삼아야 한다는 것을 알 수 있다.그리고 그 array를 복제를 해서 그 원소를 가져오는 식으로 진행된다.처음에 주어지는 array에서 가장 많이 존재하는 숫자의 갯수가 k개 라고 하면,1. 복제2. swap을 한번 마치면 타겟 숫자가 2k개 존재하고한 사이클 더 진행하면 4k개 존재한다.

2의 제곱 꼴로 채워 나가면서 array 를 채워 나가며 operation 횟수를 세면 된다.

 

이제보니 쉬운 문제 같은데 생각보다 오래 걸렸다.

+27분에 제출했다.

초기 array에서 가장 많이 등장하는 숫자를 찾는데는 map을 사용했으며, value 값의 최대치를 알기 위해 그냥 map을 for loop 돌면서 찾았는데, 이런 고인물 방법을 쓰는 사람도 있었다.

int ma = max_element(m.begin(), m.end(), [](const auto& i, const auto& j) {
        return i.second < j.second;
    })->second;

이게 되네;;

아주 고인물 지식까지는 아니니까 map 같은 것을 사용할 때 유용하게 사용하자.

 

C. Tree Infection

말 그대로 트리를 감염시키는 문제이다.

트리는 감염이 하나도 되지 않은 상태에서 시작하며, 우리는 한 턴마다 노드 하나를 직접 감염시킬 수 있다.

트리는 자식 중 하나라도 감염된 경우 알아서 매 턴마다 다른 자식 하나로 감염을 전파시킨다.

 

상식적으로 트리의 sibling(자매) 이 가장 많은 노드부터 감염시키는 것이 이득이다.한번 뿌려두면 알아서 감염시켜주기 때문.root 노드는 sibling이 없기 때문에 우리가 직접 감염시켜 주어야 하는데, 형제자매가 하나도 없으므로, 맨 마지막에 감염시켜준다.

 

하지만 하나 주의해야 하는 점은, 이렇게 감염을 다 마쳤더라도 아직 감염의 전파가 진행중이라면!?나는 한 턴에 하나씩 감염시킬 수 있으므로, 굳이 놀고 먹으면서 감염의 전파를 기다릴 이유는 없다. (물론 기다려도 전부 감염이 되기는 된다.)여기서부터는 시뮬레이션의 영역이다.노드 갯수가 그렇게 많지 않으므로 하나씩 시뮬레이션이 가능하다.

시뮬레이션을 하면서 가장 slibing이 많이 남아있는 노드에 직접 감염을 시켜주면 된다.

나는 vector로 남아있는 slibing의 숫자를 관리하면서 매 턴마다, vector를 돌면서 자동감염을 시켜주고, sort후의 vector.back()을 직접 감염시켜주는 식으로 진행했다.

 

집중이 안됐는지 헤메다가 4회 제출 후 시간이 끝나버렸다.

나중에 확인해보니 if 문에서 등호 조건을 지웠어야 했다...

vector를 sort하고 vector의 뒷쪽에서만 loop가 돈다는 점에서 시간 복잡도가 쓸데없이 커질까봐 걱정이 많았는데, 생각해보니 그냥 rbegin, rend를 사용하면 되는 것이었다. 아니면 음수를 사용하던가...

 

이하 D, E 번은 읽지도 못했으므로 패스한다...

풀이가 궁금하다면 editoral을 살펴보자..

Codeforces Round #781 (Div. 2) Editorial - Codeforces

Codeforces Round #781 (Div. 2) Editorial - Codeforces