국대교육 일지 - 7/25 | Diuven’s Blog

자소서 써야 한다. 영어 공부도 해야 한다. 그런데 PS는 더 해야 한다.

CF17은 30분정도 대회라고 한다. 그만큼 단순한 문제들, 구현이 안복잡한 문제들이 많다. 꿀잼

A. Colorful MST

색이 같은 정점끼리는 미리 unite해준 다음에, 그냥 간선 수가 k-1이 되도록 MST를 만들어 준다.

B. Many Swap Sort

1과 n-1을 인자로 한 swap을 통해 원형에서 인접한 두 원소를 교환하는 것을 구현할 수 있다. 버블소트해주면 된다.

G는 모른다.

마지막 JOISC 17을 돌았다. 오늘도 어려웠다.

한 점에서 한 방향으로 갈 수 있는 만큼 가는 것은 $O(logN)$ 에 할 수 있다.

그림을 잘 그려보면, 한 출발 방향당 꺾는 횟수가 $O(H+W)$ 밖에 안된다는 것을 알 수 있다. 그림을 그리지 않더라도, 내가 타고 있는 간선의 정체도는 단조 증가할 테니, 증가 횟수는 많아야 $O(H+W)$ 임을 쉽게 알 수 있다.

따라서 쿼리당 처리해주면 $O(Q(H+W)log(H+W))$ 에 할 수 있다.

DFS오더링 후, 내 아래에 몇개의 정점이 있는지를 저장하면 된다. 그대로 하면 36개의 비트를 사용해야 한다.

깊이가 18뿐이라는 데에 착안해서, 모든 서브트리의 크기를 단순화 시킬 것이다. 정확히는 실제로 사용하지 않는 정점을 추가하여, 서브트리의 크기의 종류를 충분히 줄이는 것이 목표이다.

어떤 실수 p(~1.02정도?)를 잡고 $\lceil p^i \rceil$ 로 양자화시켜주면 가능하다고 한다.

두개씩 묶어서 두개가 다 터진건 버리고, 3진수로 인코딩해주면 85점까지는 된다. (나는 ’00’이 없는 이진 문자열을 열거해서 75점을 받았다)

이제 세개씩 묶어서, 두개 혹은 세개가 터지면 버리고, 그 외의 경우는 적당이 인코딩해서 1비트보다 많은 정보를 담을 수 있다. 그걸 손으로 잘 찾은 후, 구현하면 된다.