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

여섯번째 퍼플진입.

---

A: Rainbow Dash, Fluttershy and Chess Coloring

홀짝성 따져서 잘 해보면 된다.

6분에 AC

---

B: Applejack and Storages

각 길이의 plank가 몇개씩 있는지 잘 세주면서, 4개 이상짜리 집합과 2개 이상짜리 집합으로 나눠서 관리하면 된다.

20분에 AC

---

C: Pinkie Pie Eats Patty-cakes

예제 입력과 출력을 보니, 제일 빈도가 높게 등장하는 숫자가 critical한 것 같았다. 빈도가 제일 높은 숫자를 최대한 떨어뜨려 배치한다면, 나머지 숫자들은 적당히 배치하여 동일 숫자간의 최소 거리를 유지할 수 있을 것 같다는 강한 직관을 느꼈다. 강한 직관은 보통 맞다. 문제가 되는 부분은, 빈도가 제일 높은 숫자가 여러 종류일 때이다. 이런 경우, 두 종류의 숫자를 한 숫자처럼 묶어서 배치하면 된다는 생각을 했다. 고로 빈도가 같은 숫자가 있다면 무시하면 된다.

35분에 AC

---

D: Rarity and New Dress

어디선가 많이 본 것 같은 문제. DP 혹은 divide and conquer 느낌이 강하게 난다.

 

재귀적인 방법(DFS)을 통해 해결해보려고 하였고, Python의 recursion limit이 거슬려서 코드도 다시 C++로 짰다. 하지만 로직 자체에 문제가 있었던 것 같다. 대회 마감 직전까지 이것저것 튜닝하며 AC를 노렸지만, 실패하였다.

 

정해는 DP가 맞다.

8 WA 3 RTE

---

총평

그냥 무난한 대회. 또 퍼플...

 

레이팅 변화 1864 + 47 = 1911

My Performance: ★★★☆☆

---

연습지