[Codeforces] Round #484 (Div. 2)

http://codeforces.com/contest/982

 

뭔가 포텐이 터져서 오렌지로 진입했네요. 정확성이 많이 올라가 좋았습니다.

 

A - Row

 

Maximum이 아니라 Maximal임에 주의해야합니다. 1이 연속해서 2개 나오거나, 0이 연속해서 3개 나오거나, 맨 앞에 0이 연속해서 2개가 나오거나, 맨 뒤에 0이 연속해서 2개가 나오면 Maximal이 아닙니다.(N = 1일 때는 별도로 처리).

 

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

 

B - Bus of Characters

 

Introvert / Extrovert에 해당하는 Priority Queue 2개를 만들어 처리를 해주면 됩니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20484/B.cpp

 

C - Cut 'em all!

 

우선 vertex가 홀수개면 답은 -1임이 자명합니다. 짝수개의 경우, 편의상 1을 root로 하는 트리로 생각을 해봅시다. 이 때 간선 하나를 제거하는 것은 임의의 노드를 root로 하는 graph를 분리하는 작업임을 알 수 있습니다. 그러므로 root가 1인 tree를 제외하고 subtree의 갯수가 짝수개인 tree의 갯수가 곧 정답입니다. DFS로 subtree의 갯수를 셀 수 있습니다.

 

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

 

E - Billiard

 

일단 아이디어는 reflecting입니다. 당구판을 무한히 이어붙인 보드를 생각해본다면, 충돌에 대한 고민 없이 그냥 공이 쭉 일직선으로 간다고 생각하면 됩니다. t초가 지났을 때 공이 구멍에 들어가기 위해서는 x+t*vx가 n의 배수이고 y+t*vy가 m의 배수이어야 합니다. 이러한 t는 Chinese Remainder Theorem 혹은 Extended Euclidean Algorithm으로 구해낼 수 있습니다. CRT를 쓸 경우 long long 범위를 벗어날 수 있기 때문에 C보다는 python을 이용하는 것이 낫습니다. 일단 t를 찾은 이후에는, 가로벽과의 bounce가 몇 번 일어나는지, 세로벽과의 bounce가 몇 번 일어나는지를 세면 4개의 구멍 중 어느 구멍에 들어가는지를 알 수 있습니다. 기하학과 정수론이 합쳐지는 신기한 문제네요.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20484/E.py

 

E를 3번 틀리고 맞추긴 했지만, A/B/C를 바로 맞췄다는게 많이 기쁩니다. 사실 아직도 잘 모르는 알고리즘이 산더미인데다가 기복도 좀 있기 때문에 금방 다시 강등당할 것 같긴 합니다. 그래도 이렇게 빨리 오렌지를 달 것이라고는 생각 못했는데ㅎㅎ.. 일단 학교 숙제랑 시험들을 넘기고 나서 2000점 위에서 계속 머무를 수 있도록 공부를 많이 해야겠습니다.