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

거의 종강일이 다 되어서야 코포를 다시 하게 되었다.

이번에도 정말 오랜만이다.

---

A: FashionabLee

정 n각형에서 서로 직각인 두 변이 존재하는지 판별하는 문제이다.

단순히 n이 4의 배수인지 확인하면 되는 문제이지만, 내각의 합이 어떻고 배수가 어떻고 한참 따지고 있었다.

식마저 잘못 풀어서 더 많은 시간을 낭비하다가 결국에는 맞는 코드에 도달했다.

9분에 AC

---

B: AccurateLee

이진문자열에서 $1$ 이후에 $0$이 연달아 나올 때, 둘 줄 하나를 지우는 연산을 반복할 수 있다.

주어진 이진문자열을 최대한 짧게 만드는 것이 목표이다.

 

문제를 푸는 데에 첫 열쇠가 된 insight는 $10$이나 $111...1110$이나 $1000...000$이나 $111...111000...000$이나 전부 다 똑같다는 것이었다. 연달아 오는 같은 숫자의 개수는 중요하지 않았다. 전부 다 $0$으로 reduce 가능했다.

또 하나의 유용한 사실은, $1$로 시작하고 $0$으로 끝나는 문자열에는 무조건 $10$이 그 사이 어딘가에서 한번 이상 존재한다는 점이다. 이는 그 $10$에서 두 digit 중 하나를 지워내 문자열의 길이를 1 줄인 이후에도 여전하다.

 

여기까지 파악을 끝냈으면 문제는 풀린 것이다. $1$의 첫 위치와 $0$의 마지막 위치를 찾아 그 사이를 다 날리고 $0$ 하나로 바꿔준다면, 남는 문자열이 정답이 된다.

16분에 AC

---

C: RationalLee

숫자 배열이 있다. 여러 친구들에게 각 친구가 요청한 개수만큼의 숫자를 나눠줬을 때, 각 친구가 가진 최대/최소 숫자의 합의 총합을 최대화해야 한다.

 

총합에 포함되지 못하고 버려지는 숫자를 최소화하고자 생각하면 풀이가 보인다.

우선, 제일 큰 숫자들을 각각 친구들에게 하나씩 나눠준다. 이 숫자들은 전부 최댓값이므로 총합에 포함된다.

숫자를 많이 필요로 하는 친구일수록, 최댓값도 아니고 최솟값도 아닌 버려지는 숫자들이 사이에 많아진다. 고로 남은 숫자 중 큰 숫자들은 숫자를 적게 필요로 하는 친구들에게 배정해서, 최솟값을 최대한 키워야 한다.

 

필요한 숫자의 개수 기준으로 친구들을 오름차순 정렬해서, 앞부터 차곡차곡 숫자들을 배정해주면 된다.

30분에 AC

---

D: TediousLee

주어진 규칙대로 트리를 그려나가면, 그 트리 안에서 찾을 수 있는 특정 모양이 몇개인지 계산하는 문제이다.

 

트리 모양을 작은 $n$에 대해서 조금만 그려보면, 트리 구조가 재귀적으로 형성되는 것을 확인할 수 있다.

재귀는 동적 계획법으로 처리하면 된다.

동적 계획법을 바로 적용할 수 있는 것은 아니고, 트리의 루트노드를 모양에 포함시키는지에 대한 규칙성을 조금 더 찾아 특정 숫자의 배수인 $n$에서 처리를 다르게 해줘야 하는 듯 한데, 나는 그냥 각 재귀 단계마다 두개의 dp 배열로부터 구해지는 값을 비교해서 더 큰 값을 취했다.

(자세히 설명하기 귀찮은데, dp 배열을 하나로 최적화하는 대신 그냥 루트노드 포함 여부에 따른 dp 배열 두개가 서로를 참조하며 진행하도록 짰다는 뜻이다.)

 

파이썬에서 TLE를 받고 ㅂㄷㅂㄷ거리면서 C++로 다시 짰다.

WA MLE TLE CE 한번씩 받고 1시간 4분에 AC

---

E: DeadLee

문제상황 착각하고 그래프로 무엇인가를 열심히 짰지만 망해버렸다.

상황을 뒤늦게 인지했고, 제출은 없었다.

---

총평

다섯 번째 퍼플 복귀이다.

문제가 쉽기도 했지만, 또 막히는 부분 없이 시원시원하게 풀어냈다.

B, C, D, E에 모두 greedy 태그가 있는 이상한 대회이다.

 

레이팅 변화 1898 + 65 = 1963

My Performance: ★★★★☆

---

연습지