PS 문제 풀이 [2021.10]

JOI 2021. Robot

로봇이 이동할 경로를 미리 정한 뒤 최소 비용을 계산한다고 생각하자. 정점 \(u\)에서 정점 \(v\)로 이동할 때 색깔을 바꾸는 방법은 다음 2가지이다.

 

1. \((u, v)\)의 색깔을 바꾼다.
2. \(u\)에 인접한 간선 중 \((u, v)\)와 색깔이 같으면서 \((u, v)\)가 아닌 간선들의 색깔을 모두 바꾼다.

그러므로 각 간선에 대해 방향성을 부여하고, 두 방법의 비용 중 더 적은 것을 간선의 가중치로 설정하여 1번 정점에서부터 \(N\)번 정점까지의 최단 경로를 구하는 방법을 생각할 수 있다. 하지만 1번 방법을 사용한 직후에 2번 방법을 사용하면 간선의 비용이 중복되서 계산될 수 있다는 문제가 있다.

 

현재 1번 방법으로 원래 색깔이 \(c\)인 간선 \((u, v)\)를 통해 정점 \(u\)에서 정점 \(v\)로 이동했다고 하자. 그리고 \(v\)와 인접하면서 색깔이 \(c\)이고 \((u, v)\)가 아닌 간선들의 집합을 \(S\)라고 하자. 이 때 집합 \(S\) 안에서 2번 방법으로 이동할 수 있는 최적 후보는 \(S\)에서 가장 비용이 큰 간선밖에 없다. (이외의 간선들은 1번 방법으로 이동하는 것이 항상 더 이득이다.) 이 간선을 \((v, w)\)라고 하면, 최단 경로를 구할 때 \(u\)에서 \(w\)로 직접 간선을 연결하는 것으로 중복 계산을 방지할 수 있다.

 

모든 간선에 대해 이 처리를 해준 뒤 위 방법으로 최단 경로를 구하면 전체 문제를 해결할 수 있다.

 

Petrozavodsk Summer 2021 Day 3. Joke

문제가 복잡하므로, \(p, q\)가 주어졌을 때 조건을 만족하는 \(a\)가 존재하기 위해서는 \(s\)가 어떤 조건을 만족해야 하는지부터 생각한다. 각 열들의 순서가 바뀌더라도 \(f(p, q)\) 값은 바뀌지 않으므로 \(p\)를 기준으로 정렬하자.

 

\(1\)부터 \(2n\)까지의 값을 순서대로 \(a\)에 적으면서 \(s\)를 채운다고 생각하자. \(p\)는 정렬되어 있으므로 \(q\)를 기준으로 생각한다. \(1\)부터 \(n\)까지의 \(i\)에 대해 다음과 같은 방법으로 \(s\)를 채울 수 있다.

 

• \(k\)를 \(q_k = i\)를 만족하는 수라고 하자.
• \(s_k\)가 이미 채워져 있다면 넘어간다.
• \(s_k = 0\)으로 할 경우 :
  • \(a_{1,k}\)가 \(a_{2,k}\)보다 먼저 채워져야 하므로 \(a_{1,1} \dots a_{1,k}\)를 채우고 \(a_{2,k}\)를 채워야 한다.
  • 그러므로 \(s_1 \dots s_k\)에서 채워지지 않은 수들은 모두 \(0\)이 되어야 한다. 이 수들을 \(0\)로 채운다.
• \(s_k = 1\)으로 할 경우 :
  •  \(a_{2,k}\)를 채우기만 하면 된다.  그러므로 \(s_k\)의 값만 \(1\)로 채워준다.

이 과정을 통해 만든 \(s\)들은 모두 조건을 만족하며, 조건을 만족하는 \(s\)를 모두 찾을 수 있다. 그리고 \(s_k = 0\)를 수행한 \(k\) 값들을 모은 수열을 \(P = \{ k_1, k_2, \dots , k_m \} (k_1 < k_2 < \dots < k_m)\)라 하면, \(q_{k_1} < q_{k_2} < \dots < q_{k_m}\)을 만족한다. 또한 \(q_{k_1} < q_{k_2} < \dots < q_{k_m}\)을 만족하는 \(P\)가 주어졌을 때 \(s\)는 유일하게 결정된다.

그러므로 \(f(p, q)\)는 \(p\)를 기준으로 정렬했을 때 \(q\)에 존재하는 증가 부분 수열의 개수와 같다.

 

이제 원래 문제는 다음과 같이 환원된다.

 

• 수열 \(A\)의 증가 부분 수열의 개수를 \(f(A)\)라 하자. 일부 위치의 수만이 정해진 순열 \(q\)가 주어질 때, 가능한 모든 \(q\)에 대해 \(f(q)\)의 합을 구하라.

먼저 \(q\)에 정해진 수가 없다고 생각하자.

\(D[i][j][k]\)를 \(q_1 \dots q_i\)에서 길이가 \(j\)이면서 마지막 수가 \(k\)인 가능한 부분 증가 수열의 개수라고 하면, 다음 식이 성립한다.

 

• \(D[0][0][0] = 1\)
• \(D[i][j][k] = D[i - 1][j][k] + (\sum_{p=1}^{k-1} D[i-1][j-1][p])\)

그리고 문제의 답은 다음과 같이 계산할 수 있다.

 

• \(ans = \sum_{i=0}^n \{ (\sum_{j=0}^n D[n][i][j]) * (n-i)! \} \)

\(q\)에 정해진 수가 있더라도 비슷한 방식으로 답을 계산할 수 있다.

따라서 \(O(n^3)\) 또는 \(O(n^4)\)에 전체 문제를 해결할 수 있다.

 

Petrozavodsk Winter 2020 Day 2. One-Way Conveyors

정점 쌍 \((a, b)\)가 여러 개 주어질 때, 모든 \((a, b)\)에 대해 \(a\)에서 \(b\)로 이동 가능하도록 간선에 방향성을 잘 부여해야 한다. 먼저 DFS 트리를 만들어서 그 방향성을 그대로 간선들에 부여하자. 즉, 트리에 포함된 간선들은 조상에서 자식 방향으로, back edge는 자식에서 조상 방향으로 방향성을 부여한다. 각 BCC 안에서는 이것만으로도 모든 정점 사이에 이동이 가능해진다. (여기서 BCC는 절단선을 기준으로 나눈다.) 각 BCC를 한 정점으로 묶으면 전체 그래프는 트리가 되므로, 트리에서 문제를 푸는 방법을 생각한다.

 

트리에서 두 정점 사이의 경로는 유일하므로, 각 \((a, b)\) 쌍에 대해 \(a\)부터 \(b\)까지의 경로에 있는 간선들의 방향성은 유일하게 결정된다. 이를 naive하게 구현하면 \(O((n+m)k)\)지만, LCA를 기준으로 경로를 나눠서 누적 합으로 최적화하면 \(O((n+k)logn + m)\)에 해결할 수 있다.

 

JOI  2018/2019 Spring Training Camp. 난

항상 공평하게 분배할 수 있는 그리디한 전략을 생각한다.

\(S(i, x)\)를 \(i\)번 사람이 처음부터 \(x\) 지점까지 난을 먹었을 때의 행복도라고 하고, \(X(i, t)\)를 \(\dfrac{t}{N} = \dfrac{S(i, x)}{S(i, L)}\)을 만족하는 \(x\)라고 하자.

\(1\)부터 \(N\)까지의 \(t\)에 대해, 다음과 같은 과정으로 난을 분배할 수 있다.

 

• 현재 난을 분배받지 않은 사람 중 \(X(i, t)\)가 최소인 사람 \(i\)를 \(i_{mn}\)이라 하자.
• \(X_t = X(i_{mn}, t)\)으로 하고, \(i_{mn}\)에게 \(X_{t-1}\)와 \(X(i_{mn}, t)\)사이의 난을 분배한다.

각 과정에서, \(X(i_{mn}, t - 1)\)와 \(X(i_{mn}, t)\) 사이의 난을 먹었을 때의 행복도가 전체 행복도의 \(\frac{1}{N}\)에 해당한다. 그런데 \(X_{t-1} \le X(i_{mn}, t - 1)\)이므로 위 방법은 항상 올바르게 난을 분배한다. 따라서 위 방법 그대로 난을 분배하면 전체 문제를 해결할 수 있다.

 

NCPC 2021. Hiring Help

먼저 사람이 나가는 쿼리가 없을 때를 생각한다.

각 쿼리에 대해, 답이 no이기 위해서는 다음 조건을 만족하는 \(t_1, t_2, \dots, t_n\)와 \(x, y\)가 존재해야 한다.

 

• \(0 \le t_i (1 \le i \le n)\)
• \(sum_{i=1}^n t_i = t\)
• \(sum_{i=1}^n t_i * l_i = x\)
• \(sum_{i=1}^n t_i * b_i = y\)
• \(x \ge l\)
• \(y \ge b\)

전체 식을 \(t\)로 나누면 다음과 같다.

 

• \(0 \le t_i (1 \le i \le n)\)
• \(sum_{i=1}^n t_i = 1\)
• \(sum_{i=1}^n t_i * l_i = x\)
• \(sum_{i=1}^n t_i * b_i = y\)
• \(x \ge \frac{l}{t}\)
• \(y \ge \frac{b}{t}\)

1~4번째 조건은, 좌표 평면에서 \((x, y)\)가 \((l_i, b_i)\)들의 convex hull 내부에 포함되어야 한다고 해석할 수 있다. \((l_i, b_i)\)들의 upper hull을 구하면 \((\frac{l}{t}, \frac{b}{t})\)의 오른쪽 위에 convex hull 내부의 점이 존재하는지 \(O(logn)\)에 알 수 있으므로 쿼리의 답을 구할 수 있다.

 

이제 사람이 나가는 쿼리가 있을 때를 생각한다.

사람이 나가는 것보다 들어오는 것이 더 처리하기 쉬우므로 전체 쿼리를 뒤집자. \(i\)번 사람이 들어오는 것은, 좌표평면에 점 \((l_i, b_i)\)를 추가하는 것으로 생각할 수 있다. upper hull의 점들을 set으로 관리하면 점이 추가될 때 upper hull을 빠르게 수정해줄 수 있다. 따라서 전체 \(O((n+e)logn)\)에 문제가 해결된다.