PS 문제 풀이 [2021.6]

Innopolis Open,  Second elimination round,  2018-2019 D. Game of Wizards

일단 마지막에 남은 포션의 개수는 생각하지 않고 누가 이기는지만 구해봅시다.

상대의 포션을 없앨 때, 상대의 포션 중 가장 왼쪽에 있지 않은 포션을 없애는 것은 다음 상대의 턴에 영향을 주지 않으므로 나중에 없애도 됩니다. 그러므로 가장 왼쪽부터 몇 개의 포션을 없애는지만 생각합니다.

다음과 같은 DP 식을 정의합니다: (플레이어는 편의상 선공을 \(0\), 후공을 \(1\)이라 하겠습니다.)

• \(D[p][q][x][y][t]\) = 선공이 남은 포션의 개수가 \(p\), 후공이 남은 포션의 개수가 \(q\), 선공이 남은 마나가 \(x\), 후공이 남은 마나가 \(y\), 현재 \(t\)의 턴일 때 이기는 사람
• \(D[p][q][x][y][0]\) = \(min_{0 \le k \le min(q, x+a_{n-p+1})} (D[p-1][q-k][x+a_{n-p+1}-k][y][1])\)
• \(D[p][q][x][y][1]\) = \(max_{0 \le k \le min(p, y+b_{m-q+1})} (D[p-k][q-1][x][y+b_{m-q+1}-k][0])\)

마나가 상대가 가지고 있는 포션의 개수를 넘어간다면 의미가 없으므로 잘라내고, \(max_{0 \le k \le min(p, y)} (D[p-k][q][x][y-k][0])\)와 \(min_{0 \le k \le min(q, x)} (D[p][q-k][x-k][y][1])\)의 값을 다른 배열을 통해 저장해 놓는다면 \(O(N^4)\)의 시간복잡도에 누가 이기는지를 알 수 있습니다. 아직 충분히 빠르지 않습니다.

만약 \(p, q, x, t\)가 고정되었을 때, \(D[p][q][x][y][t]\)의 값은 \(y\)의 값이 어느 정도 작을 때는 \(1\)이다가, 어떤 지점을 넘어서는 순간부터 \(0\)이 될 것입니다. (\(y\)가 클수록 후공이 유리하므로) 이 관찰을 토대로 다음과 같이 다시 DP 식을 정의합니다:

• \(D[p][q][x][t]\) = 선공이 남은 포션의 개수가 \(p\), 후공이 남은 포션의 개수가 \(q\), 선공이 남은 마나가 \(x\), 현재 \(t\)의 턴일 때 후공이 이기는 후공의 최소 마나 (무조건 선공이 이긴다면 \(\infty\))
• \(D[p][q][x][0]\) = \(max_{0 \le k \le min(q, x+a_{n-p+1})} (D[p-1][q-k][x+a_{n-p+1}-k][1])\)
• \(D[p][q][x][1]\) = \(max(0, min_{0 \le k \le p} (D[p-k][q-1][x][0] - b_{m-q+1} + k)\)

이전 DP와 동일하게 다른 보조배열을 만들어서 최소, 최대값을 관리해 주면 \(O(N^3)\)의 시간복잡도에 해결할 수 있습니다.

이제 원래 문제로 돌아와서, 마지막에 남은 포션의 개수를 알아내야 합니다.

만약 이기는 사람의 포션의 마지막 s개를 제거하고 게임을 진행하더라도 그 사람이 이긴다면, 그 사람은 최소 s개의 포션은 남긴 상태로 게임을 이길 수 있습니다. 이 s에 대해 이분 탐색을 진행하면 마지막으로 남은 포션의 개수를 알 수 있습니다. \(O(N^3lgN)\) 시간에 전체 문제를 해결할 수 있습니다.

 

 USACO 2021 US Open Contest, Platinum 1번. United Cows of Farmer John

모든 \(i (1 \le i \le N)\)를 순서대로 순회하며, \(i\)번째 소를 가장 오른쪽 리더로 하는 팀의 개수를 모두 구합니다.

현재 \(i\)번째 수를 순회하고 있을 때, \(i\)번째 이전까지의 수에서 \(r[n]\)을 \(n\)이 마지막으로 나온 위치, \(l[n]\)을 \(n\)이 마지막에서 두번째로 나온 위치라고 합시다. 어떤 \(p, q\)에 대해 순서대로 품종이 \(p, q, b_i\)인 팀이 가능하려면 \(r[b_i] \lt r[p], l[q] \lt r[p] \lt r[q]\)를 만족해야 합니다. \((p, q)\)쌍의 개수를 계산하기 위해 다음과 같은 배열 \(s\)를 정의합니다:

• \(b_n\)이 마지막으로 등장하는 위치가 \(n\)이라면, \(s[n] = \) (\(l[x] \lt n \lt r[x]\)를 만족하는 어떤 \(x\)의 개수)
• 아니하면, \(s[n] = 0\)

조건을 만족하는 \((p, q)\) 쌍의 개수는 \(\sum_{k=r[b_i]+1}^{i-1} s[k]\)가 됩니다. 이 배열 \(s\)를 계속 빠르게 관리할 수 있다면 문제를 해결할 수 있습니다.

\(b_n\)이 마지막으로 등장하는 위치가 \(n\)인 \(s[n]\)을 활성화되었다고 합시다. \(i\)의 탐색이 끝났다면 \(l[b_i] = r[b_i], r[b_i] = i\)가 됩니다. 바꾸기 전에 \(s\)의 값을 업데이트하기 위해 \(s[r[b_i]]\)를 비활성화시키고, \(s[i]\)를 활성화시킵니다. 그리고 \(l[b_i] \lt j \lt r[b_i]\)인 활성화된 \(s[j]\)에 모두 \(1\)을 빼고, \(r[b_i] \lt j \lt i\)인 활성화된 \(s[j]\)에 모두 \(1\)을 더합니다. 이 연산들은 모두 lazy propagation을 사용한 세그먼트 트리로 \(O(lgN)\)에 구현할 수 있습니다. 총 \(O(NlgN)\) 시간에 문제를 해결할 수 있습니다.

 

SEERC 2020 J. One Piece

정점 \(i\)에서 측정된 값을 \(a_i\), 두 정점 \(a, b\) 사이의 거리를 \(dist(a, b)\)라고 합시다. 만약 어떤 두 정점 \(a, b\)에 대해 \(a_i < dist(a, b)\)라면 \(b\)에는 보물이 존재할 수 없습니다. 트리를 탐색하면서 \(min_{1 \le j \le n} (a_j - dist(i, j)) \ge 0\)인 정점(보물이 존재할 수 있는 정점) \(i\)들을 세그먼트 트리 등을 사용하여 계산합니다. 이 때, \(min_{1 \le j \le n} (a_j - dist(i, j)) = 0\)이라면 이 정점을 '끝 정점'이라고 정의합니다. 보물이 존재할 수 있는 정점들만을 모아서 만든 트리를 \(T\)라 합시다. 어떤 정점 \(i\)에 대하여, 그 정점과의 거리가 \(a_i\)이며 \(T\)내부에 있는 정점들 중 적어도 하나에는 보물이 존재해야 하고, 이 정점들은 \(T\) 내부에 있는 가장 먼 정점들입니다. \(T\)의 지름의 중점(가장 먼 정점과의 거리가 최소인 점)을 기준으로 정점들을 나누어봅시다. \(T\)의 지름의 중점을 \(r\)이라고 하고, \(r\)을 루트로 하는 트리의 각 서브트리에서 '끝 정점'들을 모아서 만든 집합들을 각각 \(S_1, S_2, \dots , S_k\)라고 합시다. 첫번째 서브트리에 있는 정점과 가장 먼 \(T\) 내부 정점들의 집합은 \(S_2 \cup S_3 \cup \dots \cup S_k\)와 같습니다. 즉, 모든 \(i\)에 대해 \(S_1 \cup S_2 \cup \dots \cup S_k - S_i\) 중 하나는 보물이 있어야 합니다. 집합의 크기가 작을수록 각 정점에 대한 의존도가 커지므로, 크기가 작은 집합의 정점이 보물이 존재할 확률이 더 높다고 생각할 수 있습니다. 이에 따라, 끝 정점, 끝 정점이 아닌 보물이 있을 수 있는 정점, 보물이 있을 수 없는 정점 순으로 정렬하고, 끝 정점은 그 정점이 포함된 집합의 크기가 작은 순으로 정렬하면 답이 됩니다. \(r\)을 찾는 것은 \(a\) 배열 중 최소값을 찾는 것으로 간단하게 할 수 있습니다. 지름의 길이가 홀수라면 지름의 중점이 간선 위에 있게 되므로, 따로 처리해주어야 합니다.