2022.05.12 PS 일지 ★

냐

K번째 수

문제 링크

냐

풀이

사실 루트질 연습하려고 담아둔 문제인데, 그냥 세그트리로 풀었다.

이게 머지 소트 트리 맞나? 아무튼 각 노드가 구간을 커버하는 배열의 정렬된 상태를 담는데...

이렇게 하면 쿼리를 $\mathcal O(\log n)$개의 구간에 대해 각각 $\mathcal O(\log n)$의 이진 탐색을 진행하여서 총 $\mathcal O(\log^2 n)$에 응답할 수 있게 된다.

ヘビの JOI 君

문제 링크

풀이 쓰기 좀 귀찮네... 생각을 풀어서 쓰려니 귀찮다.

참고로 이 문제 기여에 나는 #Case_work를 넣었다. 깔끔하게 분류 안 하면 자꾸 꼬이는 듯.

풀이

물론 다익스트라다. 뭐 다른게 나올 일도 없지 않은가...

그 상태에서 뭘 어떻게 해야되냐가 문제인데...

 

그냥 노드가 최단거리 정보만 저장하면 해를 파악하기에 부족할 것이다.

그러면 노드와 어떤 방문 시의 상태에 묶음으로 최단거리를 저장해야 할텐데, 각 노드에 들어오기 전에 추운 방 혹은 더운 방에서 나온지 얼마나 됬는가를 함꼐 저장하면 된다.

다행히 $X$가 작으므로 공간이 맞는다.

그렇게 풀면 정답이긴 한데 앞서 말한대로 각 전이 과정을 잘 살펴서 문제를 풀어야 한다.