Codeforces Round #627 (Div. 3) 참가 후기

Dashboard - Codeforces Round #627 (Div. 3) - Codeforces

라운드 시작 시간이 밤 10시 5분으로 바뀌었다. 다른 온라인 대회와 시간이 겹쳐서 그랬다는데, 나에게는 매우 반가운 소식.

 

예전에 디비전 3을 연습했을 땐 3개 정도 풀었으니까, 이번에는 최소 3개+a로 목표를 잡았다.

---

A번을 보자. 테트리스 판이 주어졌을 때, 2*1짜리 블럭만을 이용하여 게임을 클리어할 수 있는지 판별하는 문제이다. 이때 블럭을 회전시킬 수 없다.

 

간단하다. 모든 열의 높이가 같아져야 하는 것 아닌가? 그러려면 모든 열의 높이가 홀수 또는 짝수 중 하나여야만 한다. 각 열의 높이를 2로 나눠 주기만 하면 문제 해결.

---

B번은 팰린드롬 문제이다.

수열 a의 부분 수열 중에 길이가 3 이상인 것이 있느냐?

n의 제한이 최대 5000이므로 간단하게 O(n^2) 동적 계획법을 쓰자. 수열 a와 a를 거꾸로 한 것의 LCS(Longest Common Subsequence)를 찾는 방법이다.

 

그런데 정작 문제를 봤을 땐 쓸데없이 어려워 보여서(왜지?) C번을 먼저 풀었다는 건 함정.

---

C번은 뭔가 많이 본 듯한 문제이다. 이거랑 비슷한 문제가 백준에 있는 것 같은데..

 

개구리가 발판을 밟고 점프해서 오른쪽 끝으로 가고자 한다. 개구리는 최대 d의 거리까지 뛸 수 있는데, 오른쪽 끝으로 갈 수 있는 최소의 d를 찾으시오.

아무리 봐도 BFS다. d의 최솟값을 찾아야 하니까, 이분 탐색을 쓰면 되겠다.

그런데 이거 시간 초과 안 나나? d가 최대 200000일 수도 있는데..

 

달리 생각나는 게 없어서 그냥 제출했다. 966ms로 좀 오래 걸리긴 했지만 어쨌든 통과했다.

조금 전 에디토리얼을 읽다가 놀라운 풀이를 발견했다. 요지는 왼쪽으로 뛰는 것이 전적으로 불필요하다는 것이다.

 

느낌을 살리기 위해 원문을 그대로 인용한다.

The only observation we need is that we don't need to jump left at all. This only decreases our position so we have less freedom after the jump to the left.

 

따라서 우리는 오른쪽 발판의 간격만 고려하면 된다. 0(시작 위치)와 n+1(종료 위치)를 포함한 R 발판의 간격 중 최댓값을 구하면 된다.

 

이런 observation은 어떻게 하는 거지? 놀라울 따름이다.

---

D번은 왠지 간단해 보였다.

a[i] + a[j] > b[i] + b[j]를 만족시키는 i, j 쌍(i < j)의 개수를 구하시오.

식을 살짝 바꾸면 a[i] - b[i] > a[j] - b[j]인데.. 이진 탐색의 향기가 솔솔 난다. 근데 왜 틀리지?

 

결국 30분동안 이거만 붙잡고 있다가 끝났다.

이진 탐색을 활용한다는 생각은 맞다. 그런데 식이 틀렸다. a[i] - b[i] > b[j] - a[j]가 맞으며, 한번 더 변형해 주면

a[i] - b[i] > -(a[j] - b[j])가 된다.

 

배열 c를 c[i] = a[i] - b[i]로 정의하자. c를 정렬하고, 모든 양의 정수 c[i]마다 j = lower_bound(-c[i])를 찾고 (i - j)를 더하여 정답을 구할 수 있다. 중복을 피하기 위해 양수만 검사한다.

---

전반적으로는 약간 불만족스럽다. D번을 못 푼 것도 아쉽고, B, C번도 조금 더 빨리 풀 수 있었을 것 같은데.. 어쩌겠니. 이게 내 실력인걸.

 

레이팅은 Pupil로 다시 올라왔다.

 

다음 대회

Codeforces Round #628 (Div. 2) - 2020.3.14 23:35(UTC +9)