스트레스를 엄청나게 받는다. 업솔빙은 해도 빡치고 안해도 빡치는데, 어쩔지 모르겠다. 흐어어

오전 셋

NEERC 2015 몇개를 돌았다.

  1. Graph

위상정렬하면서 적당히 잘 하면 된다….

  1. Insider’s Information

모든 조건을 만족하는 순열이 존재하니, 양 끝에 올 수 있는 수들을 순서대로 나열한 후, 뒤에서부터 다시 채워나간다. 새로운 수를 붙일 때 오른쪽이나 왼쪽 중 무조건 반 이상의 조건을 만족시키는 선택이 있으니, 그렇게 하면 된다.

  1. Journey …

가격에 대한 파라메트릭으로, DP를 deque를 써서 구현하면 O(NlogX)에 할 수 있다.

오후 셋

BOI 2018을 돌았다.

  1. Election

쿼리를 정렬한 후 하나씩 붙여나가면서 풀거나, 스파스테이블 등으로 전처리해서 풀거나, 최대 부분합을 세그트리로 관리하면서 풀면 된다.

  1. Homecoming

원형에서 DP를 해야 하는데, 최적이 아닌 경우까지 포함해도 상관없으므로, 좀 더 편하게 DP식을 잡을 수 있다. 아마 전에 사용했는지만 따지면 되는 듯 하다.

  1. Min-Max Tree

간선을 적당히 소팅하고, 간선들의 칠하는 횟수를 O(N)에 하면 되므로, 트리에서 경로 압축을 사용해서 할 수 있다. 이미 칠해진 간선으로 묶인 정점들을 uf로 묶어주면 된다.

그 후, z에 따라 그래프를 그리고, 간선들을 directing해주면 된다. 가능함이 보장되므로, DFS하면서 directing해주면 된다.