10650 Marathon
다음과 같은 두 배열을 관리하자.
- next[i] : i번째 좌표에서 i+1번째 좌표로 이동하는 거리
- save[i] : i번째 좌표를 달리기 중 생략하기로 결정했을 때 절약하는 거리
그러면 쿼리 Q는 다음과 같이 해결할 수 있다. s에서 e까지 이동해야 하면, e−1∑i=snext[i]−max 가 답이 된다. 따라서 \text{next}는 부분 합 세그먼트 트리, \text{save}는 부분 최대 세그먼트 트리를 이용해서 관리해주면 O(\log N)에 찾을 수 있다.
쿼리 U는 Naive하게 처리해 주어도 세그먼트 트리 위에서 O(\log N)에 처리 가능하다.
Trivial한 세그먼트 트리 문제.
6150 Summing Sums
이런 문제가 나오면 흔히 하던 대로 각 소가 들고 있는 수를 초기값의 선형 결합으로 대신 나타낼 수 있다. 규칙을 잘 찾아보자. 연산을 t번 시행했을 때 각 소의 수를 생각해보자. 어떤 i번째 소가 들고 있는 수를 a_1c_1 + a_2c_2 + \cdots a_Nc_N이라고 나타내면, t=1일 때 x \neq i인 a_x =1이다. 이런 a_x는 항상 값이 모두 같으므로, 이를 그냥 t번째 시행에서 a_t라고 하자. 그러면 a는 t의 기우성에 따라 a_{t+1} = a_t (n-1) + 1이던지, a_{t+1} = a_t(n-1) - 1이다. 그리고 자기 자신이 더해지는 횟수도 역시 t의 기우성에 따라 a_t -1 혹은 a_t +1이 되게 된다.
a가 t의 기우성에 따라 일차 점화식의 합성으로 나타나므로, 홀수일 때의 점화식을 짝수일 때의 점화식에 넣어 식을 적당히 정리하면 (n-1)에 대한 거듭제곱과 공비가 -1인 등비수열의 합으로 나타나게 된다. 뒤쪽 등비수열을 등비수열 공식에 넣어 계산하면 a를 거듭제곱이 지배하는 복잡도인 O(\log T)에 계산할 수 있게 된다(나눗셈이 있어서 모듈러 인버스를 써야 한다). 그 후 실제로 곱해서 계산해주면 된다.
저 일차 점화식의 합성이 굉장히 쉬운 부분인 것 같은데, 나는 저런 부분을 평소에 잘 못봐서(수올러가 아니라...) 많이 애먹었다. 그것만 빼면 무난무난한 문제인 것 같다.
5951 The Continental Cowngress
N이 작다. 각 변수에 대해서 Y와 N 각각 고정시켜보고 투샛 한번씩 돌리면 된다.
21815 Portals
문제가 상당히 이해하기 어렵다. 정말 정말 어렵다...
각 포탈을 정점으로 바꾸고 각 정점의 permutation 관계를 간선으로 생각하자. 그러면 포탈이 2N개 있고, 기존 그래프에서 p_1 p_2 p_3 p_4가 있을 때 p_1과 p_2, 그리고 p_3와 p_4를 각각 간선으로 이어줄 수 있다. 핵심적인 관찰은 이렇게 간선을 이으면 바뀐 그래프에서 모든 정점의 차수가 2이므로 disjoint cycle을 형성한다는 것이다.
만약 내가 돈을 내고 permute해서 간선을 바꿔먹는다면, 네 점이 만드는 사각형의 변이 토글되는 느낌으로 생각할 수 있다. 중요한 부분은 만약 그 네 사각형이 서로 다른 cycle에 걸쳐 있다면, 변을 토글했을 때 두 cycle이 합쳐지면서 하나의 cycle로 바뀐다는 것이다. 따라서 각 사이클을 컴포넌트라고 생각하고 permute하는 것을 간선을 추가하는 것으로 생각하면 MST 문제가 된다.
따라서 모든 permutation을 비용 순서대로 정렬하고 MST 문제를 해결하면 된다.