USACO 2021 Decomber Contest 후기

1. Bronze

 

세 문제를 전부 어렵게 푸느라 올솔이 두 시간이나 걸렸다.

전부 실버 ~ 골드 하위급 문제들이라 크게 할 말은 없다.

 

 

2. Silver

 

많이 어려웠다. A를 열고 고민하는데 너무 더러워 보였고 B를 열고 고민하는데 괜찮은 풀이가 전혀 생각나지 않았다.

다행히 C의 아이디어가 빨리 떠오르긴 했는데, 제한이 애매해서 안전하게 가려면 FFT를 써야 하는 상황이었다.

FFT 템플릿을 가져와 스위핑을 적당히 구현해주었고 한시간이 조금 넘은 시점에 C를 맞았다.

그리고는 그나마 쉬워보이는 B를 잡았다.

일단 유니온파인드를 이용해  간선들을 그룹 짓고, 열심히 케이스워크를 해서 직접 만든 예제들을 다 맞췄다.

그런데 반례는 끝도 없이 나왔고, 결국 유파에 map을 섞는 이상한 풀이를 구상했는데 이게 맞아버렸다. 이 풀이의 반례가 있는지는 더 생각해봐야 알 것 같다.

A는 아이디어만 봐줄 만한 구현 문제였다. 케이스 나누기도 힘들고, 이분 탐색 등을 구현하는 것이 많이 까다로웠다.

그래도 한 번에 맞아서 다행이었다.

 

 

3. Gold

 

문제를 쓱 봤는데 C번이 기하여서 승산이 없다고 판단, 그냥 바로 껐다.