대회후기: Codeforces Round #628 (Div. 2)

블루-퍼플 진동은 당분간 계속될 것 같다.

대회가 있는 줄 모르고 있었는데, Nyso의 카톡을 받고 추가 등록 시간에 등록하였다.

---

A: EhAb AnD gCd

최대공약수와 최소공배수의 합이 $x$가 되는 두 수를 출력하면 된다.

print(x - 1, 1)로 해결했다.

12분에 AC

---

B: CopyCopyCopyCopyCopy

길이 $n$의 배열이 들어온다. 그 배열을 $n$번 반복시킨 새로운 배열에 대해서, LIS는?

 

처음에는 착각하여 답이 나올 리 없는 코드를 제출했었다.

다시 생각해보니 print(len(set(a)))로 한번에 처리되는 문제였다.

1 WA 후 18분에 AC

---

C: Ehab and Path-etic MEXs

Tree가 입력으로 들어온다.

$n-1$개의 edge에 $0$부터 $n - 2$까지의 integer label을 붙여 [maximum value of '두 node 사이의 path 상의 MEX값' over all pairs of nodes]를 최소화하고자 한다.

 

먼저 혼자 착각해서 한번 틀렸다. Again.

다시 풀어보자.

 

Tree의 특징을 잘 생각해보면, 임의의 두 edge를 골랐을 때, 그 두 edge가 동시에 포함되는 path는 무조건 존재한다. 따라서 0과 1값이 동시에 포함되는 경로는 무조건 존재할 수 밖에 없기에, 우리의 목표는 이제 0, 1, 2 값이 동시에 존재하는 경로를 존재할 수 없게 하는 것이다.

이는 0, 1, 2 값을 각각 leaf와 연결된 edge에 올림으로써 달성 가능하다. 만약 leaf 개수가 3개가 안된다면 총 2개가 있다는 뜻인데, 이런 경우에는 그냥 모든 node가 줄줄이 꿰어져 있는 경우이므로 어떻게 배열해도 상관이 없다(in this context, we are considering all nodes with a degree of 1 to be leaves, even if it may be the root).

1 WA 후 38분에 AC

---

D: Ehab the Xorcist (오늘의 뇌절문제)

XOR해서 $u$, 더해서 $v$가 되는 숫자들을 찾아라... But, minimize the number of numbers.

 

일단 XOR의 특성에 대해 혼자 착각해서 뻘짓을 오래 했다. 이렇게 착각한 것은 이번 대회가 처음이 아니다. (지난 대회 C)

 

정신 차리고 다시 풀었지만, MLE, TLE, 로직 오류 삼단콤보로 디버깅만 하면서 시간을 엄청 날렸다.

결론적으로 풀이방법은 다음과 같다:

길이 64의 배열을 만든다. 이 배열에서 각 값이 나타내는 바는 정답이 되는 숫자들의 각 자리수마다 그 합이 얼마가 돼야 하는지이다. $u$를 만들기 위해 일단 $u$를 하나 깔아두고, $v$를 만들기 위해 높은 자리수부터 각 자리수마다 짝수만큼 증가시킬 수 있는 최대치를 증가시킨다. 이런 greedy한 방법이 되는 이유는 대회시간에 직관을 섞어서 대충 증명했었다. 일단 이러한 방식으로 이 길이 64짜리 배열이 완성되면, 각 자리수마다 최대 1개씩 훑어내며 이진수를 출력하면 된다.

1 MLE, 2 TLE, 3 WA 후 1시간 38분에 AC

이후 뒷 문제들은 정답률이 현저히 낮아 쳐다보지도 않았다.

---

총평

XOR를 못하고서도 너가 컴공이냐;;

 

레이팅 변화 1921 - 49 = 1872

My Performance: ★★☆☆☆

 

연습지