Codeforces Round #824 (Div. 2)

주말에 노느라 ABC, ARC를 다 안쳐서 죄책감에 이거라도 쳤다.

 

A. Working Week (0:12, +)

잘 정리하면 답은 \(\frac{n}{3} - 2\)라고 한다. 난 생각이 안나서 더럽게 풀었다. 이걸 어떻게 알지?

 

B. Tea with Tangerines (0:16, +)

최솟값이 기준이 되어야 한다는 사실을 자명하게 알 수 있고, 다른 수들도 잘 나눠줄 수 있다는 사실은 덜 자명하지만 찍어서 맞출 수 있다.

 

C. Phase Shift (0:35, +1)

그리디하게 보내주면 되는데, 모든 알파벳이 반드시 하나의 큰 사이클을 이루어야 해서 좀 까다롭다. 난 대충 Union Find를 써서 구현했다.

 

D. Meta-set (0:47, +)

2개를 정하면 남은 1개를 정할 수 있다. 따라서, 이와 같은 방법으로 각 카드를 포함하는 set의 개수를 구할 수 있고, 이 개수들에 대해 \({n \choose 2}\)를 모두 더해주면 된다.

 

E. House Planning (1:36, +2)

우선 일반성을 잃지 않고 \(p_1 <= p_2, p1=0, p2=x\)라고 해 보자. 그러면 둘 사이에 있는 집은 각 배열에서의 값이 합이 \(x\)일 것이고, 바깥에 있는 집은 차가 \(x\)일 것이다. 따라서, \(x\)를 고정하고 나면 각 배열에서 합이나 차가 \(x\)인 값들을 간선으로 이어준 후 완전 매칭을 찾는 문제와 동치가 된다. 그리고, 가능한 \(x\)의 후보는 \(O(N)\)개이다. Unit Capacity에다 이분 그래프라 디닉이 빠르게 도므로, 모든 \(x\)에 대해서 플로우를 돌려주면 된다. 역추적은 잘 해주면 되는데, 음수가 나오는 것만 주의해주자.