[Codeforces] Round #526 Div. 1

https://codeforces.com/contest/1083

 

C, D에 비해 E가 훨씬 쉬웠어서 뭔가 난이도 배치가 이상했습니다. 

 

A - The Fair Nut and the Best Path (Code)

 

임의로 1번 노드를 root로 만든 후, $D[i]$를 i번째 node에서 시작해 밑으로 내려가기만 할 때의 경로의 최댓값이라고 합시다. 그러면 $D[i] = w[i] + \max (D[j] - road(i,j))$ ($j$는 $i$의 자식)  으로 둘 수 있습니다.

 

그리고 정답을 계산할 때는 자식 $a$에서 현재 계산하고있는 $i$를 거쳤다가 자식 $b$로 가는 경우를 고려해야 합니다.

 

B - The Fair Nut and Strings (Code)

 

맨 처음엔 좀 막막했는데 다행히 착안을 해낼 수 있었습니다. 머릿속으로 가상의 Trie를 만들어봅시다. 그러면 depth 1에 총 몇 가지의 노드가 가능한지, depth 2에 총 몇 가지의 노드가 가능한지, ... , depth $n$에 총 몇 가지의 노드가 가능한지를 계산할 수 있습니다. 이제 모든 1, 2, ..., n번째 값에 대해, k 이하면 그 값을 그대로 더해주고 k 이상이면 k만 더해주기만 하면 됩니다.

 

E - The Fair Nut and Rectangles (Code)

 

주어진 점들을 x좌표 순으로 정렬을 해봅시다. $D[i]$를 i번째 직사각형을 반드시 포함할 때의 최댓값이라고 하면 "no nested rectangle" 이라는 조건 덕분에 $D[i] = \max(D[j]+(x[i]-x[j])y[i]-a[i]) (1\leq j \leq i-1) $ 으로 계산이 가능하고 이래저래 손을 보고나면 Convex Hull Trick Optimization으로 풀이가 가능함을 알 수 있습니다.

 

 

 

 

1점 아깝다링..