[Codeforces] Forethought Future Cup - Elimination Round

https://codeforces.com/contest/1146

 

거의 두 달 만에 친 코포였고 적당히 조졌습니다ㅎㅎ...

 

A - Love "A" (Code)

 

min(2*a의 갯수-1, 전체 길이)가 답입니다.

 

B - Hate "A" (Code)

 

주어진 T의 길이를 lenT, T 내의 a의 갯수를 numa라고 할 경우 S의 길이는 $(lenT+numa)/2$입니다. 이를 토대로 S를 찾아낸 후 S로부터 실제 T를 만들어 주어진 T와 일치하는지 확인하면 됩니다.

 

C - Tree Diameter (Code)

 

트리의 지름은 임의의 노드 a에 대해 우선 a와 가장 멀리 떨어진 노드 b를 찾고, 노드 b와 가장 멀리 떨어진 c를 찾았을 때 b와 c의 거리입니다. 이 성질을 이용해 답을 구할 수 있지만, 굳이 이를 쓰지 않더라도 모든 쌍에 대한 거리를 확인하게끔 질의를 해서 깔끔하게 해결할 수 있습니다.

 

번호가 다른 두 수는 반드시 특정 비트의 값이 다르므로 제일 오른쪽 비트가 0인 수의 집합 / 1인 수의 집합으로 나누어 질의를 보내고, 그 다음 비트가 0인 수의 집합 / 1인 수의 집합으로 나누어 질의를 보내고... 이런식으로 하면 답을 구할 수 있습니다.

 

C까지 굉장히 빠르게 풀어낸 후 D에서 막혔고, E를 보다가 splay tree를 이용해 푸는 문제인줄 알고 시간 낭비를 하다가 다시 D로 돌아와서 납득이 잘 안가는 그리디를 세워서 어찌저찌 코딩을 했는데, 해당 그리디가 맞긴 했지만 구현에서 실수가 있었는지 system test에서 터지고.. 여러모로 아쉬운게 많았습니다.

 

쉬운 문제는 굉장히 빨리 풀어내는데 조금만 어려워지면 굉장히 버벅거리게 되네요. 양질의 문제를 많이 풀어봐야 나아질텐데 아쉽습니다. 학기 중에는 오렌지 유지를 목표로 삼아야겠습니다.