[Codeforces] Round #499 (Div. 1)

http://codeforces.com/contest/1010

 

거의 3주만에 친 코포였습니다. 그 사이에 실력이 많이 늘었을 줄 알았는데 생각보다 그렇지 않아서 아쉬웠습니다. 참가자 대다수가 A, B, C, D를 풀었고 저는 D 풀이를 다소 늦게 착안했습니다. A 또한 문제의 조건을 잘못 이해해서 System test때 틀렸습니다.

 

A - Fly

 

연료의 양을 가지고 binary search를 하면 됩니다. 맨 처음에 연료의 양이 1e9일 때 가능한가/불가능한가를 먼저 확인했는데 이 경우 실수 오차로 인해 실제로 가능한데 불가능하다고 간주해버릴 수 있습니다. 문제의 조건 중에 "가능하다면 연료의 양이 반드시 1e9 이하다"라는 조건을, "연료의 양이 1e9 이하일 때만 답으로 간주한다"라고 잘못 이해해서 어떻게해도 실수 오차가 발생하니 그냥 1e9로 확인했는데, 제대로 이해했다면 그냥 1e9+1로 확인하면 됐었습니다. 이외에도 식을 직접적으로 찾아내 $O(N)$에 해결할 수도 있습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20499%20Div.%201/A.cpp

 

B - Rocket

 

맨 처음에 N번에 걸쳐 1을 보내면 rocket의 sequence를 알 수 있습니다. 그 후 binary search를 하면 됩니다. 흥미로운 Interactive 문제였습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20499%20Div.%201/B.cpp

 

C - Border

 

$gcd(a,b) = g$라고 할 때 $S = {ax+by|x,y is integer} = {ng | n is integer}$입니다. (Diophantine equation) 그렇기에 모든 수에 대해 우선 K로 나눈 나머지를 계산한 후, 그 나머지들과 K의 gcd가 저 집합에서의 g에 해당합니다. 이제 정답의 갯수는 $K / g$ 이고 $g, 2g, 3g, ..., (K/g)g$가 가능한 value들입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20499%20Div.%201/C.cpp

 

D - Mars rover

 

맨 처음엔 감을 못잡다가 끝나기 한 40분 전부터 감을 잡았습니다. 일단 초기값에서 각 Node의 값이 true인지 false인지를 DFS를 돌면서 구해둡니다. 그 다음에 할 것은, 그 Node의 값이 flip됐을 때 root의 값이 어떻게 되는지를 Memoization을 통해 구합니다. 그러고나서 답을 출력하면 끝입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20499%20Div.%201/D.cpp

 

D를 풀어낸게 다행이긴 하지만 A를 틀리고 B, D 모두 한 번씩 틀리고 맞춘게 좀 아쉽네요.