PS 문제 풀이 [2021.3]

처음으로 블로그를 만들어 봤다.

무엇을 적어야할지 잘 모르겠어서 일단 재밌었던 문제의 풀이를 몇 개 적어봤다.

PPC 2018 F. Edge Coloring

그래프가 트리일 경우를 생각해 봅시다.

트리의 리프에서부터 루트 아래까지 올라가며 부모 정점으로 가는 간선을 색칠할 때

• 리프일 경우, 무조건 색칠
• 리프도 루트도 아닐 경우, 자식으로 가는 간선 중 색칠된 간선이 짝수일 경우 색칠

이러한 방식으로 각 간선의 색칠 여부를 유일하게 결정할 수 있습니다.

색칠 후에 루트 정점의 차수는 짝수일 수도 홀수일 수도 있는데,

모든 정점의 차수 합은 항상 짝수이므로 \(n\)이 짝수일 때 루트 정점의 차수는 홀수가 됩니다.

그러므로 그래프가 트리일 때는 \(n\)이 짝수면 \(1\), 홀수면 \(0\)이 답이 됩니다.

 

풀이를 확장하여 일반적인 연결 그래프에서 문제를 풀어봅시다.

그래프의 스패닝 트리를 하나 잡고, 스패닝 트리에 포함되지 않은 간선은 아무렇게나 색칠합니다.

이 때의 스패닝 트리의 색칠 또한 유일합니다.

트리에서의 풀이에서 각 정점의 차수의 홀짝 여부만 다르기 때문에, 비슷한 귀납적 방식으로 해결할 수 있습니다.

(물론 \(n\)이 홀수라면 올바른 색칠 방법은 없습니다.)

 

결국 문제의 답은

• \(n\)이 홀수라면 \(0\)
• \(n\)이 짝수라면 \(2^{m-n+1}\)

이 됩니다.

실제로는 그래프가 연결 그래프가 아닐 수 있기 때문에 각 컴포넌트에 대해서 정점과 간선의 개수를 세어 경우의 수를 모두 곱해야 합니다.

 

CEOI 2019. Dynamic Diameter

정점 \(n\)의 루트까지의 거리를 \(d_n\)이라 하면 두 정점 \(u, v\)간의 거리는 \(d_u + d_v - 2 * d_{lca(u, v)}\)가 됩니다.

그러므로 \(u, v\)를 잘 선택해 앞의 식을 최대화하는 문제로 바꿔서 풀 수 있습니다.

\(lca(u, v)\)를 먼저 선택했다면, \(u, v\)는 \(lca(u, v)\)의 서로 다른 서브트리에서 골라야 합니다. (\(u = lca(u, v)\)같은 경우도 있으므로 서브트리에 \(lca(u, v)\)도 포함하여 생각합니다.)

복잡해 보이지만, 이렇게 선택하는 방식은 Euler Tour Tree를 사용하여 1차원적으로 표현할 수 있습니다.

트리를 DFS로 순회하면서 각 정점을 처음 방문할 때와 자식 정점에서 돌아올 때 Euler Tour 배열에 정점을 추가합니다.

(문제의 예제 1번 트리의 경우, \(1, 2, 3, 2, 4, 2, 1\)과 같이 만들어집니다.)

결국 트리에서 \(u, v, lca(u, v)\)를 선택하는 것은 Euler Tour 배열에서 중복을 허용하여 세 개의 수를 선택하는 것과 동일합니다.

선택한 세 수가 순서대로 \(u, lca(u, v), v\)에 해당하기 때문입니다. (\(lca(u, v)\)를 기준으로 서브트리가 나누어 지기 때문에 서로 다른 서브트리에서 선택되게 됩니다.)

\(u\)나 \(v\)가 \(lca(u, v)\)의 자손이 아닌 선택이 일어날 수도 있지만, 이 경우 자손을 선택하는 것보다 항상 손해이므로 무시할 수 있습니다.

결론적으로, 이 문제는 다음과 같은 문제로 환원됩니다:

크기가 \(k\)인 수열 \(a\)가 주어질 때, 다음과 같은 쿼리를 실행하라.

• 1. 어떤 세 정수 \(p, q, r\) \((1 \le p \le q \le r \le k)\)에 대해 \(a_p - 2 * a_q + a_r\)의 최댓값을 계산
• 2. 세 정수 \(s, e, w\) \((1 \le s \le e \le k)\) 이 주어지면 \(a_s, a_{s+1}, \dots , a_e\)에 \(w\)를 더함

1번 쿼리가 지름을 구하는 쿼리에 해당하고, 2번 쿼리는 간선의 가중치를 변경할 때 서브트리에 있는 정점들의 깊이를 변경하는 쿼리에 해당합니다. (Euler Tour 배열에서 어떤 서브트리의 정점들은 모두 연속되어 있습니다.)

 

이 쿼리를 해결하기 위해 세그먼트 트리를 사용해 봅시다.

• 2번 쿼리는 단순한 Lazy Propagation를 통해 해결할 수 있습니다.
• 1번 쿼리가 문제인데, 각 구간에서 다음과 같은 5개의 수를 정의합니다:
  • mx : 구간 최댓값
  • mn : 구간 최솟값
  • left : 구간에서 두 수 p, q \((p \le q)\)를 선택했을 때, \(a_p - 2 * a_q\)의 최댓값
  • right : 구간에서 두 수 p, q \((p \le q)\)를 선택했을 때, \(a_q - 2 * a_p\)의 최댓값
  • answer : 구간에서의 쿼리 1의 답
• 세그먼트 트리의 어떤 구간에 대해 그 구간을 \(S\), 자식 구간중 왼쪽 구간과 오른쪽 구간을 각각 \(L, R\)이라 하면
  • \(S_{mx} = max(L_{mx}, R_{mx})\)
  • \(S_{mn} = min(L_{mn}, R_{mn})\)
  • \(S_{left} = max(L_{left}, R_{left}, L_{mx} - 2 * R_{mn})\)
  • \(S_{right} = max(L_{right}, R_{right}, R_{mx} - 2 * L_{mn})\)
  • \(S_{answer} = max(L_{answer}, R_{answer}, L_{left} + R_{mx}, L_{mx} + R_{right})\)
• 답은 루트 구간의 answer값이 됩니다.

총 시간복잡도는 \(O(N + QlgN)\)입니다.

 

ARC 112 D. Skate

D - Skate

어떤 칸에서 모든 칸을 지나갈 수 있을 조건을 생각해 봅시다.

만약 그 칸에서 시작하여 모든 행에서 멈출 수 있거나 모든 열에서 멈출 수 있다면 모든 칸을 지나갈 수 있습니다.

그렇지 않다면 멈출 수 없는 행과 멈출 수 없는 열이 동시에 존재하고, 이 행과 열이 겹치는 칸은 지나갈 수 없습니다.

이 관찰을 토대로 그래프를 사용해 문제를 풀 수 있습니다.

각 행과 열에 대해 그 줄을 대표하는 정점을 \(H+W\)개 만들고, #인 칸에 대해 그 칸의 행과 열을 간선으로 연결합니다. ( \(S_{1, 1}, S_{1, W}, S_{H, 1}, S_{H, W}\) 중 #이 아닌 것이 있다면 #으로 변경하여 생각합니다.)

이 그래프에서 어떤 두 행을 대표하는 두 정점 사이에 경로가 존재한다면, 한 행에서 시작하여 다른 행에서 멈출 수 있고 열에 관하여도 마찬가지입니다.

즉, 어떤 칸에서 시작하여도 모든 칸을 지나갈 수 있다는 것은 이 그래프에서 모든 행이 연결되어 있거나 모든 열이 연결되어 있는 것과 동일합니다.

#인 칸을 하나 추가하여 두 행을 연결시킬 수 있으므로 모든 행을 연결시키기 위해 필요한 최소 변경 횟수는 (행만을 보았을 때 컴포넌트의 개수) - 1이 됩니다.

열에 대해서도 똑같으므로, 둘 중 작은 값이 정답이 됩니다.

 

Open Cup GP of  Tokyo. Bit Operation

두 수를 골랐을 때 추가되는 수는 \(x = y = 1\)이면 연산 종류에 관계없이 \(1\), \(x = y = 0\)이면 연산 종류에 관계없이 \(0\)이며 \(x \neq y\)이면 \(0\) 또는 \(1\)이 됩니다. 그러므로 문제에서 주어진 연산은 인접한 두 수를 골라 하나의 수를 삭제하는 연산과 동일하다고 볼 수 있습니다. 마지막으로 남을 \(1\)을 고정하고 나머지 수를 삭제하는 경우의 수를 계산해 봅시다.

현재 배열의 크기가 \(M\)일때, \(k\)번째 수를 삭제하기 위해서는 \(k-1, k\)번째 수를 고르거나 \(k, k+1\)번째 수를 골라야 하므로 \(1\)번째와 \(M\)번째 수는 삭제하는 방법이 \(1\)개이고 나머지 수는 \(2\)개입니다.

마지막으로 남은 수의 위치를 \(i\), \(P_{n}\)을 \(1 * 3 * \dots * (2n-1)\)이라고 하면 \(1, 2, \dots , i-1\)번째 수만을 삭제하는 경우의 수는 \(P_{i-1}\)이고, \(i+1, i+2, \dots , n\)번째 수만을 삭제하는 경우의 수는 \(P_{n-i}\)입니다.

\(i\)를 기준으로 왼쪽이나 오른쪽을 \(n-1\)번 고르는 순서의 경우의 수는 \(n-1 \choose i-1\)이므로 \(n-1\)개의 수를 삭제하는 경우의 수는 \({n-1 \choose i-1} * P_{i-1} * P_{n-i}\)입니다.

모든 \(1\)에 대해 위 식을 계산하여 더해주면 전체 경우의 수를 계산할 수 있습니다.

\(N\)이 최대 \(10^6\)이기 때문에 빠른 거듭제곱과 팩토리얼 전처리 등을 통해 \(n-1 \choose i-1\)을 빠르게 계산해주어야 합니다.