Codeforces Round #736 (Div. 2)

A. Gregor and Cryptography(00:04, +1)

주어지는 수가 5 이상의 소수이므로 홀수임이 보장되고, \( N \equiv 1 \pmod {N-1} \) 이므로 2와 \(N-1\)을 출력하면 된다.

 

B. Gregor and the Pawn Game (00:08,+)

앞에서부터 보며 해당 칸에 올 수 있는 폰들 중 가장 왼쪽에 있는 것을 선택해주면 된다.

 

C. Web of Lies (00:20, +)

본인보다 큰 노드와 하나라도 연결되어 있으면 죽음을 알 수 있다. 따라서 각 연결을 큰 쪽에서 작은 쪽으로의 일방향 연결이라 생각했을 때의 indegree 갯수를 관리해주면 된다.

 

D. Integers Have Friends (01:54, +5)

말할 거리가 많은데, 처음 봤을 때 파라메트릭+세그트리를 이용한 풀이가 떠올랐지만 저번 대회에서 그러다 말린 기억이 나 파라메트릭을 투 포인터로 내렸다. 시간 안에 무조건 돌거라는 생각에 세그트리를 짰지만 TLE가 아닌 MLE가 났고, 이후 더 깊은 생각을 통해 풀이를 투 포인터를 두 번 쓰는 \(O(N)\)으로 줄일 수 있었다. 그런데 막상 대회가 끝나고 보니 대부분의 사람들이 세그트리를 이용한 풀이로 풀었더라.. MLE가 왜 났는지는 아직도 의문이다.

 

F1.Gregor and the Odd Cows (Easy)

픽의 정리를 알면 문제가 굉장히 간단하게 바뀐다. D를 빨리 풀었으면 풀었을 수도 있을 것 같아 아쉽다.