오전 셋

적당한 백준 셋을 돌았다

쉽게 제한된 메모리 / 제한된 메모리
Parallel Binary Search를 구현하면 된다. O(NlogMlogX)에 할 수 있다.

Haybale Guessing
Mysterious Array
RMQ

Justice for All
2배가 가능하고 +1이 가능하다. 따라서 모든 수를 만들 수 있다.
초기 상태는 양쪽에 정점이 한개 있고, 서로 연결되어있는 1의 상태다.
여기서 2^x배를 하고싶다면, 정점이 2개씩 있는 완전 이분 그래프를 x개 얹으면 된다.
여기서 +1을 하고싶다면, 방금 얹은 그래프들을 대각으로 이어주면 된다. 예시와 그림이 필요하다.

오후 셋

적당한 RC 셋을 돌았다.

Hanging Hats

History Course
적당히 하랜다. (official)

Journey from Petersburg to Moscow
임의의 path P를 생각하자. |P|\leq k인 경우에는 그냥 최단경로를 구해주면 된다.
|P|>k인 경우에는, t를 P에서 k+1번째로 큰 가중치라고 했을 때, Cost(P) = \sum\limits_{e \in P} max(0, e.cost-t)가 된다.
가능한 t는 최대 M개이므로, 가능한 모든 t에 대해서 다익스트라를 돌려주면 된다. (0도 포함하면 편하다)