[Codeforces] Round #482

http://codeforces.com/contest/979/

 

A/B의 pretest가 굉장히 약해 hack이 굉장히 많이 나왔습니다. A를 풀자마자 hack이 많이 발생하겠다는 것을 깨달아 A에서 6번 hack을 성공하고, B에서도 5번 hack을 성공했지만 정작 저의 B와 C가 실수로 나가서 아쉬웠습니다. hack이 없었으면 레이팅이 심각하게 깎일 뻔 했습니다.

 

A - Pizza, Pizza, Pizza!!!

 

2n개의 조각을 만들기 위해서는 n/2번의 칼질이 필요하고 2n+1개의 조각을 만들기 위해서는 2n+1번의 칼질이 필요합니다. 단 1개의 조각을 만들기 위해서는 칼질을 0번 해야합니다. 이 예외처리를 하지 않은 사람들이 많았습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20482/A.cpp

 

B - Treasure Hunt

 

설명은 단어 단위로 어쩌구저쩌구 써져있지만 생각해보면 사실상 각 글자의 출현빈도만 가지고 있으면 됨을 알 수 있습니다.(abc의 등장횟수나 a/b/c 각각의 등장횟수나 동일하므로) 그리고 min(max_frequency+n, L)을 계산하면 됩니다. 그러나 단 하나의 예외가 있는데, max_frequency = L이고 n = 1일 때만 답이 n-1입니다. (aaaa -> aaab 이므로.) 제가 착각한 것은 aaab, n = 2일 때 답이 3이라고 생각했는데(aaab -> aaaa -> aaab) 사실은 aaab -> aaac -> aaaa로 답을 4로 만들 수 있습니다. 이러한 것이 pretest에 없었고, lock을 한 뒤에야 깨달아서 남의 것만 hack을 했습니다.

 

C - Kuro and Walking Route

 

x를 root로 두어 트리를 재구성해보면, x의 자식의 subtree 중에서 y가 속한 subtree를 제외한 나머지의 원소에서 y의 subtree로 가는 것이 불가능함을 알 수 있습니다. 그러므로 이들의 갯수를 구해 곱한 값을 n*(n-1)에서 빼면 됩니다. int 범위를 벗어나기 때문에 long long을 써야하는데 아무 생각 없이 int를 써서 날려먹었습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20482/C.cpp

 

저번에 A B C D를 풀었는데 정작 A C D를 날려먹은 라운드와 비슷하게 A B C를 푼 줄 알았는데 B C를 날려먹었습니다. 그나마 hack 덕분에 퍼플을 유지하긴 했지만 앞으로 같은 실수를 하지 않게 주의해야겠습니다.