Codeforces Round #628 (Div. 2) 참가 후기

글이 늦은 이유는 개강을 했기 때문.. 이라고 핑계를 대 본다.

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

지난 div. 2에서 1문제밖에 풀지 못했던 아픔이 있기 때문에 이번에는 2문제를 확실하게 푸는 것으로 목표를 정했다. 3문제를 풀기에는 내 수면 패턴이 허락하지 않을 듯 하여..

---

여느 때와 다름없이 A번을 읽는다.

x가 주어질 때, GCD(a, b) + LCM(a, b) = x를 만족시키는 (a, b) 쌍을 구하시오. 쌍이 여러 개일 경우 아무거나 출력한다.
단, GCD(a, b)는 a와 b의 최대공약수이며 LCM(a, b)는 a와 b의 최소공배수이다.

 

문제를 보고 5분동안 브루트 포스에 대해 생각해 봤다. x가 최대 10억이니까 시간 초과가 나지 않을까? 글쎄..

 

아무리 생각해 봐도 방법이 없어서 그냥 구현해 봤다. 그런데 예제 결과에서 나는 아주 신기한 관찰을 할 수 있었다.

정답이 전부 (1, x-1)만 나오잖아?

1은 모든 수의 공약수, 1과 n의 최소공배수는 n..

그렇다면 (1, x-1)은 항상 정답이 될 수 있다!

 

빠르게 제출하고 넘어가자.

---

B번을 읽는데 왠지 조금 졸린 것 같다.

길이 n인 수열 a를 n번 이어붙인 수열에서 LIS(Longest Increasing Subsequence)의 길이를 구하시오.

평범한 LIS 문제였다면 O(N^2log(N^2))으로 풀 수 있겠으나, n이 최대 10만이므로 n^2은 최대 100억이다. 이래서는 시간은 고사하고 메모리조차도 맞출 수 없다.

 

사실 여기서 내가 많이 삽질했다. LIS를 구하라고 나와 있기 때문에, 내가 모르는 LIS 계산 방법이 있나 찾아봤는데 그건 아닌 것 같고. 이런저런 생각을 해 보지만.. 좋은 생각이 떠오르지 않는다.

 

어느덧 12시 반이 다 되어간다. 마지막으로 문제를 다시 읽어보자.

같은 수열을 n번 이어붙였기 때문에, 이어붙인 수열마다 수 하나를 선택할 수 있다. LIS를 만들기 위해 오름차순으로 수를 선택해야 할 것이다. 같은 수를 여러 번 선택하면 안 되겠고..

 

그렇다면 주어진 수열 a에서 중복을 제거한 길이가 답이 되지 않겠는가? 왜 이걸 지금까지 생각하지 못했지?

---

시간상 C번을 풀지 못할 것 같긴 하지만 읽어나 보자.

트리에 n개의 노드가 있다. 여기에 있는 (n-1)개의 간선에 번호를 붙이려고 한다..

자야겠다. 무리다. ㅠㅠ

---

이번 대회에서는 절반의 성공을 거두었다. 문제 2개를 풀었다는 점은 만족스럽지만, 더 빨리 풀 수 있지 않았나 하는 아쉬움이 든다. C번 같은 트리 dp 문제도 풀 줄 알아야 하는데. 이번 주에는 트리 문제를 많이 풀어 보자.

 

그리고 대망의 레이팅-

1점 지켰다

떨어질 것 같긴 했는데 54점이나?

 

하..

갈 길이 멀다. 화이팅하자.

 

 

다음 대회

Codeforces Global Round 7 - 2020/3/19 23:35(UTC +9) 시작