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

대회가 언제였더라? ㅋㅋㅋㅋㅋㅋ

2 주 미루다 이제서야 후기를 쓴다.

 

이번 후기부터는 자동 생성된 템플릿을 쓴다! 대회 링크를 입력해주면 문항들을 알아서 크롤링해와서 아래와 같이 각 문항 이름과 링크가 자동으로 걸리도록 코딩하였다. 매번 문제 이름들을 복붙하고 링크를 걸어주는 것이 귀찮아서 후기를 미루게 됐었는데, 이제는 정말 간편하게 후기를 쓸 수 있게 되었다.

---

A: Space Navigation

정말 간단한 문제임에도 불구하고 생각을 여러 차례 잘못하는 바람에 많은 지체가 있었다.

AC: 10분

---

B: New Colony

잠시 살펴보면 그냥 구현 문제임을 확인할 수 있다. $k$ 값이 매우 큰 경우는 직접 확인할 필요가 없기 때문이다.

AC: 20분

구현이 꼬여서 세번이나 틀렸다.

---

C: Fence Painting

마지막 페인터가 가진 색깔이 최종 울타리에 없다면 실패다. 만약 그렇지 않다면, 마지막 페인터가 칠하는 칸이 있을 것이다. 칠할 곳이 없는 페인터들은 전부 다 이 칸에 자신의 색을 칠해주면 된다. 어짜피 마지막 페인터가 덮어주기 때문이다.

페인터들을 색깔별로 정리해주고, 울타리의 각 칸마다 페인터를 한명씩 배정해주면 된다.

배정할 페인터가 없으면 실패다.

남아도는 페인터는 앞에서 설명한 바와 같이 마지막 페인터가 칠하는 칸을 칠해주면 된다.

AC: 45분

얘는 네번이나 틀렸다.

---

D: AB Graph

Palindrome의 길이가 홀수인 경우에는 trivial하게 해가 존재한다.

짝수일 때에는, 모든 vertex 사이의 두 간선이 $a$와 $b$ 종류 하나씩 있는 경우만이 문제가 된다.

이러한 경우에서는, 모든 vertex마다 나가는 간선의 종류가 한가지인 경우 palindrome 구축이 불가능하고, 그렇지 않은 경우 가능해짐을 어렵지 않게 보일 수 있다.

풀이의 방향은 맞았지만, 마지막에 constructive algorithm을 만드는 과정에서 짝수 길이가 아닌 4의 배수 길이에만 통하는 방법을 구현했다가 WA를 여러번 얻어맞고 수정하였다. (그 전에도 버그가 있어서 많이 틀린건 안비밀)

문제 난이도 자체는 쉬웠다.

AC: 1시간 32분

얘는 10번 틀렸다.

---

E: Sorting Books

혹시나 해서 도전해봤는데 끝나고 정해를 보니 어림도 없었다.

Constructive algorithm을 떠올린 후, 이를 계산해줄 DP를 구현하는 방식으로 풀리는데 에디토리얼을 보고 이해하기가 쉽지 않았다.

---

총평

E를 포함하면 20번의 틀린 제출이 있었다.

틀린 제출 수로는 이번 대회가 1위인 듯 하다 ㅋㅋㅋㅋㅋ

올라서 다행이다.

 

레이팅 변화: 1916 + 10 = 1926

My Performance: ★★★☆☆

---

연습지