Codeforces Round #670 (Div. 2 only)

이번에는 38등을 했다. 한동안 only div2 밖에 없어서 2099에 최대한 근접시키고 한번에 쭉 올라가려고 했는데, 뭔가 이번이 기회인것 같아서 그냥 쭉 올려버렸다. 사실 좀 더 잘했을 수 있었을 것 같은데 비장의 한 방 치고는 조금 아쉬웠던 것 같기도 하다. 사실 한번 2등을 했어서 이제는 성에 안차는 것 같기도...

A . Subset Mex

두 개의 그룹으로 나누고 두 그룹에 대한 각각의 Mex 값의 합을 최대화 시켜야 한다. 0부터 보면서 2번 이상 나왔으면 양쪽 모두에 넣을 수 있으며, 1번만 나왔으면, 한쪽 그룹에는 넣을 수 없고, 한 번도 나오지 않으면 양쪽 모두 넣을 수 없다. 따라서 우리가 구하고자 하는 값은 1번 이하로 등장한 가장 작은 수 + 0번 이하로 등장한 가장 작은 수 이다. 

그냥 뚝딱하면 풀 수 있는 문제. 해석도 관찰도 어렵지 않았다. 10초만 빨랐어도 2분일텐데... 00:03

B . Maximum Product

5개의 숫자를 곱해서 가장 크게 만들면 된다. 맨처음에 보고 양수와 음수를 나눠서 보관하려다 0은 또 어떻게 처리해야할 지 몰라서 잠깐 어리바리 했다. 그런데 생각해보니까 그냥 싹다 넣고 정렬해서 음수는 0,2,4 개 이려고 노력할테니까 최종 답은 정렬한 배열에서 (1,2,3,4,n)번째 수의 곱, (1,2,n-2,n-1,n)번째 수의 곱, (n-4,n-3,n-2,n-1,n)번째 수의 곱이 될 수 밖에 없다.

일단 C를 먼저 풀려고 C번 문제를 먼저 읽고 잠깐 고민을 했었다. 그러다가 B로 와서 잡았는데, 아이디어는 빠르게 생각을 했지만, 배열 크기 구현 미스, 3번째 경우를 고려 안한 미스. 두 번의 실수를 하면서 2틀로 굉장히 안좋은 자리를 선점하였다. 이는 이후에 빡세게 스노우볼이 굴러가게 된다. 결과는 9분이 걸렸다 00:12

C . Link Cut Centroids

ㅏㅏㅏㅏㅏㅏ 글을 쓰던 것이 날라갔다. 이 아래로는 좀 글이 부실해질 수 있다.

1. 나는 Centroid 를 구하는 것을 해본적이 없다. Centroid Decomposition에 대해서만 좀 봤었다.
2. 그래서 나는 Centroid를 구하는 것도 굉장히 어려울 것이라고 생각했다. 
3. 그래서 절대 Div2C에는 Centroid가 안나올 줄 알았다. 

일단 풀이는 트리의 Centroid는 한 개 혹은 두 개이며, 두 개인 경우에는 두 개의 Centroid가 붙어있다. 이 성질은 고수들 사이에서는 꽤나 유명한 것 같지만, 나는 몰랐다. 하지만 굉장히 간단하게 직관적으로 생각을 해냈다. 그리고, 두 개의 센트로이드를 잇는 간선을 자르면 두 개의 컴포넌트의 크기는 같아진다. 따라서 한 쪽의 컴퍼넌트에서 노드 하나를 떼서 반대쪽의 센트로이드에 가져다 붙이면 문제를 해결할 수 있을것이라고 생각했다.

일단 Centroid를 구하는 코드를 검색해봤다. 와! 이렇게 쉬울줄 몰랐다. 절대 Centroid는 아닐 줄 알고, E를 계속 보다 왔는데 뒷통수가 얼얼해지는 느낌이었다. 그대로 긁어왔다. 하나의 Centroid에서 반대쪽의 노드를 찾는 방법은 무엇일까? 그 센트로이드를 루트로 해서 트리를 만든다음에 가장 크기가 큰 서브트리 쪽으로 가면 된다. 당연히 가장 큰 서브트리가 그 잘랐을 때 반대쪽 컴포넌트로 가는 길일 것이다. 그래서 끝까지 가서 그냥 점 하나 떼와서 센트로이드에 붙이면 된다.

위에서 말했던 것처럼 Centroid는 안 쓸 줄 알고 여러가지 뻘짓을 했다... 결과적으로 C를 굉장히 빨리 풀 수 있었음에도 불구하고 굉장히 시간이 늦어졌다. 이것도 B에서의 2틀과 함께 스노우 볼이 뭉쳐졌다. 00:59

E . Deleting Numbers

굉장히 좋고 잘 만든 문제라고 생각한다. 인터렉티브 문제이고 문제 설명은 직접 링크로 읽는 것을 추천한다.

맨 처음에 이 문제를 읽고 생각한 키워드는 '소수'이다. 당연히 배수들을 가지고 물어보고 장난치는데, 당연히 소수를 가지고 뭔가를 해야할 것이다. 일단 1부터 100000까지의 소수의 갯수는 9552이다. 맨 처음 생각한 풀이는 모든 소수에 대해서 B p를 한 다음에 A p를 해서 x가 어떠한 p의 배수인지 확인하고, 만약 p의 배수라면 $p^2$ $p^3$... 을 계속 물어보면서 x의 소인수 분해 결과를 모두 얻는 방법으로 하려고 했다. 하지만 이게 되면 E에 있지는 않을 것이다. 이 경우 필요한 횟수는 약 20000번이다.

제일 문제였던 부분은 소수이다. 소수는 B p A p 로 무조건 2회를 물어봐야 x가 p인지 알 수 있다고 생각을 했다. 이 문제는 못풀겠다 싶어서 C로 돌아가서 위에 적은 짓거리를 하다가 왔다. 그리고서 문제를 다시 읽어보니 A는 1부터 B는 2부터 라는 말이 너무 거슬렸다. A 1을 하면 남아있는 모든 숫자의 갯수를 알 수 있게 된다. 즉, 한번에 묶어서 처리를 할 수 있다는 것이다. 이 문제의 포인트는 거기에 있었다.

약 4900개의 가장 큰 소수를 B p 를 때린다음에 A 1을 부르면 x의 약수에 4900개의 소수가 1개 이상 있는지 알 수 있다. 만약 존재한다면 여기서 다시 4900개의 소수에 대해서 A p를 부르면 어떤 소수의 배수인지를 알 수 있다. 존재 하지 않는다면 그 다음 2500개의 소수에 대해서 위의 짓을 반복하면 된다.
위의 과정을 잘 생각해보면 자연스럽게 10000개를 넘지 않게 된다는 것을 알 수 있다.  

2*큰 소수 같은 경우도 있을 수 있으니, 현재 본 그룹에서 구한 값에다가 곱해서 n을 넘지 않는 소수들에 대해서는 앞에서 부터 순서대로 추가로 체크를 해주어야 한다. 이 과정을 아무리 생각해봐도 400번이나 질문을 던질리는 없다. 따라서 앞에서 부터 소수를 보면서 되면 제곱해 가면서 소인수 분해한 결과를 모두 찾아주면 된다. 코드를 보고 싶으면 그냥 제 제출기록을 보면 될 것 같다.

A 1의 묘수를 찾는 것이 오래 걸렸지만, 사실 그 묘수를 찾는 것이 이 문제의 핵심이기 때문에 뭐 그럴 수 있다고 생각했다. 무난하게 잘 풀었던 것 같다. 시간은 1:33

결과 x

스노우볼이 오지게 굴렀다. ABCE를 풀었음에도 불구하고 20명 정도의 ABCD보다 낮은 점수를 기록했다. 정말 회심의 한방으로 더 쭉 올려야 했고, 이 등수에서는 한등수 한등수에 따라서 올라가는 레이팅의 차이가 굉장히 많이 나게 된다. 좀 많이 아쉬웠지만, 그래도 나쁘지 않았고 Centroid를 배웠으니까 그 수업료라고 생각해야겠다...