[Codeforces] Round #500 (Div. 1)

SCPC 전날에 쳤던 코포였는데 시원하게 말아먹었습니다. 그 때문에 좀 찜찜했던 기억이 있네요.

 

A - Photo of The Sky (Code)

 

Greedy한 관점에서 생각해보면 비슷한 크기를 가진 값들을 몰아서 x 혹은 y에 넣는게 좋습니다. 그러니 일단 정렬을 해두고 N개씩 묶은 값을 봅니다. 예를 들어 1 3 4 5 6 7 이면 (1 3 4) / (5 6 7), (3 4 5) / (1 6 7), (4 5 6) / (1 3 7)을 살펴보면 됩니다.

 

B - Chemical table (Code)

 

X로 묶인 행/열을 Union-Find로 관리해서 그룹의 갯수가 몇 개인지를 세면 됩니다. 맨 처음에는 문제를 아예 잘못 이해했고, 이후에도 행과 열을 따로 생각해서 아주 삽질을 엄청나게 하고 대회 때는 맞추지도 못했네요.

 

C - Hills (Code)

 

$D_{i,j}$를 i개의 hill에서 j개의 집을 지을 수 있도록 하는 최소 시간이라고 할 때, $D_{i,j}$는 $D_{1 to i-1, j-1}$로부터 구해낼 수 있고 값을 누적시키면서 진행하면 $O(N^2)$에 해결할 수 있습니다. 풀이는 비교적 빠르게 찾아냈는데 B에서 시간을 내다버리고 급하게 짜다가 결국 완성을 못하고 대회가 끝났습니다.

 

 

오랜만에 레이팅을 완전 꼴아박았습니다. 다시 열심히 해야겠네요.