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

휴가 중 두번째 대회.

---

A: Perfect Permutation

Shift one.

AC: 2 분

---

B: Party

경우를 나누어 생각하면 어렵지 않다. 일단 모든 사람을 최대한 포함시키는 것에서 시작한다. Pair의 개수가 홀수라면, 그래프에서 몇몇 정점을 제거해야한다. 제거해야 하는 정점의 집합 속에 홀수명의 친구를 가진 정점이 있다면, 그 정점만 제거해도 됨을 알 수 있다. 제거해야 하는 정점의 집합  속에 홀수명의 친구를 가진 정점이 없다면, 그 중 두 정점이 서로 친구여야만 함을 알 수 있고, 서로 친구인 두 정점만 제거해도 됨을 알 수 있다.

 

따라서 홀수 친구를 가진 모든 정점을 먼저 살피고, 서로 친구인 짝수 친구를 가진 정점들을 다 살피면 된다.

모두 살펴도 시간은 충분하다. 

AC: 20 분

---

C: Color the Picture

규칙에 맞게 칸들을 색칠해나가면, 같은 색은 무조건 세로로, 혹은 가로로 끝에서 끝까지 이어지는 strip모양이 됨을 알 수 있다. 이때, strip의 두께는 2 이상이다.

주어진 색들의 개수로부터 이러한 strip들을 만들 수 있는지 판별하면 되는데, strip 두께가 2 이상이라는 조건 때문에 예외처리가 복잡해졌다. 이 예외처리하느라 시간 다씀;;

AC: 1 시간 19 분

---

총평

D와 E는 난이도가 너무 어려워서 실질적으로 ABC 빨리풀기 대회였다.

싫다.

 

레이팅 변화: 1837 - 41 = 1796

My Performance: ★★☆☆☆