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\ast 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\ast 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\ast a_q$의 최댓값
  • right : 구간에서 두 수 p, q $(p\le q)$를 선택했을 때, $a_q-2\ast 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\ast R_{mn})$
  • $S_{right}=max(L_{right},R_{right},R_{mx}-2\ast 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\ne y$이면 $0$ 또는 $1$이 됩니다. 그러므로 문제에서 주어진 연산은 인접한 두 수를 골라 하나의 수를 삭제하는 연산과 동일하다고 볼 수 있습니다. 마지막으로 남을 $1$을 고정하고 나머지 수를 삭제하는 경우의 수를 계산해 봅시다.

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

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

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

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

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