그래서 자소서는?

오전 셋

UCPC 16 몇개를 돌았다.

C. 사전 조사는 A, A-1, B, B+1이 사전순으로 몇번째인지 세주면 된다.

G. 내가 … 는 DFS트리를 만들고, lowlink를 보면서 적당히 잘 해주면 된다.

K. The Fest… 는 파라메트릭으로 지름이 x이하인 포레스트를 만들 수 있는가를 체크하는데, O(N) tree DP로 된다고 한다.

포스터는 어자피 셀이 O(N^2)이니까, 한번 칠한 셀을 다시 보지 않으면 된다. 한줄마다 union find를 잘 해주면 된다.

오후 셋

폴란드 트레이닝? 문제를 돌았다. 문제 본문은 어디서보는지 모르겠다.

A. Highway Modernization

트리에서 한 간선을 끊고, 임의의 한 간선을 만들었을 때 가능한 지름의 최소와 최대를 구하는 것이다.

모든 서브트리의 지름을 O(N)에 구할 수 있고, 구하고자 하는 값은 서브트리의 지름에만 관여하는 값이기 때문에 O(N)에 가능하다.

트리가 작은 것 부터 DP를 채워나가면 된다고 한다.

B. Car Washing

문제가 복잡하다.

전체 구간의 최소값을 기준으로 분할할 수 있다. 이를 통해 O(N^3M)의 DP를 세울 수 있다.

C. las

적당히 문제 조건에 만족하도록 만들어 주면 된다.

모든 사람에 대해 이웃한 케이크 중 큰 쪽을 먹도록 한다.

다시, 모든 사람에 대해 뒤도는 것이 이득이면 그렇게 하도록 한다.

그러면 만족한다.

D. Desert

DAG가 너무 커서 문제인데, 이는 전부 이어주는 것이 아니라, 정점을 새로 만들어서 간선의 개수를 줄이는 식으로 개선한다.

구간의 개수는 최대 O(M+\Sigma k)개이고, 이를 segtree로 구간을 표현하듯 해주면 로그가 붙는다.

거기서는 다시 비슷하게 해주면 된다.

상당히 재밌었던 문제.