로봇이 이동할 경로를 미리 정한 뒤 최소 비용을 계산한다고 생각하자. 정점 에서 정점 로 이동할 때 색깔을 바꾸는 방법은 다음 2가지이다.
- 의 색깔을 바꾼다.
- 에 인접한 간선 중 와 색깔이 같으면서 가 아닌 간선들의 색깔을 모두 바꾼다.
그러므로 각 간선에 대해 방향성을 부여하고, 두 방법의 비용 중 더 적은 것을 간선의 가중치로 설정하여 1번 정점에서부터 번 정점까지의 최단 경로를 구하는 방법을 생각할 수 있다. 하지만 1번 방법을 사용한 직후에 2번 방법을 사용하면 간선의 비용이 중복되서 계산될 수 있다는 문제가 있다.
현재 1번 방법으로 원래 색깔이 인 간선 를 통해 정점 에서 정점 로 이동했다고 하자. 그리고 와 인접하면서 색깔이 이고 가 아닌 간선들의 집합을 라고 하자. 이 때 집합 안에서 2번 방법으로 이동할 수 있는 최적 후보는 에서 가장 비용이 큰 간선밖에 없다. (이외의 간선들은 1번 방법으로 이동하는 것이 항상 더 이득이다.) 이 간선을 라고 하면, 최단 경로를 구할 때 에서 로 직접 간선을 연결하는 것으로 중복 계산을 방지할 수 있다.
모든 간선에 대해 이 처리를 해준 뒤 위 방법으로 최단 경로를 구하면 전체 문제를 해결할 수 있다.
문제가 복잡하므로, 가 주어졌을 때 조건을 만족하는 가 존재하기 위해서는 가 어떤 조건을 만족해야 하는지부터 생각한다. 각 열들의 순서가 바뀌더라도 값은 바뀌지 않으므로 를 기준으로 정렬하자.
부터 까지의 값을 순서대로 에 적으면서 를 채운다고 생각하자. 는 정렬되어 있으므로 를 기준으로 생각한다. 부터 까지의 에 대해 다음과 같은 방법으로 를 채울 수 있다.
- 를 를 만족하는 수라고 하자.
- 가 이미 채워져 있다면 넘어간다.
- 으로 할 경우 :
- 가 보다 먼저 채워져야 하므로 를 채우고 를 채워야 한다.
- 그러므로 에서 채워지지 않은 수들은 모두 이 되어야 한다. 이 수들을 로 채운다.
- 으로 할 경우 :
- 를 채우기만 하면 된다. 그러므로 의 값만 로 채워준다.
이 과정을 통해 만든 들은 모두 조건을 만족하며, 조건을 만족하는 를 모두 찾을 수 있다. 그리고 를 수행한 값들을 모은 수열을 라 하면, 을 만족한다. 또한 을 만족하는 가 주어졌을 때 는 유일하게 결정된다.
그러므로 는 를 기준으로 정렬했을 때 에 존재하는 증가 부분 수열의 개수와 같다.
이제 원래 문제는 다음과 같이 환원된다.
- 수열 의 증가 부분 수열의 개수를 라 하자. 일부 위치의 수만이 정해진 순열 가 주어질 때, 가능한 모든 에 대해 의 합을 구하라.
먼저 에 정해진 수가 없다고 생각하자.
를 에서 길이가 이면서 마지막 수가 인 가능한 부분 증가 수열의 개수라고 하면, 다음 식이 성립한다.
그리고 문제의 답은 다음과 같이 계산할 수 있다.
에 정해진 수가 있더라도 비슷한 방식으로 답을 계산할 수 있다.
따라서 또는 에 전체 문제를 해결할 수 있다.
정점 쌍 가 여러 개 주어질 때, 모든 에 대해 에서 로 이동 가능하도록 간선에 방향성을 잘 부여해야 한다. 먼저 DFS 트리를 만들어서 그 방향성을 그대로 간선들에 부여하자. 즉, 트리에 포함된 간선들은 조상에서 자식 방향으로, back edge는 자식에서 조상 방향으로 방향성을 부여한다. 각 BCC 안에서는 이것만으로도 모든 정점 사이에 이동이 가능해진다. (여기서 BCC는 절단선을 기준으로 나눈다.) 각 BCC를 한 정점으로 묶으면 전체 그래프는 트리가 되므로, 트리에서 문제를 푸는 방법을 생각한다.
트리에서 두 정점 사이의 경로는 유일하므로, 각 쌍에 대해 부터 까지의 경로에 있는 간선들의 방향성은 유일하게 결정된다. 이를 naive하게 구현하면 지만, LCA를 기준으로 경로를 나눠서 누적 합으로 최적화하면 에 해결할 수 있다.
항상 공평하게 분배할 수 있는 그리디한 전략을 생각한다.
를 번 사람이 처음부터 지점까지 난을 먹었을 때의 행복도라고 하고, 를 을 만족하는 라고 하자.
부터 까지의 에 대해, 다음과 같은 과정으로 난을 분배할 수 있다.
- 현재 난을 분배받지 않은 사람 중 가 최소인 사람 를 이라 하자.
- 으로 하고, 에게 와 사이의 난을 분배한다.
각 과정에서, 와 사이의 난을 먹었을 때의 행복도가 전체 행복도의 에 해당한다. 그런데 이므로 위 방법은 항상 올바르게 난을 분배한다. 따라서 위 방법 그대로 난을 분배하면 전체 문제를 해결할 수 있다.
먼저 사람이 나가는 쿼리가 없을 때를 생각한다.
각 쿼리에 대해, 답이 no이기 위해서는 다음 조건을 만족하는 와 가 존재해야 한다.
전체 식을 로 나누면 다음과 같다.
1~4번째 조건은, 좌표 평면에서 가 들의 convex hull 내부에 포함되어야 한다고 해석할 수 있다. 들의 upper hull을 구하면 의 오른쪽 위에 convex hull 내부의 점이 존재하는지 에 알 수 있으므로 쿼리의 답을 구할 수 있다.
이제 사람이 나가는 쿼리가 있을 때를 생각한다.
사람이 나가는 것보다 들어오는 것이 더 처리하기 쉬우므로 전체 쿼리를 뒤집자. 번 사람이 들어오는 것은, 좌표평면에 점 를 추가하는 것으로 생각할 수 있다. upper hull의 점들을 set으로 관리하면 점이 추가될 때 upper hull을 빠르게 수정해줄 수 있다. 따라서 전체 에 문제가 해결된다.
